c - ソートのカウントの複雑さを理解しようとしています

Question

いろいろなことを読んでいます。ソートのカウントの場合、以下のCコードは正常に機能しますが、時間計算量について質問があります。多くの場所で読んでいるように、実際にはO（N）ではありませんが、O（入力配列の最大値-配列の最小値）です。これはNより大きくなる可能性があります。ここで、Nを増やし、同時にmax --minを増やす（範囲-つまり、maxを増やし、minを減らす）と、実行時の複雑さは2次式、つまり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 ² ) になります。これは、実際にはかなりの量で発生します。