Cualquier libro de texto decente sobre algoritmos explicará lo rápidos que son los algoritmos de ordenación como el quicksort y el heapsort, pero no hace falta hacer una locura matemática para demostrar que son tan asintóticamente rápidos como sea posible.
Una nota pedante sobre la notación
La mayoría de los informáticos utilizan la notación big-O para significar «asintóticamente igual, hasta un factor de escala constante», que no es exactamente lo que significa para otros matemáticos. Lo siento, usaré big-O como en los libros de texto de CS, pero al menos no lo mezclaré con otra notación matemática.
Ordenación basada en la comparación
Veamos el caso especial de los algoritmos que comparan valores de dos en dos (como quicksort y heapsort, y la mayoría de otros algoritmos populares). Las ideas pueden extenderse a todos los algoritmos de ordenación más adelante.
Un simple argumento de recuento para el peor caso
Suponga que tiene un array de cuatro elementos, todos diferentes, en orden aleatorio. ¿Puedes ordenarlo comparando sólo un par de elementos? Obviamente no, pero aquí hay una buena razón que demuestra que no se puede: por definición, para ordenar la matriz, se necesita cómo reorganizar los elementos para ponerlos en orden. En otras palabras, necesitas saber qué permutación se necesita. ¿Cuántas permutaciones posibles hay? El primer elemento puede moverse a uno de los cuatro lugares, el segundo puede ir a uno de los tres restantes, el tercer elemento tiene dos opciones y el último tiene que ocupar el único lugar restante. Así que hay 4×3×2×1=4!=244 \Nveces 3 \Nveces 2 \Nveces 1 = 4! = 24 permutaciones posibles entre las que elegir, pero sólo hay dos resultados posibles al comparar dos cosas diferentes: «MAYOR» y «MENOR». Si hicieras una lista de todas las permutaciones posibles, podrías decidir que «MAYOR» significa que necesitas la permutación nº 8 y «MENOR» significa que necesitas la permutación nº 24, pero no hay forma de saber cuándo necesitas las otras 22 permutaciones.
Con dos comparaciones, tienes 2×2=42 \Nveces 2 = 4 resultados posibles, lo que sigue sin ser suficiente. No puedes ordenar todas las posibles matrices barajadas a menos que hagas al menos cinco comparaciones (25=322^5 = 32). Si W(N)W(N) es el peor número de comparaciones necesarias para ordenar NN elementos diferentes utilizando algún algoritmo, podemos decir
2W(N)≥N!2^{W(N)} \geq N!
Tomando un logaritmo base 2,
W(N)≥log2N!W(N) \geq \log_2{N!}
Asintóticamente, N!N! crece como NNN^N (ver también la fórmula de Stirling), por lo que
W(N)⪰logNN=NlogNW(N) \succeq \log{N^N} = N\log{N}
Y eso es un límite O(NlogN)O(N\log N) en el peor de los casos sólo de contar salidas.
Caso medio de la teoría de la información
Podemos obtener un resultado más fuerte si extendemos ese argumento de conteo con un poco de teoría de la información. He aquí cómo podríamos utilizar un algoritmo de ordenación como código para transmitir información:
- Pienso en un número – digamos, 15
- Busco la permutación #15 de la lista de permutaciones de cuatro elementos
- Ejecuto el algoritmo de ordenación en esta permutación y registro todos los resultados de la comparación «MAYOR» y «MENOR»
- Te transmito los resultados de la comparación en código binario
- Realizas mi ejecución del algoritmo de ordenación, paso a paso, refiriéndote a mi lista de resultados de la comparación según sea necesario
- Ahora que sabes cómo he reorganizado mi matriz para ordenarla, puedes invertir la permutación para averiguar mi matriz original
- Buscas mi matriz original en la lista de permutación para averiguar que he transmitido el número 15
Bien, es un poco extraño, pero se puede hacer. Eso significa que los algoritmos de ordenación están limitados por las mismas leyes que los esquemas de codificación normales, incluyendo el teorema que demuestra que no hay un compresor de datos universal. Transmití un bit por cada comparación que hace el algoritmo, así que, en promedio, el número de comparaciones debe ser al menos el número de bits necesarios para representar mis datos, según la teoría de la información. Más técnicamente, el número medio de comparaciones debe ser al menos la entropía de Shannon de mis datos de entrada, medida en bits. La entropía es una medida matemática del contenido de información, o la imprevisibilidad, de algo.
Si tengo una matriz de elementos NN que podría estar en cualquier orden posible sin sesgo, entonces la entropía es maximizada y eslog2N!\Nlog_2{N!} bits. Eso demuestra que O(NlogN)O(N\log{N}) es un promedio óptimo para una ordenación basada en la comparación con una entrada arbitraria.
Esa es la teoría, pero ¿cómo se comparan los algoritmos de ordenación reales? A continuación se muestra un gráfico del número medio de comparaciones necesarias para ordenar una matriz. He comparado el óptimo teórico con el quicksort ingenuo y con la ordenación por inserción y fusión de Ford-Johnson, que se diseñó para minimizar las comparaciones (aunque rara vez es más rápido que el quicksort en general, porque hay más cosas en la vida que minimizar las comparaciones). Desde que se desarrolló en 1959, la ordenación por inserción se ha ajustado para reducir algunas comparaciones más, pero el gráfico muestra que ya es casi óptima.
Es agradable cuando un poco de teoría da un resultado práctico tan ajustado.
Resumen hasta ahora
Esto es lo que se ha probado hasta ahora:
- Si el array puede empezar en cualquier orden, se necesitan al menos O(NlogN)O(N\log{N}) comparaciones en el peor caso
- El número medio de comparaciones debe ser al menos la entropía del array, que es O(NlogN)O(N\log{N}) para una entrada aleatoria
Nota que #2 permite que los algoritmos de ordenación basados en comparaciones sean más rápidos que O(NlogN)O(N\log{N}) si la entrada es de baja entropía (en otras palabras, más predecible). La ordenación por fusión es cercana a O(N)O(N) si la entrada contiene muchas submatrices ordenadas. La ordenación por inserción se aproxima a O(N)O(N) si la entrada es una matriz ordenada antes de ser perturbada un poco. Ninguno de ellos superaO(NlogN)O(N\log{N}) en el peor de los casos, a menos que algunas ordenaciones de matrices sean imposibles como entradas.
Algoritmos generales de ordenación
Las ordenaciones basadas en la comparación son un caso especial interesante en la práctica, pero no hay nada teóricamente especial enCMP frente a cualquier otra instrucción en un ordenador. Ambos argumentos anteriores pueden generalizarse a cualquier algoritmo de ordenación si se observan un par de cosas:
- La mayoría de las instrucciones de ordenador tienen más de dos salidas posibles, pero siguen teniendo un número limitado
- El número limitado de salidas significa que una instrucción sólo puede procesar una cantidad limitada de entropía
Eso nos da el mismo límite inferior O(NlogN)O(N\log{N}) en el número de instrucciones. Cualquier ordenador físicamente realizable sólo puede procesar un número limitado de instrucciones a la vez, por lo que es un límite inferior O(NlogN)O(N\log{N}) en el tiempo requerido, también.
¿Pero qué pasa con los algoritmos «más rápidos»?
La implicación práctica más útil del límite general O(NlogN)O(N\log{N} es que si se oye hablar de cualquier algoritmo asintóticamente más rápido, se sabe que debe estar «engañando» de alguna manera. Debe haber alguna trampa que significa que no es un algoritmo de ordenación de propósito general que escala a matrices arbitrariamente grandes. Todavía puede ser un algoritmo útil, pero es una buena idea leer la letra pequeña de cerca.
Un ejemplo bien conocido es la ordenación radix. A menudo se le llama un algoritmo de ordenación O(N)O(N), pero el problema es que sólo funciona si todos los números caben en kk bits, y en realidad es O(kN)O(kN).
¿Qué significa eso en la práctica? Supongamos que tienes una máquina de 8 bits. Puedes representar 28=2562^8 = 256 números diferentes en 8 bits, así que si tienes una matriz de miles de números, vas a tener duplicados. Eso puede estar bien para algunas aplicaciones, pero para otras hay que pasar a por lo menos 16 bits, que pueden representar 216=65.5362^16 = 65.536 números distintos. Los 32 bits soportarán 232=4.294.967.2962^32 = 4.294.967.296 números diferentes. A medida que aumenta el tamaño de la matriz, el número de bits necesarios tiende a aumentar también. Para representar NN números diferentes de forma distinta, necesitará k≥log2Nk \\Ngeq \log_2{N}. Así que, a menos que usted está bien con un montón de duplicados en su matriz, O(kN)O(kN) es efectivamente O(NlogN)O(N\log{N}).
La necesidad de O(NlogN)O(N\log{N}) de los datos de entrada en el caso general en realidad demuestra el resultado global por sí mismo. Ese argumento no es tan interesante en la práctica porque rara vez necesitamos ordenar miles de millones de enteros en una máquina de 32 bits, y si alguien ha llegado a los límites de una máquina de 64 bits, no nos lo ha dicho al resto.