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是您所指的最大值。除非您有理由相信其他情况，否则数量n和U是相互独立的。

现在，很有可能，由于特定应用程序的原因，数组中的最大值最多为n²，最小值为0，在这种情况下，U=O（n²）。在这种情况下，计数排序的运行时间实际上是O（n²）。实际上，这种情况在实践中相当多。