azrael

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