下面给出的是$ C $下，我想有人帮我找出了时间和空间的复杂性，同时考虑到他们两人将仅仅依靠的排序算法code给定的程序。 请记住，没有了。你可以输入应该是一个奇数不含1，和偶数列将产生错误的结果，由于code被排序方式列的。 当问及不断倍增器，你需要在这些测试数字，这有助于排序的二维数组键入： 1.为100元，列= 33和恒定倍数= 4， 2.为200元，列= 67，不断乘数= 10， 3.为300元，列= 101和恒定的乘数= 15， 4.为400元，列= 133和恒定的乘数= 15， 5.对于500元，列= 167和恒定的乘数= 25， 6.为30000元，列= 9999，不断乘数= 2500。 等等。等等。
我也愿意接受从其他地方保存一个txt文件的输入。我该怎么办呢？ 干杯。感谢您与我露出：）
在code：
＃包括＆LT;的iostream＆GT;
＃包括＆LT; CONIO.H＆GT;
＃包括＆LT; stdio.h中＆GT;
＃包括＆LT; fstream的＆GT;
使用名字空间std;
无效的主要（）
{
系统（CLS）;
INT关口;
INT D组;
诠释缺点= 1;
A：
COUT＆LT;＆LT; ENDL;
诠释一个[3] [40000] = {{0}}; //初始化数组0
COUT＆LT;＆LT; 输入栏没有。; //没有。列的3XN矩阵
CIN＆GT;＆GT; COL;
INT NOE = COL * 3;元素//总数
// code，接受不断的倍增器
COUT＆LT;＆LT; 输入系数器;
CIN＆GT;＆GT;缺点;
// code，生成随机整数的列表，并将其存储在阵列中
的for（int i = 0; I＆LT;西;我++）
为（诠释J = 0; J＆所述; 3; J ++）
{
D =兰特（）％9000;
一个[J] [我] = D;
}
INT K = 0;
INT温度; //临时存储
INT标志= 0;
//排序算法
对于（INT N = 0; N＆LT; = NOE *利弊; N ++）
{
如果（（K％2 == 0）及及（标志== 0））
{
//排序上三角
// 3行检查
如果（一个[0] [k]的＆gt;一种[0] [K + 1]）
{
临时=一个[0] [K + 1];
一个[0] [K + 1] = A [0] [k]的;
一个[0] [k]的=气温;
}
如果（一个[1] [k]的＆gt;一种[1] [K + 1]）
{
临时=一个[1] [K + 1];
一个[1] [K + 1] = A [1] [k]的;
一个[1] [k]的=气温;
}
如果（一个[2] [k]的＆gt;一种[0] [K + 2]）
{
临时=一个[0] [K + 2];
一个[0] [K + 2] = A [2] [k]的;
一个[2] [k]的=气温;
}
//第一列检查
{
如果（一个[0] [k]的＆gt;一种[1] [k]的）
{
温度=一[1] [k]的;
一个[1] [k]的一个= [0] [k]的;
一个[0] [k]的=气温;
}
如果（一个[1] [k]的＆gt;一种[2] [k]的）
{
温度=一个[2] [k]的;
一个[2] [k]的一个= [1] [k]的;
一个[1] [k]的=气温;
}
如果（一个[0] [k]的＆gt;一种[1] [k]的）
{
温度=一[1] [k]的;
一个[1] [k]的一个= [0] [k]的;
一个[0] [k]的=气温;
}
}
//第二列检查
{
如果（一个[0] [K + 1]＆gt;在[1] [K + 1]）
{
临时=一个[1] [K + 1];
一个[1] [K + 1] = A [0] [K + 1];
一个[0] [K + 1] =温度;
}
如果（一个[1] [K + 1]＆gt;在[0] [K + 2]）
{
临时=一个[0] [K + 2];
一个[0] [K + 2] = A [1] [K + 1];
一个[1] [K + 1] =温度;
}
如果（一个[0] [K + 1]＆gt;在[1] [K + 1]）
{
临时=一个[1] [K + 1];
一个[1] [K + 1] = A [0] [K + 1];
一个[0] [K + 1] =温度;
}
}
// 3对角线检查
如果（一个[0] [K + 1];一个[1] [k]的）
{
温度=一[1] [k]的;
一个[1] [k]的一个= [0] [K + 1];
一个[0] [K + 1] =温度;
}
如果（一个[2] [k]的＆gt;一种[1] [K + 1]）
{
临时=一个[1] [K + 1];
一个[1] [K + 1] = A [2] [k]的;
一个[2] [k]的=气温;
}
如果（一个[2] [k]的＆gt;一种[0] [K + 1]）
{
临时=一个[0] [K + 1];
一个[0] [K + 1] = A [2] [k]的;
一个[2] [k]的=气温;
}
//上三角排序
K = K + 2;
如果（K ==（山口 - 1））标志= 1;
}
否则如果（（K％2 == 0）及及（标志== 1））
{
//排序下三角
// 3行检查
如果（一个[2] [K - 2]＆gt;在[0] [k]的）
{
温度=一个[0] [k]的;
一个[0] [k]的一个= [2] [K - 1];
一个[2] [K - 2] =温度;
}
如果（一个[1] [K - 1]＆gt;在[1] [k]的）
{
温度=一[1] [k]的;
一个[1] [k]的一个= [1] [K - 1];
一个[1] [K - 1] =温度;
}
如果（一个[2] [K - 1]＆gt;在[2] [k]的）
{
温度=一个[2] [k]的;
一个[2] [k]的一个= [2] [K - 1];
一个[2] [K - 1] =温度;
}
//第一列检查
{
如果（一个[2] [K - 2]＆gt;在[1] [K - 1]）
{
温度=一[1] [K - 1];
一个[1] [K - 1] = A [2] [K - 2];
一个[2] [K - 2] =温度;
}
如果（一个[1] [K - 1]＆gt;在[2] [K - 1]）
{
温度=一个[2] [K - 1];
一个[2] [K - 1] = A [1] [K - 1];
一个[1] [K - 1] =温度;
}
如果（一个[2] [K - 2]＆gt;在[1] [K - 1]）
{
温度=一[1] [K - 1];
一个[1] [K - 1] = A [2] [K - 2];
一个[2] [K - 2] =温度;
}
}
//第二列检查
{
如果（一个[0] [k]的＆gt;一种[1] [k]的）
{
温度=一[1] [k]的;
一个[1] [k]的一个= [0] [k]的;
一个[0] [k]的=气温;
}
如果（一个[1] [k]的＆gt;一种[2] [k]的）
{
温度=一个[2] [k]的;
一个[2] [k]的一个= [1] [k]的;
一个[1] [k]的=气温;
}
如果（一个[0] [k]的＆gt;一种[1] [k]的）
{
温度=一[1] [k]的;
一个[1] [k]的一个= [0] [k]的;
一个[0] [k]的=气温;
}
}
// 3对角线检查
如果（一个[0] [k]的＆其中;一个[1] [K - 1]）
{
温度=一[1] [K - 1];
一个[1] [K - 1] = A [0] [k]的;
一个[0] [k]的=气温;
}
如果（一个[2] [K - 1]＆gt;在[1] [k]的）
{
温度=一[1] [k]的;
一个[1] [k]的一个= [2] [K - 1];
一个[2] [K - 1] =温度;
}
如果（一个[2] [K - 1]＆gt;在[0] [k]的）
{
温度=一个[0] [k]的;
一个[0] [k]的一个= [2] [K - 1];
一个[2] [K - 1] =温度;
}
//下三角排序
k = k - 2;
如果（K == 0）标志= 0;
}
}
// code打印排序元素
COUT＆LT;＆LT; 排序元素：＆LT;＆LT; ENDL;
的for（int i = 0; I＆LT;西;我++）
为（诠释J = 0; J＆所述; 3; J ++）
{
COUT＆LT;＆LT;一个[J] [1] - ;＆LT; ;
}
// code检查的元素进行排序或不
int类型l = 0;
的int =一个[0] [0];
的for（int i = 0; I＆LT;西;我++）
为（诠释J = 0; J＆所述; 3; J ++）
{
如果（S＆gt;在[J] [我]）l ++;
S =一个[j]的[I];
}
如果（L == 0）COUT＆LT;＆LT; ！ nSorted阵 N的;
否则COUT＆LT;＆LT; ！ nUnsorted N的;
系统（暂停）;
GOTO A;
}
解决方案
翻翻算法，它会开始出现，这是一个O（n）的时间复杂度的排序算法，如果我们把常数因子为常数（你'已经得到了一个循环与C * n次迭代），但比较基于排序算法有一个下界为O（n *的log（n））。这要么意味着。你没有成功，在传统意义上的对数据进行排序（我假设这是不是这样），B。你正在做一个非比较排序（它似乎你正在做一个比较排序），或c。常数因子不能被视为恒定（这是几乎可以肯定的情况下，特别是因为在恒定的因素是较大的放大输入）。
你是如何确定的常数因子？这是它的相对于输入的大小？你需要确定（如统计学，因为我在评论中所述）是这种关系是否如常数因子= C *日志（输入大小），或常数因子= C *（输入大小），或介于两者之间。
空间复杂度似乎是一个常数，因为你没有动态地分配任何内存或使用交换阵列之类的东西，也不是你使用递归。
Given below is the code for which I would like someone to help me figure out the time and space complexity, keeping in mind that both of them would depend only on the "Sorting Algorithm Code" of the given program. Do keep in mind that the no. of columns that you can take as input should be an odd integer excluding 1, and an even numbered column will yield false results due to the way the code is being sorted. When asked for the "constant multiplier" you need to type in these tested numbers, that help sort the 2D array: 1. For 100 elements, columns=33 and constant multiplier=4, 2. For 200 elements, columns=67 and constant multiplier=10, 3. For 300 elements, columns=101 and constant multiplier=15, 4. For 400 elements, columns=133 and constant multiplier=15, 5. For 500 elements, columns=167 and constant multiplier=25, 6. For 30000 elements, columns=9999 and constant multiplier=2500. etc.. etc..
I would also like to accept input from a .txt file saved elsewhere. How can I do it? Cheers. Thanks for baring with me :)
The Code:
#include<iostream>
#include<conio.h>
#include<stdio.h>
#include<fstream>
using namespace std;
void main()
{
system("cls");
int col;
int d;
int cons=1;
A:
cout << endl;
int a[3][40000] = { {0} };//Initializing the array to 0
cout << "enter no. of columns:";//No. of Columns for the 3xN matrix
cin >> col;
int noe = col * 3;//Total No. of Elements
//Code to accept the constant multiplier
cout << "Enter the constant multiplier:";
cin >> cons;
//Code to generate a list of random integers and store it in the array
for (int i = 0; i < col;i++)
for (int j = 0; j < 3; j++)
{
d = rand() % 9000;
a[j][i] = d;
}
int k = 0;
int temp;//Temporary Storage
int flag = 0;
//Sorting algorithm
for (int n = 0; n <= noe*cons; n++)
{
if ((k % 2 == 0) && (flag == 0))
{
//Sorting Upper Triangle
//3 row check
if (a[0][k]>a[0][k + 1])
{
temp = a[0][k + 1];
a[0][k + 1] = a[0][k];
a[0][k] = temp;
}
if (a[1][k] > a[1][k + 1])
{
temp = a[1][k + 1];
a[1][k + 1] = a[1][k];
a[1][k] = temp;
}
if (a[2][k] > a[0][k + 2])
{
temp = a[0][k + 2];
a[0][k + 2] = a[2][k];
a[2][k] = temp;
}
//First Column Check
{
if (a[0][k] > a[1][k])
{
temp = a[1][k];
a[1][k] = a[0][k];
a[0][k] = temp;
}
if (a[1][k] > a[2][k])
{
temp = a[2][k];
a[2][k] = a[1][k];
a[1][k] = temp;
}
if (a[0][k] > a[1][k])
{
temp = a[1][k];
a[1][k] = a[0][k];
a[0][k] = temp;
}
}
//Second Column Check
{
if (a[0][k + 1] > a[1][k + 1])
{
temp = a[1][k + 1];
a[1][k + 1] = a[0][k + 1];
a[0][k + 1] = temp;
}
if (a[1][k + 1] > a[0][k + 2])
{
temp = a[0][k + 2];
a[0][k + 2] = a[1][k + 1];
a[1][k + 1] = temp;
}
if (a[0][k + 1] > a[1][k + 1])
{
temp = a[1][k + 1];
a[1][k + 1] = a[0][k + 1];
a[0][k + 1] = temp;
}
}
//3 Diagonal Checks
if (a[0][k + 1] < a[1][k])
{
temp = a[1][k];
a[1][k] = a[0][k + 1];
a[0][k + 1] = temp;
}
if (a[2][k] > a[1][k + 1])
{
temp = a[1][k + 1];
a[1][k + 1] = a[2][k];
a[2][k] = temp;
}
if (a[2][k] > a[0][k + 1])
{
temp = a[0][k + 1];
a[0][k + 1] = a[2][k];
a[2][k] = temp;
}
//Upper Triangle Sorted
k = k + 2;
if (k == (col - 1))flag = 1;
}
else if ((k % 2 == 0) && (flag == 1))
{
//Sorting Lower Triangle
//3 row check
if (a[2][k - 2]>a[0][k])
{
temp = a[0][k];
a[0][k] = a[2][k - 1];
a[2][k - 2] = temp;
}
if (a[1][k - 1] > a[1][k])
{
temp = a[1][k];
a[1][k] = a[1][k - 1];
a[1][k - 1] = temp;
}
if (a[2][k - 1] > a[2][k])
{
temp = a[2][k];
a[2][k] = a[2][k - 1];
a[2][k - 1] = temp;
}
//First Column Check
{
if (a[2][k - 2] > a[1][k - 1])
{
temp = a[1][k - 1];
a[1][k - 1] = a[2][k - 2];
a[2][k - 2] = temp;
}
if (a[1][k - 1] > a[2][k - 1])
{
temp = a[2][k - 1];
a[2][k - 1] = a[1][k - 1];
a[1][k - 1] = temp;
}
if (a[2][k - 2] > a[1][k - 1])
{
temp = a[1][k - 1];
a[1][k - 1] = a[2][k - 2];
a[2][k - 2] = temp;
}
}
//Second Column Check
{
if (a[0][k] > a[1][k])
{
temp = a[1][k];
a[1][k] = a[0][k];
a[0][k] = temp;
}
if (a[1][k] > a[2][k])
{
temp = a[2][k];
a[2][k] = a[1][k];
a[1][k] = temp;
}
if (a[0][k] > a[1][k])
{
temp = a[1][k];
a[1][k] = a[0][k];
a[0][k] = temp;
}
}
//3 Diagonal Checks
if (a[0][k] < a[1][k - 1])
{
temp = a[1][k - 1];
a[1][k - 1] = a[0][k];
a[0][k] = temp;
}
if (a[2][k - 1] > a[1][k])
{
temp = a[1][k];
a[1][k] = a[2][k - 1];
a[2][k - 1] = temp;
}
if (a[2][k - 1] > a[0][k])
{
temp = a[0][k];
a[0][k] = a[2][k - 1];
a[2][k - 1] = temp;
}
//Lower Triangle Sorted
k = k - 2;
if (k == 0)flag = 0;
}
}
//Code to print the sorted elements
cout << "Sorted Elements:" << endl;
for (int i = 0; i < col; i++)
for (int j = 0; j < 3; j++)
{
cout << a[j][i] << " ";
}
//Code to check if the elements are sorted or not
int l = 0;
int s = a[0][0];
for (int i = 0; i < col;i++)
for (int j = 0; j < 3; j++)
{
if (s > a[j][i])l++;
s = a[j][i];
}
if (l == 0)cout << "nSorted Array!n";
else cout << "nUnsorted!n";
system("pause");
goto A;
}
解决方案
Looking through the algorithm, it would initially appear that this is an O(n) time complexity sorting algorithm if we treat the constant factor as a constant (you've got one loop with C * n iterations), but a comparison based sorting algorithm has a lower bound of O(n * log(n)). This either means that a. you're not successfully sorting the data in the traditional sense of the word (I'm assuming this isn't the case), b. you're doing a non-comparison sort (and it appears that you are doing a comparison sort), or c. the constant factor can't be treated as a constant (this is almost certainly the case, particularly because the constant factor is larger for larger inputs).
How are you determining the constant factor? What is its relation to the input size? What you need to determine (e.g. statistically as I described in the comments) is whether this relation is e.g. "constant factor = C * log(input size)", or "constant factor = C * (input size)", or something in between.
Space complexity appears to be a constant, because you're not dynamically allocating any memory or using a swap array or anything like that, nor are you using recursion.
相关推荐
最新文章