1

我是 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
4

2 回答 2

1

我想我们在这里比较不同的东西。运行程序的时间复杂度和时间是不同的。时间复杂度可以简单的说为asymptotic behavior of running time as input size tends to infinity.

现在你说它在说它正在跟随O(n)。我猜您正在查看两个输入并考虑时间的乘法增量。您的算法可能An^1.5+bn+C循环运行。所以首先你不能比较......确切地说。您可以说随着输入的增加，它会渐近地接近与 成比例的函数n^1.5。

程序运行时间和复杂性之间的直接关联不是您应该寻找的。相反，您可以从程序中完成的基本操作中考虑。

如果您认为我们可以完全从运行时间考虑时间复杂度，那么我想我们不必考虑那些基本操作等等。

于 2017-10-26T05:30:01.807 回答
0

我不认为反向顺序是（这个）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

然后我将您的替换size - i为rand()，并添加srand(time(0));到main()：

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()除了其他所有内容之外，还有一个额外的要求。但不像随机数据那样慢得多。

于 2017-10-26T06:36:28.043 回答