Matias Graña wrote:
> 2009/12/12 Fede Martinez <federicoemartinez@???>:
>> Si N es la cantidad de cosas que tenes, n las que queres sacar:
>>
>> El heap lo podes armar en O(N). Despues sacar el minimo te cuesta O(log(N)),
>> como vas a sacar n veces el minimo, lo que te queda es un O(n*log(N))
>
> Hasta donde entiendo, armar el heap es N.log(N). Pero igual tomar los
> primeros n parece que está bien optimizado:
Armar un heap a partir de un array es O(N). [0]
Tomar el elemento mas chico (si es una min heap) es O(1).
Remover ese elemento (para poder encontrar el siguiente elemento
mínimo) es log(N).
En total, encontrar los m menores elementos entre N elementos será
O(N + m log N).
Según optimizaciones listadas en [1], se puede hacer en O(N log m) u
O(N + m log m).
Y, finalmente, como dice el último caso de [1]. "Si no es necesario
que los m elementos estén ordenados, se puede hacer en O(N), que es
insuperable."
Aunque no lo aclara en los docs de heapq, asumo que no usa el último
algoritmo, pero siendo esto Python, debe haber alguna librería que
lo aplique.
[0]
http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
[1]
http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements
--
Guillermo O. «Tordek» Freschi. Programador, Escritor, Genio Maligno.
http://tordek.com.ar :: http://twitter.com/tordek
http://www.arcanopedia.com.ar - Juegos de Rol en Argentina
---------------------------------------------------------------------
Para dar de baja la suscripcion, mande un mensaje a:
pyar-unsubscribe@???
Para obtener el resto de direcciones-comando, mande un mensaje a:
pyar-help@???
PyAr - Python Argentina - Sitio web:
http://www.python.com.ar/
(text/plain)