Какова временная сложность heapq.merge в python?

Question

Я читал, что функция heapq.merge специально используется для объединения 2 отсортированных массивов? такое сложность времени O(n)? если нет то что это и почему? И в чем его сложность.

Я решал вопрос слияния 2 отсортированных массивов с 2 указателями и мог достичь O (n) временной сложности и O (n) пространственной сложности.

Answer 1

Если вы объединяете K отсортированных массивов, и каждый массив имеет N элементов, тогда heapq.merge выполнит операцию с временной сложностью NK(logK). Потому что NK — это общее количество элементов во всех K массивах, и каждый элемент необходимо сравнивать. В то время как logK — это временная сложность операций пузырькового спуска с вершины кучи (то есть высоты кучи).

В вашем случае K =2, log(2) = 1. Так что в вашем особом случае это O(n)

Answer 2

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

Космическая сложность O(K) потому что в минхипе K предметы в любой момент времени во время выполнения.