Пытаясь понять сложность сортировки

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 ² ). Это на самом деле происходит приличное количество на практике.