Algoritmos de ordenación (2).
Tirado en la cama este mediodía, me ha parecido dar con la “chispa” del n log n.
El árbol binario de n hojas tiene 1/2(n^2-n) nodos y una altura log n.
El árbol binario de n hojas tiene n-1 nodos y una altura log n-1. (No estaba pensando en árboles binarios sino en combinaciones.)
Por lo tanto un algoritmo de ordenación tendría complejidad log n si hiciera en cada iteración las comparaciones correspondientes a todo un nivel del árbol. Pero el numero de comparaciones en cada nivel del árbol depende de n.
Podríamos pensar que entonces la complejidad será de orden n log n… pero hay algo que no me cuadra. No tengo la cabeza para pensar, pero ¿la complejidad no sería 1/2(n^2-n) log n ? xD
April 14th, 2007 at 19:01
Me parece por lo que recuerdo que la altura de un arbol es un numero entero.
April 16th, 2007 at 15:46
Claro que sí, pero se calcula con log n.
Se agradece que le heches un vistazo, Alberto.