Какова сложность сортировки сегментов O (n + k), если мы реализуем сегменты, используя связанные списки?

Question

Мне интересно, почему сортировка сегментов имеет время выполнения O (n + k), если мы используем сегменты, реализованные со связанными списками. Например, предположим, что у нас есть этот ввод:

n = no of element= 8
k = range = 3

array = 2,2,1,1,1,3,1,3

Ведра будут выглядеть так:

1: 1 -> 1 -> 1 -> 1
2: 2 -> 2
3: 3 -> 3

Общее время, затраченное на вставку в эти сегменты, равно O (n), при условии, что мы храним указатель хвоста в связанных списках.

Для удаления мы должны перейти к каждому сегменту, а затем удалить каждый узел в этом сегменте. Следовательно, сложность должна быть O (K * средняя длина списка ссылок сегмента), поскольку мы пересекаем каждый связанный список.

Однако я прочитал, что сложность сортировки сегментов равна O (n + k). Почему это не согласуется с моим анализом? Пожалуйста, исправьте меня, поскольку я все еще учусь вычислительной сложности.

Answer 1

Ваш анализ почти правильный, но есть важная деталь, которую вы упускаете.

Прямо сейчас, вы правы, что итерация по входному массиву для распределения элементов по сегментам занимает время O (n). Тем не менее, вы немного не согласны, когда говорите, что общее количество времени, необходимое для сборки массива, равно O (k * (среднее количество элементов в корзине)). Обратите внимание, что, поскольку имеется n элементов и k блоков, это может привести к O (k * (n / k)) = O (n) для общего времени выполнения O (n). Чтобы понять, почему реальный ответ - O (n + k), нам нужно более внимательно посмотреть на этот термин big-O.

Для начала, вы абсолютно правы, что среднее количество времени, которое вы тратите на каждое ведро, составляет O (n / k). Затем вы говорите, что, поскольку имеется k блоков, общее время выполнения составляет O (k * (n / k)) = O (n). Однако это неверно: в частности, не верно, что k * O (n / k) = O (n). Причина этого в том, что термин O (n / k) скрывает постоянный коэффициент. Когда вы посещаете каждое ведро и смотрите на содержащиеся в нем элементы, это не займет ровно n / k времени или даже некоторое постоянное кратное n / k времени. Например, что произойдет, если корзина пуста? В этом случае вы все еще тратите некоторое время на просмотр корзины, поскольку вам необходимо определить, что вам не следует перебирать ее элементы. Таким образом, более точное представление времени, необходимого для каждого сегмента, имеет вид c ₀ (n / k) + c ₁ , где c ₀ и c ₁ - константы, зависящие от реализации. Это выражение, конечно, O (n / k).

Подвох заключается в том, что происходит, когда вы умножаете это выражение на k, чтобы получить общий объем выполненной работы. Если вы вычислили

k * (c ₀ (н / к) + c ₁ )

Вы получаете

c ₀ n + c ₁ k

Как видите, это выражение напрямую зависит от k, поэтому общее время выполнения равно O (n + k).

Более прямой способ получить такой результат - посмотреть код для второго шага сортировки сегментов, который выглядит следующим образом:

For each bucket b:
    For each element x in b:
        Append x to the array.

Сколько работы в целом сделано? Ну, есть k разных сегментов, поэтому внешний цикл должен занять не менее O (k) времени, потому что мы должны смотреть в каждом сегменте. Внутри, внутренний цикл будет выполнен в общей сложности O (n) раз, потому что есть общее количество n элементов, распределенных по сегментам. Отсюда получаем общее время выполнения O (n + k).

Причина, по которой это важно, заключается в том, что если вы попытаетесь выполнить сортировку сегментов с огромным количеством сегментов (скажем, намного больше, чем n), во время выполнения может преобладать время, необходимое для сканирования по всем ведра, которые ищут те места, которые вы фактически использовали, даже если большинство из них пустые. Причина, по которой радикальная сортировка полезна, состоит в том, что она использует несколько итераций сортировки сегментов, где есть только два сегмента, которые выполняются за время O (n + 2) = O (n). Поскольку вам нужно только выполнить O (lg U) итераций этого (где U - максимальное значение в массиве), время выполнения равно O (n lg U) вместо O (n + U), которое вы получите из корзины сортировка, что намного хуже.

Надеюсь, это поможет!