Más sobre la cota log(n!).
A la hora de añadir un elemento a un vector ordenado, es evidente que el coste óptimo es log(n) -mediante busqueda binaria-.
El error que se comete es creer que hacer esto mismo con varios elementos nos lleva necesariamente a algo proporcional.
Para añadir n elementos a un vector ordenado (o lo que es lo mismo, ordenar n elementos), parece que el coste vaya a ser n log n en el peor caso. Sin embargo esto tan sólo es cierto si no tenemos en cuenta las realciones entre los elementos. Por lo tanto n log n sólo es cota para el peor caso de un algoritmo de ordenación óptimo.
Para ilustrar esto comparemos la búsqueda binaria con los algoritmos anteriores.
BusquedaBinaria(estable)
4 6 0 0 0 5 6 0 7 0 7 8 2 7 8 0
4<=6 comps=1
0<=4<=6 comps=2
0<=0<=4<=6 comps=4
0<=0<=0<=4<=6 comps=6
0<=0<=0<=4<=5<=6 comps=9
0<=0<=0<=4<=5<=6<=6 comps=12
0<=0<=0<=0<=4<=5<=6<=6 comps=15
0<=0<=0<=0<=4<=5<=6<=6<=7 comps=19
0<=0<=0<=0<=0<=4<=5<=6<=6<=7 comps=23
0<=0<=0<=0<=0<=4<=5<=6<=6<=7<=7 comps=27
0<=0<=0<=0<=0<=4<=5<=6<=6<=7<=7<=8 comps=31
0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=8 comps=35
0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8 comps=39
0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8<=8 comps=43
0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8<=8 comps=47
June 1st, 2007 at 15:46
puntualizo: “A la hora de añadir un elemento a un vector ordenado, es evidente que el coste óptimo es log(n)”
no! ese coste es el de buscar la posición de inserción, luego hay que “hacer hueco” en el vector para añadir el elemento y eso tiene coste lineal en el caso peor
June 2nd, 2007 at 17:25
Tienes razón, me refería al coste de la busqueda en comparaciones, el otro depende de la estructura de datos utilizada. Vamos, creo :P.
A lo que me refiero es en realidad más bien un árbol binario de búsqueda.
¿Estás de acuerdo en que el coste promedio de un algoritmo de ordenación óptimo pudiera ser ligeramente inferior a n log n?
Y esta es más complicada ¿Se te ocurre como hallar un algoritmo de ordenación óptimo en el numero de comparaciones?
P.D.: Pese a alguna inexactitud, lo que quería en este post, es demostrar que “viendo todo el vector” se puede ordenar más rápido que “viendo los elementos uno por uno”.
June 2nd, 2007 at 21:27
no investigo en algoritmia, pero no creo que se pueda bajar el coste promedio de ordenación más abajo de nlogn; y sobre lo de algoritmo óptimo en nº de comparaciones, la verdad es que no recuerdo si hay muchas diferencias con el nº de movimientos, pero no lo creo
June 9th, 2007 at 19:59
Gracias por responder. A ver si consigo algo tangible.
De momento estoy convencido de que lo más rápido que se puede hacer es parecido a “ordenar mínimos”, “ordenar máximos”, repetir con el resto y mezclar. El problema es que un merge ahí suele hacer más comparaciones de las necesarias, y que para que sea óptimo de verdad ha de ordenar un vector en el que el único elemento desordenado sea el último en n-1+log(n-2) y no en n-1 + n-2.
Le estoy dando vueltas a algoritmos en los que se comparen de forma recurrente los terminos medios entre máximos y minimos puntuales.