¿Cuál es la complejidad temporal de las funciones en la biblioteca heapq?

Mi pregunta es de la solución en el código de código de abajo, no puedo entender por qué es O(k+(nk)log(k)) .

Suplemento: tal vez la complejidad no sea que, de hecho, no conozco la complejidad del tiempo de heappush() y heappop()

 # O(k+(nk)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 es un montón binario, con O (log n) push y O (log n) pop . Ver el código fuente de heapq .

El algoritmo que muestra toma O (n log n) para insertar todos los elementos en el montón, y luego O ((nk) log n) para encontrar el kth elemento más grande. Entonces la complejidad sería O (n log n). También requiere O (n) espacio extra.

Puede hacer esto en O (n log k), utilizando O (k) espacio adicional modificando ligeramente el algoritmo. No soy un progtwigdor de Python, así que tendrás que traducir el pseudocódigo:

 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() 

La clave aquí es que el montón contiene solo los elementos más grandes vistos hasta ahora. Si un elemento es más pequeño que el kth más grande visto hasta ahora, nunca se coloca en el montón. El peor de los casos es O (n log k).

En realidad, heapq tiene un método de heapreplace , por lo que podría reemplazar esto:

  if num > heap.peek() heap.pop() heap.push(num) 

con

  if num > heap.peek() heap.replace(num) 

Además, una alternativa a empujar los primeros k elementos es crear una lista de los primeros k elementos y llamar a heapify . Un algoritmo más optimizado (pero todavía O (n log k)) es:

 create array of first `k` items heap = heapify(array) for remaining nums if (num > heap.peek()) heap.replace(num) return heap.pop() 

También puede llamar a heapify en toda la matriz, luego heapify los primeros elementos nk y luego tomar la parte superior:

 heapify(nums) for i = 0 to nk heapq.heappop(nums) return heapq.heappop(nums) 

Eso es más simple. No estoy seguro si es más rápido que mi sugerencia anterior, pero modifica la matriz original. La complejidad es O (n) para generar el montón, luego O ((nk) log n) para los pops. Entonces es O ((nk) log n). Peor caso O (n log n).