Análisis del ordenamiento rápido

¿Cómo es que el tiempo de ejecución del peor caso y del caso promedio del ordenamiento rápido difieren? Vamos a empezar por ver el tiempo de ejecución del peor caso. Supón que en realidad somos muy desafortunados y que los tamaños de las particiones están muy desbalanceados. En particular, supón que el pivote escogido por la función partition siempre es el elemento más pequeño o el más grande en el subarreglo de $n$‍ elementos. Entonces una de las particiones no va a contener elementos y la otra partición contendrá $n-1$‍ elementos (todos menos el pivote). Así que las llamadas recursivas serán sobre subarreglos de tamaños 0 y $n-1$‍.

Como en el ordenamiento por mezcla, el tiempo para una llamada recursiva dada en un subarreglo de $n$‍ elementos es $\mathrm{\Theta }(n)$‍. En el ordenamiento por mezcla, ese era el tiempo para mezclar, pero en el ordenamiento rápido es el tiempo para hacer las particiones.

Cuando el ordenamiento rápido siempre tiene las particiones más desbalanceadas posibles, entonces la llamada original tarda un tiempo $cn$‍ para alguna constante $c$‍, la llamada recursiva sobre $n-1$‍ elementos tarda un tiempo $c(n-1)$‍, la llamada recursiva sobre $n-2$‍ elementos tarda un tiempo $c(n-2)$‍, y así sucesivamente. Aquí está un árbol de los tamaños de los subproblemas con sus tiempos para hacer las particiones:

Cuando sumamos los tiempos para hacer las particiones para cada nivel, obtenemos

La última línea es porque $1+2+3+\cdots +n$‍ es la serie aritmética, como vimos cuando analizamos el ordenamiento por selección. (Le restamos 1 porque para el ordenamiento rápido, la suma empieza en 2, no en 1). Tenemos algunos términos de orden inferior y coeficientes constantes, pero los ignoramos cuando usamos notación Θ grande. En notación Θ grande, el tiempo de ejecución del peor caso del ordenamiento rápido es $\mathrm{\Theta }(n^2)$‍.

El mejor caso del ordenamiento rápido ocurre cuando las particiones están balanceadas tan uniformemente como sea posible: sus tamaños son iguales o difieren en 1. El primer caso ocurre si el subarreglo tiene un número impar de elementos, el pivote está justo en medio después de hacer la partición y cada partición tiene $(n-1)/2$‍ elementos. El otro caso ocurre si el subarreglo tiene un número par $n$‍ de elementos y una partición tiene $n/2$‍ elementos mientras que la otra tiene $n/2-1$‍. En cualquiera de estos casos, cada partición tiene a lo más $n/2$‍ elementos, y el árbol de los tamaños de los subproblemas se parece mucho al árbol de los tamaños de los subproblemas para el ordenamiento por mezcla, con los tiempos para hacer las particiones que se ven como los tiempos de mezcla:

Al usar notación Θ grande, obtenemos el mismo resultado que para un ordenamiento por mezcla: $\mathrm{\Theta }(n{\log }_{2}n)$‍.

Mostrar que el tiempo de ejecución del caso promedio también es $\mathrm{\Theta }(n{\log }_{2}n)$‍ requiere unas matemáticas bastante complicadas, así que no lo vamos a hacer. Pero podemos obtener un poco de intuición al ver un par de otros casos para entender por qué podría ser $O(n{\log }_{2}n)$‍ (una vez que tengamos $O(n{\log }_{2}n)$‍, la cota de $\mathrm{\Theta }(n{\log }_{2}n)$‍ se sigue porque el tiempo de ejecución del caso promedio no puede ser mejor que el tiempo de ejecución del mejor caso). Primero, imaginemos que no siempre obtenemos particiones igualmente balanceadas, pero que siempre obtenemos una razón de 3 a 1. Es decir, imagina que cada vez que hacemos una partición, un lado obtiene $3n/4$‍ elementos y el otro lado obtiene $n/4$‍ (para mantener limpias las matemáticas, no vamos a preocuparnos por el pivote). Entonces, el árbol de los tamaños de los subproblemas y los tiempos para hacer las particiones se vería así:

El hijo izquierdo de cada nodo representa un subproblema cuyo tamaño es un 1/4 del tamaño del padre, y el hijo derecho representa un subproblema cuyo tamaño es 3/4 del tamaño del padre. Como los subproblemas más pequeños están del lado izquierdo, al seguir el camino de hijos izquierdos llegamos de la raíz hasta un problema de tamaño 1 más rápido que por cualquier otro camino. Como se muestra en la figura, después de ${\log }_{4}n$‍ niveles, llegamos a un subproblema de tamaño 1. ¿Por qué ${\log }_{4}n$‍ niveles? Podría ser más fácil pensar en términos de empezar con un subproblema de tamaño 1 y multiplicarlo por 4 hasta llegar a $n$‍. En otras palabras, estamos preguntando: ¿para qué valor de $x$‍ se cumple que $4^x=n$‍? La respuesta es ${\log }_{4}n$‍. ¿Qué pasa si vamos por un camino de hijos derechos? La figura muestra que se necesitan ${\log }_{4/3}n$‍ niveles para llegar a un subproblema de tamaño 1. ¿Por qué ${\log }_{4/3}n$‍ niveles? Como el tamaño de cada hijo derecho es 3/4 del tamaño del nodo arriba de él (su nodo padre), el tamaño de cada padre es 4/3 el tamaño de su hijo derecho. Volvamos a pensar en empezar con un subproblema de tamaño 1 y multiplicar su tamaño por 4/3 hasta llegar a $n$‍. ¿Para qué valor de $x$‍ se cumple que $(4/3{)}^x=n$‍? La respuesta es ${\log }_{4/3}n$‍.

En cada uno de los primeros ${\log }_{4}n$‍ niveles hay $n$‍ nodos (de nuevo, incluyendo pivotes que en realidad ya no se están particionando), así que el tiempo total de hacer particiones para cada uno de estos niveles es de $cn$‍. ¿Qué pasa con el resto de los niveles? Cada uno tiene menos de n nodos, así que el tiempo para hacer particiones para cada nivel es a lo más $cn$‍. Todo junto, hay ${\log }_{4/3}n$‍ niveles, así que el tiermpo total para hacer particiones es $O(n{\log }_{4/3}n)$‍. Ahora, hay un hecho matenático que dice que

para todos los números positivos $a$‍, $b$‍ y $n$‍. Al hacer $a=4/3$‍ y $b=2$‍, obtenemos que

así que ${\log }_{4/3}n$‍ y ${\log }_{2}n$‍ solo difieren por un factor de ${\log }_2(4/3)$‍, que es una constante. Como los factores constantes no importan cuando usamos la notación O grande, podemos decir que si todas las divisiones tienen una razón de 3 a 1, entonces el tiempo de ejecución del ordenamiento rápido es $O(n{\log }_{2}n)$‍, aunque con un factor constante más grande escondido que el tiempo de ejecución del mejor caso.

¿Qué tan seguido esperaríamos ver una razón de divisiones que sea 3 a 1 o mejor? Depende de cómo escojamos el pivote. Imaginemos que el pivote es igualmente probable de acabar en cualquier lado en un subarreglo de $n$‍ elementos después de hacer las particiones. Para obtener una división que tenga una razón de 3 a 1 o mejor, el pivote debería estar en algún lado en "la mitad de en medio":

Así que si el pivotes es igualmente probable de acabar en cualquier lado en el subarreglo después de hacer las particiones, hay una probabilidad del 50% de obtener una división de 3 a 1 en el peor de los casos. En otras palabras, esperamos tener una división de 3 a 1 o mejor alrededor de la mitad del tiempo.

El otro caso que vamos a ver para entender por qué el tiempo de ejecución del caso promedio del ordenamiento rápido es $O(n{\log }_{2}n)$‍, es qué pasaría si en la mitad de veces que no obtenemos una división de 3 a 1, obtenemos el peor caso de la división. Vamos a suponer que las divisiones de 3 a 1 y del peor caso alternan, y piensa en un nodo en el árbol con $k$‍ elementos en su subarreglo. Entonces veríamos una parte del árbol como esta:

en vez de así:

Por lo tanto, incluso si la mitad de las veces tuviéramos el peor caso de la división y la otra mitad una división de 3 a 1, el tiempo de ejecución sería alrededor del doble del tiempo de ejecución de siempre obtener una división de 3 a 1. De nuevo, eso es solo un factor constante y se absorbe en la notación O grande. Así que en este caso, en donde se alterna entre el peor caso para las divisiones y el caso de 3 a 1, el tiempo de ejecución es $O(n{\log }_{2}n)$‍.

Ten en cuenta que este análisis no es matemáticamente riguroso, pero te da una idea intuitiva de por qué el tiempo de ejecución del caso promedio podría ser $O(n{\log }_{2}n)$‍.

Supón que tu peor enemigo te da un arreglo para ordenarlo con el ordenamiento rápido. Sabe que siempre escoges el elemento de hasta la derecha en cada subarreglo como el pivote y acomodó el arreglo de modo que siempre obtengas el peor caso de la división. ¿Cómo puedes frustrar a tu enemigo?

Podrías no necesariamente escoger el elemento de hasta al derecha en cada subarreglo como el pivote. En lugar de eso, podrías escoger un elemento en el subarreglo de manera aleatoria y usar ese elemento como el pivote. Pero espera, la función partition supone que el pivote está en la posición de hasta la derecha del subarreglo. No hay problema, solo intercambia el elemento que escojas como el pivote con el elemento de hasta la derecha, y después haz la partición como antes. A menos que tu enemigo sepa cómo escoges ubicaciones aleatorias en el subarreglo, ¡tú ganas!

De hecho, con un poco más de esfuerzo, puedes mejorar tu probabilidad de obtener una división que sea, en el peor de los casos, de 3 a 1. Escoge de manera aleatoria no uno, sino tres elementos del subarreglo, y toma la mediana de los tres como el pivote (al intercambiarlo por el elemento de hasta la derecha). Por la mediana, queremos decir el elemento de los tres cuyo valor esté en medio. No te vamos a mostrar por qué, pero si escoges la mediana de tres elementos elegidos de manera aleatoria como el pivote, tienes una probabilidad de 68.75% (11/16) de obtener una división de 3 a 1 o mejor. Incluso puedes ir más allá. Si escoges cinco elementos de manera aleatoria y tomas la mediana como el pivote, tu probabilidad para un peor caso de 3 a 1 mejora a alrededor de 79.3% (203/256). Si tomas la mediana de siete elementos elegidos de manera aleatoria, sube hasta alrededor de 85.9% (1759/2048). ¿Mediana de nueve? Alrededor de 90.2% (59123/65536). ¿Mediana de 11? Alrededor de 93.1% (488293/524288). Entiendes la idea. Por supuesto, no necesariamente funciona mejor escoger un número grande de elementos de manera aleatoria y tomar su mediana, pues el tiempo que se tarda en hacerlo podría contrarrestar el beneficio de obtener buenas divisiones casi todo el tiempo.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.