Мой вопрос заключается в решении в leetcode ниже, я не могу понять, почему это O(k+(nk)log(k)).
Дополнение: Может быть, сложность не в том, что на самом деле я не знаю временную сложность heappush() и heappop()
# O(k+(n-k)lgk) time, min-heap
def findKthLargest(self, nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
for _ in xrange(len(nums)-k):
heapq.heappop(heap)
return heapq.heappop(heap)
heapq - двоичная куча, с O (log n) push и O (log n) pop. См. Исходный код heapq.
Выбранный вами алгоритм принимает O (n log n), чтобы выталкивать все элементы в кучу, а затем O ((nk) log n), чтобы найти k-й наибольший элемент. Таким образом, сложностью будет O (n log n). Он также требует O (n) дополнительного пространства.
Вы можете сделать это в O (n log k), используя O (k) дополнительное пространство, слегка изменив алгоритм. Я не программист на Python, поэтому вам придется переводить псевдокод:
create a new min-heap
push the first k nums onto the heap
for the rest of the nums:
if num > heap.peek()
heap.pop()
heap.push(num)
// at this point, the k largest items are on the heap.
// The kth largest is the root:
return heap.pop()
Ключевым моментом здесь является то, что куча содержит только самые большие предметы, которые видели до сих пор. Если элемент меньше, чем k-я наибольшая, увиденная до сих пор, он никогда не кладет на кучу. Наихудший случай - O (n log k).
На самом деле, heapq имеет heapreplace метод, так что вы могли бы заменить это:
if num > heap.peek()
heap.pop()
heap.push(num)
с
if num > heap.peek()
heap.replace(num)
Кроме того, альтернативой нажатию первых элементов k является создание списка первых элементов k и вызов heapify. Более оптимизированный (но еще O (n log k)) алгоритм:
create array of first 'k' items
heap = heapify(array)
for remaining nums
if (num > heap.peek())
heap.replace(num)
return heap.pop()
Вы также можете вызвать heapify на весь массив, затем heapify первые элементы nk, а затем взять верх:
heapify(nums)
for i = 0 to n-k
heapq.heappop(nums)
return heapq.heappop(nums)
Это проще. Не уверен, что это быстрее, чем мое предыдущее предложение, но оно изменяет исходный массив. Сложность - это O (n) для создания кучи, тогда O ((nk) log n) для всплывающих окон. Таким образом, это O ((nk) log n). Худший случай O (n log n).