c - 尝试理解计数排序的复杂性

Question

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

假设我们已经计算了给定数组的最小值和最大值，并将其传递给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);
}

Answer 1

如果不对输入数组中的特定值进行任何进一步假设，计数排序的运行时间为 O(n + U)，其中 U 是您所说的 max - min 值。数量 n 和 U 彼此独立，除非您有理由不相信。

现在，由于特定应用程序的特定原因，很可能出现数组中的最大值最多为 n² 且最小值为 0 的情况，在这种情况下，U = O(n²)。在这种情况下，计数排序的运行时间确实是 O(n²)。实际上，这种情况在实践中发生过很多次。