Я пытаюсь понять временную сложность k-way слияния, используя кучу, и, хотя на ней имеется множество литературы, я не могу найти такую, которая разбивает анализ так, чтобы я мог понять .
В этой статье Википедии утверждается, что "на этапе предварительной обработки O (k) куча создается с использованием стандартной процедуры heapify". Тем не менее, вставка кучи составляет O(log(n)), а время поиска - O(1). Мы начнем с вставки первых элементов каждого массива в кучу. Это займет ∑log(i) время,
i = 0 to k - 1 или O(klog(k)) время, которое опровергает анализ сложности Википедии. (на самом деле O(log(k!)))
Затем мы удаляем элемент min и вставляем следующий элемент из массива.
откуда изначально появился элемент min. Это займет O(1) + O(log(k)) время, которое мы повторяем n - 1 раз.
Общее время:
O(klog(k)) + O(n - 1) + O((n - 1)log(k)) ≅ O(klog(k)) + O(n) + O(nlog(k))
Википедия утверждает: "общее время работы O (n log k)". Как это?