Какова сложность сортировки ведер 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), в предположении, что мы храним хвостовой указатель в связанных списках.
Для удаления мы должны перейти к каждому ведру, а затем удалить каждый узел в этом ведре. Следовательно, сложность должна быть O(K * средняя длина связующего списка ведер), так как мы проходим через каждый связующий список.
Однако, я читал, что сложность типа ведра - O(n + k). Почему это не согласуется с моим анализом? Пожалуйста, поправьте меня, так как я все еще учусь вычислительной сложности.
1 ответ
Ваш анализ почти правильный, но есть важная деталь, которую вы упускаете.
Прямо сейчас, вы правы, что итерация по входному массиву для распределения элементов по сегментам занимает время O (n). Тем не менее, вы немного не согласны, когда говорите, что общее количество времени, необходимое для сборки массива, равно O (k * (среднее количество элементов в сегменте) Обратите внимание, что, поскольку имеется n элементов и k блоков, это может привести к O (k * (n / k)) = O (n) для общего времени выполнения O (n). Чтобы понять, почему реальный ответ - O (n + k), нам нужно более внимательно посмотреть на этот термин большого числа.
Для начала, вы абсолютно правы, что среднее количество времени, которое вы тратите на каждое ведро, составляет O (n / k). Затем вы говорите, что, поскольку имеется k блоков, общее время выполнения составляет O (k * (n / k)) = O (n). Однако это неверно: в частности, не верно , что k * O (n / k) = O (n). Причина этого в том, что термин O (n / k) скрывает постоянный коэффициент. Когда вы посещаете каждое ведро и смотрите на содержащиеся в нем элементы, это не займет ровно n / k времени или даже некоторое постоянное кратное n / k времени. Например, что произойдет, если корзина пуста? В этом случае вы все еще тратите некоторое время на просмотр корзины, поскольку вам необходимо определить, что вам не следует перебирать ее элементы. Таким образом, более точное представление времени, требуемого для каждого сегмента, имеет вид c 0 (n / k) + c 1 , где c 0 и c 1 являются константами, зависящими от реализации. Это выражение, конечно, O (n / k).
Подвох состоит в том, что происходит, когда вы умножаете это выражение на k, чтобы получить общий объем выполненной работы. Если вы вычислите
k * (c 0 (n / k) + c 1 )
Вы получите
c 0 n + c 1 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), которое вы получите из корзины сортировка, что намного хуже.
Надеюсь, это поможет!