the algorithm design manual español
¿Hay algoritmos O(n ^ n) reales? (5)
El programa que toma una descripción de una máquina Turing (que termina), y devuelve el número de pasos que se necesita para terminar. Este es un programa relativamente simple de escribir: simplemente puede emular la máquina de Turing y contar los pasos.
La complejidad de este programa no tiene un límite superior computable (y en particular crece más rápido que cualquier función computable), por lo que ciertamente crece más rápido que O (n ^ n).
El tiempo de ejecución en el peor de los casos en una entrada de tamaño n es BB (n), la secuencia Busy Beaver , que comienza con 0, 1, 4, 6, 13, se desconoce después de esto (aunque existen límites inferiores, por ejemplo, los siguientes dos valores son al menos 47176870 y 7.412 × 10 ^ 36534 respectivamente) e indiscutibles para n lo suficientemente grandes.
¿Existe algún algoritmo real con una complejidad de tiempo O (n ^ n) que no sea solo un truco?
Puedo crear un algoritmo de este tipo, como calcular n ^ n en O (n ^ n) / Θ (n ^ n):
long n_to_the_power_of_m(int n, int m) {
if(m == 0) return 1;
long sum = 0;
for(int i = 0; i < n; ++i)
sum += n_to_the_power_of_m(n, m-1);
return sum;
}
(Necesita más de 4 minutos para calcular 10 ^ 10)
O al revés: ¿Hay algún problema que no pueda resolverse mejor que en O (n ^ n)?
Hay cálculos (por ejemplo, tetration ) donde el tamaño de salida es O (n n ). Es un poco difícil calcularlos con una complejidad de tiempo menor que O (n n ).
Hay muchos problemas de optimización que son esencialmente O (n!), Es decir, en la compresión de datos. Los algoritmos comunes para todo esto necesitan hacer trampa de una manera u otra (muchos se basan en heurísticas) pero no pueden asegurarse de que hayan encontrado el resultado perfecto de esta manera. Es decir, elegir los filtros de línea óptimos durante la compresión de una imagen PNG es un problema que es comparativamente fácil de entender.
Otro ejemplo son los algoritmos para romper el cifrado que pueden ser incluso peores que O (n!).
Lo que ha codificado en su ejemplo es muy similar a una primera búsqueda en profundidad. Entonces, esa es una respuesta.
Un primer algoritmo de búsqueda en profundidad sin ninguna característica especial (como rutas re-convergentes que pueden optimizarse) debe ser n ^ n.
Esto en realidad no es un ejemplo artificial. Los programas de ajedrez operan en el mismo algoritmo. Cada movimiento hay n movimientos a considerar (es decir, ramas), y busca d movimientos profundos. Entonces eso se convierte en O (n ^ d)
Según Wikipedia , hay algunos problemas de tiempo exponencial doble O (2 2 poli (n) ) que son más complejos que O (n n ), por ejemplo, "Procedimientos de decisión para la aritmética de Presburger " (O (2 2 cn )) y "Computación una base de Gröbner "(en el peor de los casos O (2 2 n / 10 )