Слияние k отсортированные связанные списки - анализ
Я думаю о различных решениях для одной проблемы. Предположите, что у нас есть отсортированные связанные списки 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) время. Так, вопрос - сделал меня f%ck где-нибудь или он на самом деле неправильный относительно этого? И если я прав, почему этот подход 'divide&conquer' не может использоваться вместо приоритетного подхода очереди?
4 ответа
Если у вас есть небольшое количество списков для слияния, эта попарная схема, вероятно, будет быстрее, чем метод очереди с приоритетом, потому что у вас очень мало операций на слияние: в основном только одно сравнение и два переназначения указателя для каждого элемента (для перехода на новый отдельный -связанный список). Как вы показали, это O (N log K) ( log K шагов, обрабатывающих N элементов каждый).
Но я считаю, что наилучшими алгоритмами очереди с приоритетом являются O (sqrt (log K)) или O (log log U) для вставки и удаления (где U - количество возможных различных приоритетов) - если вы можете установить приоритеты с помощью значения вместо необходимости использовать сравнение - поэтому, если вы объединяете элементы, которые могут быть заданы, например целочисленные приоритеты, а K велико, тогда вам лучше с очередью с приоритетами.
Это 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 ;
Судя по вашему описанию, ваш процесс действительно O (N log K). Он тоже будет работать, так что вы можете его использовать.
Лично я бы использовал первую версию с приоритетной очередью, так как подозреваю, что она будет быстрее. Это не быстрее в грубом смысле большого О, но я думаю, что если вы действительно определите количество сравнений и сохранений, сделанных обоими, вторая версия потребует в несколько раз больше работы.
Она действительно выполняется за O(N*log K), но не забывайте, что O(N*log K) - это подмножество O(N*K). Т.е. ваш друг тоже не ошибается.