2009/12/12 Facundo Batista <facundobatista@???>:
> 2009/12/12 Pablo Mouzo <pablomouzo@???>:
>
>> 2009/12/12 Facundo Batista <facundobatista@???>:
>>>>>> import heapq
>>>>>> heapq.nsmallest(2, [1, 4, 55, 65, 7, 3])
>>> [1, 3]
>>
>> Crear un heap con n elementos no es O(n.log(n))?
>
> No sé.
>
> Habría que analizar el código del mismo.
>
> ¿Vos por qué decís que es O(n.log(n))?
>
> --
> . Facundo
>
Si mal no recuerdo, al insertar un elemento nuevo en un heap, las
operaciones necesarias para que vuelva a quedar con la propiedad del
heap es log(n) (n es la cantidad de elementos que tiene el heap), y si
tenés una lista de n elementos, con los cuales vas a crear un heap
para sacar los más chicos, estás haciendo n veces el reordenamiento
del heap. (Esta parte es la que no estoy seguro) Al final, cuando le
sacas las constantes para llegar a la notacion big-O queda n.log(n).
El heap es genial cuando queres mantener algo, a lo que le insertas y
sacas elementos constantemente, ordenado. Por ejemplo una cola de
mensajes con prioridad. Para todo lo demas existe quicksort :P.
Saludos,
Pablo
---------------------------------------------------------------------
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)