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

Мне интересно, почему сортировка ведра имеет время выполнения 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), предполагая, что мы храним указатель на хвост в связанных списках.

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

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

Ответ 1

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

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

Для начала вы абсолютно правы, что среднее количество времени, которое вы тратите на каждое ведро, равно O (n/k). Затем вы говорите, что, поскольку есть k ведер, общая продолжительность выполнения равна O (k * (n/k)) = O (n). Однако это неверно: в частности, это не true, что 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 ₀ (n/k) + 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), в среде выполнения может быть указано время, необходимое для сканирования по всем ведра, которые ищут ведра, которые вы фактически использовали, даже если большинство из них пустые. Причина, по которой используется сортировка radix, заключается в том, что она использует несколько итераций сортировки ведра, где есть только два ведра, которые выполняются во времени O (n + 2) = O (n). Поскольку вам нужно только выполнить O (lg U) итерации этого (где U - максимальное значение в массиве), время выполнения - O (n lg U) вместо O (n + U), которое вы получите из ведра сортировать, что намного хуже.

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