Сложность времени слияния k связанных списков - O (nk log (k))

Question

Я знаю, что есть несколько вопросов относительно этого, но у меня нет решения моего вопроса.

Вопрос прост: слияние k n-length отсортированных связанных списков.

Многие ответы есть, используя очереди приоритета длины к со сложностью O (п LOG (к))

Не знаю, как. Вот ссылка Merging K- Sorted Lists using Priority Queue

Это заставляет меня думать, что я ошибаюсь. Таким образом, мой раствор:

Для слияния двух списков длиной n требуется время O (2n).

1. объединить списки в паре двух ==== K 2 слияния/* 2n раз в слиянии каждой пары влево с к/2, списки 2n длины
2. повторите шаг 1, пока не осталось с 1 массивом размером n * k.

Так что сложность времени будет.

к/2 * 2n = к * п

к/4 * 4n = к * п

.

.

.

к/2^х * 2^х п = к п

последний член будет к * п с 2^х = к или х = лог (к)

так всего журнала (k) итераций с k * n сравнениями на каждой итерации. Таким образом, сложность времени была бы O (k * n * log (k))

Может ли кто-нибудь сказать, где я ошибаюсь?

Спасибо за ваше время.

Answer 1

Если не указано иное, когда сложность алгоритма задается в терминах N, то размер ввода N. Поэтому, когда мы собираем «слияние k связанных списков - это O (N log k)», мы имеем в виду, что N - общее количество элементов во всех списках.

Как вы говорите, слияние k m-length перечисляет O (km log k). Здесь размер ввода - km (общее количество элементов), поэтому это согласуется с приведенным выше утверждением.

Ваше утверждение не так сильно, хотя, поскольку оно охватывает только k списков одинаковой длины. «Объединение k связанных списков - O (N log k)» - это значение независимо от того, как эти N элементов распределяются среди списков.