Sobre la cota log(n!).
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 ;).
May 19th, 2007 at 15:51
Quiero aclarar una cosa, por “recursivamente adaptativo” lo que entiendo es algo que aún no he visto en ningún algoritmo adaptativo.
Un algoritmo adaptativo aprovecha el orden de la secuencia de entrada, la idea es que un algoritmo recursivamente adaptativo, aproveche el orden de la secuencia de entrada Y DE TODAS Y CADA UNA DE LAS SECUENCIAS INTERMEDIAS.