shell 使用 hibbard 增量排序
shell sort using hibbard increment
我是 C 的新手。我想在 C 中使用 hibbard 增量对 shell 排序进行实验。而且,为了测试最坏的情况,我总是根据输入大小。我希望在时间复杂度 O(n^1.5) 之后看到 运行 时间。但是,我的输出以某种方式遵循时间复杂度 O(n)。以下是我的代码。如果有人能帮我找到问题所在,我将不胜感激。
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
int get_input() {
int input;
printf("Please type input size(n): ");
if(scanf("%d", &input) == 0) {
fscanf(stdin, "%*[^\n]%*c");
}
return input;
}
int* build_data(int* array, int size) {
array = malloc(sizeof(int) * size);
for(int i=0; i < size; i++) {
array[i] = size - i;
}
return array;
}
double record_time(int* array, int size, void (*fp)(int*, int)) {
clock_t begin = clock();
(*fp)(array, size);
clock_t end = clock();
return (double)(end - begin) / CLOCKS_PER_SEC;
}
void shell_sort(int* array, int size) {
int* h_inc;
int h_size;
h_size = floor(log(size+1)/log(2));
h_inc = malloc(sizeof(int) * h_size);
for(int i=0; i < h_size; i++) {
h_inc[i] = pow(2, i+1) - 1;
}
int i, j, tmp;
for (int r = (h_size - 1); r >= 0; r--) {
int gap = h_inc[r];
for(i = gap; i < size; i++) {
tmp = array[i];
for(j = i; j >= gap && tmp < array[j-gap]; j-=gap) {
array[j] = array[j-gap];
}
array[j] = tmp;
}
}
free(h_inc);
return;
}
int main() {
while(1) {
int size;
int* data;
double time_elapsed;
size = get_input();
if (size <= 0) { break; }
data = build_data(data, size);
time_elapsed = record_time(data, size, shell_sort);
printf("Elapsed time: %f sec\n", time_elapsed);
free(data);
}
return 0;
}
我的输出是:
Please type input size(n): 10000
Elapsed time: 0.001168 sec
Please type input size(n): 50000
Elapsed time: 0.006094 sec
Please type input size(n): 100000
Elapsed time: 0.010946 sec
Please type input size(n): 500000
Elapsed time: 0.054341 sec
Please type input size(n): 1000000
Elapsed time: 0.118640 sec
Please type input size(n): 5000000
Elapsed time: 0.618815 sec
Please type input size(n): 10000000
Elapsed time: 1.332671 sec
我想我们在这里比较的是不同的东西。 运行 一个程序的时间复杂度和时间是不同的。时间复杂度可以简单的表示为asymptotic behavior of running time as input size tends to infinity.
现在你说的是在说跟O(n)
。我猜您正在查看两个输入并考虑时间的乘法增量。您的算法可能在 An^1.5+bn+C
个周期内 运行ning。所以首先你不能比较……完全一样。您可以说随着输入的增加,它会渐近地接近与 n^1.5
.
成比例的函数
程序 运行 时间和复杂性之间的直接关联不是您应该寻找的。相反,您可以从程序中完成的基本操作来考虑。
如果你认为我们可以从 运行ning 时间完全考虑时间复杂度,那么我想我们不需要考虑那些基本操作等等。
我不认为逆序是(这个)shell 排序的最坏情况。我把你的代码 运行 放在我的 Mac 上,得到了时间:
Please type input size(n): 10000
Elapsed time: 0.000247 sec
Please type input size(n): 50000
Elapsed time: 0.001314 sec
Please type input size(n): 100000
Elapsed time: 0.002768 sec
Please type input size(n): 500000
Elapsed time: 0.016154 sec
Please type input size(n): 1000000
Elapsed time: 0.033013 sec
Please type input size(n): 5000000
Elapsed time: 0.173584 sec
Please type input size(n): 10000000
Elapsed time: 0.338931 sec
Please type input size(n): 10000000
Elapsed time: 0.344284 sec
Please type input size(n): 10000000
Elapsed time: 0.343052 sec
Please type input size(n): 0
然后我用 rand()
替换了你的 size - i
,并在 main()
的开头添加了 srand(time(0));
:
static int *build_data(int *array, int size)
{
array = malloc(sizeof(int) * size);
for (int i = 0; i < size; i++)
{
array[i] = rand(); //size - i;
}
return array;
}
运行备选方案,我有这样的时间:
Please type input size(n): 10000
Elapsed time: 0.001117 sec
Please type input size(n): 50000
Elapsed time: 0.007097 sec
Please type input size(n): 100000
Elapsed time: 0.015724 sec
Please type input size(n): 500000
Elapsed time: 0.095657 sec
Please type input size(n): 1000000
Elapsed time: 0.191383 sec
Please type input size(n): 5000000
Elapsed time: 1.214821 sec
Please type input size(n): 10000000
Elapsed time: 2.684908 sec
Please type input size(n): 10000000
Elapsed time: 2.716862 sec
Please type input size(n): 10000000
Elapsed time: 2.739099 sec
Please type input size(n): 0
这些时间远远长于反向序号的时间。时间也比线性增长更快——不是那么显着,但肯定更快。而减法和调用之间的区别 rand()
不是问题的根源。我还创建了一个这样的版本:
static int *build_data(int *array, int size)
{
array = malloc(sizeof(int) * size);
unsigned long random_sum = 0;
for (int i = 0; i < size; i++)
{
array[i] = size - i;
random_sum += rand();
}
printf("Random sum: %lu\n", random_sum);
return array;
}
示例输出是:
Please type input size(n): 10000
Random sum: 10730036823932
Elapsed time: 0.000380 sec
Please type input size(n): 50000
Random sum: 53866916004733
Elapsed time: 0.001351 sec
Please type input size(n): 100000
Random sum: 107321572319270
Elapsed time: 0.002879 sec
Please type input size(n): 500000
Random sum: 536869931129596
Elapsed time: 0.015761 sec
Please type input size(n): 1000000
Random sum: 1073512237256859
Elapsed time: 0.034148 sec
Please type input size(n): 5000000
Random sum: 5370226579401372
Elapsed time: 0.170608 sec
Please type input size(n): 10000000
Random sum: 10737805324344696
Elapsed time: 0.357169 sec
Please type input size(n): 10000000
Random sum: 10735216573040655
Elapsed time: 0.350111 sec
Please type input size(n): 10000000
Random sum: 10739807847077051
Elapsed time: 0.349979 sec
Please type input size(n): 0
慢一点,是的;除其他所有内容外,还需要一个额外的 printf()
。但不像 运行dom 数据那么慢。
我是 C 的新手。我想在 C 中使用 hibbard 增量对 shell 排序进行实验。而且,为了测试最坏的情况,我总是根据输入大小。我希望在时间复杂度 O(n^1.5) 之后看到 运行 时间。但是,我的输出以某种方式遵循时间复杂度 O(n)。以下是我的代码。如果有人能帮我找到问题所在,我将不胜感激。
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
int get_input() {
int input;
printf("Please type input size(n): ");
if(scanf("%d", &input) == 0) {
fscanf(stdin, "%*[^\n]%*c");
}
return input;
}
int* build_data(int* array, int size) {
array = malloc(sizeof(int) * size);
for(int i=0; i < size; i++) {
array[i] = size - i;
}
return array;
}
double record_time(int* array, int size, void (*fp)(int*, int)) {
clock_t begin = clock();
(*fp)(array, size);
clock_t end = clock();
return (double)(end - begin) / CLOCKS_PER_SEC;
}
void shell_sort(int* array, int size) {
int* h_inc;
int h_size;
h_size = floor(log(size+1)/log(2));
h_inc = malloc(sizeof(int) * h_size);
for(int i=0; i < h_size; i++) {
h_inc[i] = pow(2, i+1) - 1;
}
int i, j, tmp;
for (int r = (h_size - 1); r >= 0; r--) {
int gap = h_inc[r];
for(i = gap; i < size; i++) {
tmp = array[i];
for(j = i; j >= gap && tmp < array[j-gap]; j-=gap) {
array[j] = array[j-gap];
}
array[j] = tmp;
}
}
free(h_inc);
return;
}
int main() {
while(1) {
int size;
int* data;
double time_elapsed;
size = get_input();
if (size <= 0) { break; }
data = build_data(data, size);
time_elapsed = record_time(data, size, shell_sort);
printf("Elapsed time: %f sec\n", time_elapsed);
free(data);
}
return 0;
}
我的输出是:
Please type input size(n): 10000
Elapsed time: 0.001168 sec
Please type input size(n): 50000
Elapsed time: 0.006094 sec
Please type input size(n): 100000
Elapsed time: 0.010946 sec
Please type input size(n): 500000
Elapsed time: 0.054341 sec
Please type input size(n): 1000000
Elapsed time: 0.118640 sec
Please type input size(n): 5000000
Elapsed time: 0.618815 sec
Please type input size(n): 10000000
Elapsed time: 1.332671 sec
我想我们在这里比较的是不同的东西。 运行 一个程序的时间复杂度和时间是不同的。时间复杂度可以简单的表示为asymptotic behavior of running time as input size tends to infinity.
现在你说的是在说跟O(n)
。我猜您正在查看两个输入并考虑时间的乘法增量。您的算法可能在 An^1.5+bn+C
个周期内 运行ning。所以首先你不能比较……完全一样。您可以说随着输入的增加,它会渐近地接近与 n^1.5
.
程序 运行 时间和复杂性之间的直接关联不是您应该寻找的。相反,您可以从程序中完成的基本操作来考虑。
如果你认为我们可以从 运行ning 时间完全考虑时间复杂度,那么我想我们不需要考虑那些基本操作等等。
我不认为逆序是(这个)shell 排序的最坏情况。我把你的代码 运行 放在我的 Mac 上,得到了时间:
Please type input size(n): 10000
Elapsed time: 0.000247 sec
Please type input size(n): 50000
Elapsed time: 0.001314 sec
Please type input size(n): 100000
Elapsed time: 0.002768 sec
Please type input size(n): 500000
Elapsed time: 0.016154 sec
Please type input size(n): 1000000
Elapsed time: 0.033013 sec
Please type input size(n): 5000000
Elapsed time: 0.173584 sec
Please type input size(n): 10000000
Elapsed time: 0.338931 sec
Please type input size(n): 10000000
Elapsed time: 0.344284 sec
Please type input size(n): 10000000
Elapsed time: 0.343052 sec
Please type input size(n): 0
然后我用 rand()
替换了你的 size - i
,并在 main()
的开头添加了 srand(time(0));
:
static int *build_data(int *array, int size)
{
array = malloc(sizeof(int) * size);
for (int i = 0; i < size; i++)
{
array[i] = rand(); //size - i;
}
return array;
}
运行备选方案,我有这样的时间:
Please type input size(n): 10000
Elapsed time: 0.001117 sec
Please type input size(n): 50000
Elapsed time: 0.007097 sec
Please type input size(n): 100000
Elapsed time: 0.015724 sec
Please type input size(n): 500000
Elapsed time: 0.095657 sec
Please type input size(n): 1000000
Elapsed time: 0.191383 sec
Please type input size(n): 5000000
Elapsed time: 1.214821 sec
Please type input size(n): 10000000
Elapsed time: 2.684908 sec
Please type input size(n): 10000000
Elapsed time: 2.716862 sec
Please type input size(n): 10000000
Elapsed time: 2.739099 sec
Please type input size(n): 0
这些时间远远长于反向序号的时间。时间也比线性增长更快——不是那么显着,但肯定更快。而减法和调用之间的区别 rand()
不是问题的根源。我还创建了一个这样的版本:
static int *build_data(int *array, int size)
{
array = malloc(sizeof(int) * size);
unsigned long random_sum = 0;
for (int i = 0; i < size; i++)
{
array[i] = size - i;
random_sum += rand();
}
printf("Random sum: %lu\n", random_sum);
return array;
}
示例输出是:
Please type input size(n): 10000
Random sum: 10730036823932
Elapsed time: 0.000380 sec
Please type input size(n): 50000
Random sum: 53866916004733
Elapsed time: 0.001351 sec
Please type input size(n): 100000
Random sum: 107321572319270
Elapsed time: 0.002879 sec
Please type input size(n): 500000
Random sum: 536869931129596
Elapsed time: 0.015761 sec
Please type input size(n): 1000000
Random sum: 1073512237256859
Elapsed time: 0.034148 sec
Please type input size(n): 5000000
Random sum: 5370226579401372
Elapsed time: 0.170608 sec
Please type input size(n): 10000000
Random sum: 10737805324344696
Elapsed time: 0.357169 sec
Please type input size(n): 10000000
Random sum: 10735216573040655
Elapsed time: 0.350111 sec
Please type input size(n): 10000000
Random sum: 10739807847077051
Elapsed time: 0.349979 sec
Please type input size(n): 0
慢一点,是的;除其他所有内容外,还需要一个额外的 printf()
。但不像 运行dom 数据那么慢。