Слияние k отсортированных связанных списков - анализ

Question

Я думаю о разных решениях для одной проблемы. Предположим, у нас есть K отсортированных связанных списков, и мы объединяем их в один. Все эти списки вместе имеют N элементов.

Хорошо известным решением является использование очереди приоритетов и выталкивание / отправка первых элементов из каждого списка, и я могу понять, почему это занимает O(N log K) время.

Но давайте посмотрим на другой подход. Предположим, у нас есть некоторая процедура MERGE_LISTS(LIST1, LIST2), которая объединяет два отсортированных списка, и это займет O(T1 + T2) время, где T1 и T2 означают LIST1 и LIST2 размеры.

То, что мы делаем сейчас, обычно означает объединение этих списков и объединение их попарно (если число нечетное, последний список, например, можно игнорировать на первых шагах). Обычно это означает, что мы должны создать следующее «дерево» операций слияния:

N1, N2, N3... обозначает LIST1, LIST2, LIST3 размеры

• O(N1 + N2) + O(N3 + N4) + O(N5 + N6) + ...
• O(N1 + N2 + N3 + N4) + O(N5 + N6 + N7 + N8) + ...
• O(N1 + N2 + N3 + N4 + .... + NK)

Кажется очевидным, что будет log(K) этих строк, каждая из которых реализует O(N) операций, поэтому время для операции MERGE(LIST1, LIST2, ... , LISTK) будет фактически равно O(N log K).

Мой друг сказал мне (два дня назад), что это займет O(K N) время. Итак, вопрос - я где-то нашелся или он на самом деле не прав? И если я прав, почему этот подход «разделяй и властвуй» нельзя использовать вместо подхода с приоритетной очередью?

Answer 1

Если у вас есть небольшое количество списков для объединения, эта парная схема, вероятно, будет быстрее, чем метод очереди с приоритетами, потому что у вас очень мало операций на объединение: в основном только одно сравнение и две переназначения указателя на элемент (чтобы перейти вновый односвязный список).Как вы показали, это O(N log K) (log K шагов по обработке N элементов каждый).

Но наилучшие алгоритмы очереди приоритетов, я полагаю, O(sqrt(log K)) или O(log log U) для вставкии удалите (где U - количество возможных различных приоритетов) - если вы можете установить приоритет со значением вместо необходимости использовать сравнение - так, если вы объединяете элементы, которым можно дать, например, целочисленные приоритеты, и K чем больше, тем лучше с приоритетной очередью.

Answer 2

Из вашего описания это звучит так, будто ваш процесс действительно O (N log K). Это также будет работать, так что вы можете использовать его.

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

Answer 3

Это O(2*log(K)*N), это O(N*log(K)), и вы не можете иметь худшую сложность, потому что вы только 2N раз добавляете в очередь приоритетов в O(log(K)).

Или вы можете вставить все элементы в вектор в O(2N). И сортируйте это в O(2n*log(2n)). Тогда у вас есть O(2N+2N*Log(2N)), это O(N*LOG(N)), точно ваш K = N;

Answer 4

Это действительно работает в O(N*log K), но не забывайте, что O(N*log K) является подмножеством O(N*K). То есть твой друг тоже не ошибается.