El peor caso de un algoritmo superadaptativo, será cuando nos encontremos la ordenación mínima en el vector de n datos, y en los sucesores vectores que analice el algoritmo, es decir, estos dos casos:
A<=B>C<=D>E<=F o A>B<=C>D<=E>F
A<=C>E y B<=D>F o A>C<=E y B>D<=F
A<=E y B<=F o A>E y B>F
A<=E<=C<= B<=F<=D o D<=F<=B<=C<=E<=A
Si esto es de verdad así, yo lo llamaría acordeón :P.
La cota log(n!) (O (n log(n))), es la cota inferior (y superior) de un algoritmo de ordenación por comparación óptimo no adaptativo.
Sin embargo es la cota superior de un algoritmo de ordenación por comparación óptimo adaptativo.
La cota inferior de un algoritmo adaptativo es O(n).
Por lo tanto el coste de un algoritmo adaptativo óptimo se situará entre O(n) y O(n log n).
Para comprobar si mis hipótesis son correctas, estoy trabajando en un algoritmo recursivamente adaptativo. Puede que no sea practico, entre otras cosas por no tener muy en cuenta el modelo de cachés, pero seguro que será interesante (según creo el coste medio estará rozando el n log n, pero por debajo ;).
Si en Quicksort se usara la comparacion “<=”, para los datos de antes de la posicion de pivote, y “<” para los datos de despues del pivote, el algoritmos sería estable, y posiblemente mejoraría su rendimiento en situaciones de repetición de claves.
EDIT: La respuesta dos post más adelante “Ejemplo superadaptativo”, el quicksort estable pierde rendimiento.
Hoy me pasaba algo rarísimo, en una practica de algoritmos de ordenación, al utilizar quicksort en su caso medio el coste era
n log n, en el peor (para un vector ordenado) cuadrático, pero con vectores MUY grandes, ambos costes convergían.
Garantizo que nada en el código estaba mal, y ha sido un profesor quien ha dado con el quid de la cuestión. Podría dejar la resolucióndel enigma al lector… pero no sé si hay datos suficientes para deducir que pasaba.
Estaba usando muy pocas claves distintas (27 para vectores de 100000 elementos). ¿Porque hacía eso que el caso peor y el medio tuviran un coste similar?
La explicación es sencilla; el Quicksort tradicional tiene 3 casos malos (orden cuadrático):
-un vector ordenado
-un vector inversamente ordenado
-un vector de elementos iguales (la comparacíon “<=” lo hace equivalente a un vector ordenado).
Teniendo pocas claves en un vector muy grande, se forman grandes grupos de claves idénticas.
Solución: Usar muchas claves diferentes (todo el rango de enteros en ADA).
Este es otro argumento a favor de los algoritmos de ordenación adaptativos, normalmente usar pocas claves será una gran ventaja. ¿Pero y con un texto?Muchas letras iguales seguidas no habrá… pero con 27 claves (la letras), seguro que hay grandes grupos ordenados en la mayor parte de los vectores. Además, un texto no es aleatorio.
Esta, me parece una explicación sencilla, bonita y para toda la familia.
Pero atención, porque le faltan bastantes optimizaciones.
En este documento, explican como mediante una desordenación aleatoria de los elementos del vector a ordenar, los algoritmos adaptativos de ordenación son más rápidos.
Es un punto de vista probabilistico, y supongo que presupone que el vector a ordenar no está inicialmente desordenado de forma realmente aleatoría.
De todas formas, un mergesort adaptativo no es la panacea. Su gran virtud es poder usarlo en cualquier caso con una gran eficacia. Por ejemplo si alguien “se equivoca” y decide ordenar un vector ya ordenado, o un vector que contiene ya un vector ordenado. Quicksort es mucho más facíl de implementar, pero más lento (y no sólo en estos casos).
P.D.: El algoritmo en el que aplican esta mejora no es “Timsort”, sino uno de sus predecesores.
P.D.2:Algún día acabaré mi versión de Timsort… más tarde haré algo mejor :p.
Para todo el que le interesen los problemas de optimización, y en especial el TSP, desde su entrada en la Wikipedia, he llegado a unos documentos interesantes.
Me llama la atención especialmente que para aproximaciones igual de buenas a las personas les cuesta menos calcularlas que usando algoritmos sofisticados.
Le acabo de dar algunas vueltas, y estoy casi seguro de que se puede hacer un merge con espacio adicional constante . Sean A y B los dos vectores a mezclar, la complejidad computaciotnal de dicho algoritmo sería siempre inferior a AxB.
El único problema que veo es que en el procesador iba a usar registros que te cagas, y que sería realmente complejo de programar, la búsqueda binaría incluiría a menudo elementos que no están en su posición original en el vector.
Bueno, como ya sabemos que P=NP (:P).
La idea que proponía hace un tiempo era hacer una base de datos enorme y compartida, de todos los mejores algoritmos para realizar cualquier función. Usaríamos un lenguaje funcional tan simple como el hablado para resolver cualquier problema.
Aprovechando que P=NP, probablemente siempre sepamos el mejor algoritmos para resolver un problema.
De modo que en esa enorme base de datos ya no necesitaremos tener código. Asúmiendo que se deriven los algoritmos óptimos de sus especificaciones, con guardar especificaciones ligadas al nombre de los algoritmos y/a/o sus sinónimos, basta.
¿Fácil, sencillo y para toda la familia, no?
Y el que no lo vea, en mi humilde opinión, está ciego o tiene poca visión de futuro.
Por eso son importantes iniciativas como esta.
Que se puede aprender lo mismo divirtiéndose y entendiéndolo lo sabe todo el mundo.
Sin embargo seguimos copiando apuntes como borregos, algo que también todo el mundo sabe que es inútil, las cosas no se memorizan a largo plazo por copiarlas, sino por entenderlas.
Aprendemos muchas cosas estériles.
¿Si todos vemos que se puede mejorar porque no se mejora?
¿Falta de medios? ¿No se ve el camino?
En la escuela ya pensaba que la forma de la que nos enseñaban distaba mucho de ser óptima, tiene que haber algo mejor. Y no hablo de adquirir conocimientos con una pastilla mágica.
¿Porque no se dedican equipos enteros a desarrollar, por ejemplo, software EDUCATIVO para universitarios?
Yo me sé de un par de asignaturas de Ingeniería Informática, que si un software interactivo las explicara decentemente y con un mínimo de diversión y elegancia, podrían venderlo a 100 leuros la unidad, y lo venderían como churros.
P.D.: De más joven probé Adi, una maravilla en aquellos tiempos de 486 y Windows 3.1. La idea era genial, y de verdad que aprendías algo, pero el software distraía demasiado y te permitía juguetear en exceso.