0

阅读各种。在计数排序的情况下，下面的 C 代码可以正常工作，但我对它的时间复杂度有疑问。正如我在很多地方读到的那样，它并不是真正的 O(N)，而是 O(输入数组的最大值 - 数组的最小值)。这可以大于 N。现在如果我们增加 N，同时增加 max - min（范围 - 即增加 max 并减少 min），那么运行时复杂度是否可以得到二次，即 O(N 2 ) 或否？或者对于这种排序来说，最坏的情况是输入数组有多个相同值的实例。不是很清楚试图理解。

假设我们已经计算了传递给counting_sort 的给定数组的最小值、最大值。n 是输入数组的长度

void counting_sort_mm(int *array, int n, int min, int max)
{
  int i, j, z;

  int range = max - min + 1;
  int *count = malloc(range * sizeof(*array));

  for(i = 0; i < range; i++) count[i] = 0;
  for(i = 0; i < n; i++) count[ array[i] - min ]++;

  for(i = min, z = 0; i <= max; i++) {
    for(j = 0; j < count[i - min]; j++) {
      array[z++] = i;
    }
  } 

  free(count);
}
4

1 回答 1

0

如果对输入数组中的特定值没有任何进一步的假设，计数排序的运行时间是 O(n + U)，其中 U 是您所指的最大值 - 最小值。除非你有理由相信，否则 n 和 U 的数量是相互独立的。

现在，很有可能，由于特定于您的特定应用程序的原因，数组中的最大值最多为 n 2而最小值为 0，在这种情况下 U = O(n 2 ) . 在这种情况下，计数排序的运行时间确实是 O(n 2 )。这实际上在实践中发生了相当多的事情。

于 2015-08-26T18:41:19.357 回答