algorithm - rapper - big o notation java
¿Algoritmos con tiempo de ejecución superexponencial? (4)
¿Los algoritmos para calcular números reales a una cierta precisión cuentan? La fórmula para el área del conjunto de Mandelbrot converge extremadamente lentamente ; 10 118 términos para dos dígitos, 10 1181 términos para tres.
El otro día hablé con un estudiante sobre las clases de complejidad comunes de algoritmos, como O (n), O (n k ), O (n lg n), O (2 n ), O (n!), Etc. Estaba tratando de encontrar un ejemplo de un problema para el cual las soluciones cuyo mejor tiempo de ejecución conocido es super-exponencial, como O (2 2 n ), pero aún así son decidibles (por ejemplo, ¡no es el problema de la detención!) El único ejemplo que conozco es la satisfacibilidad de la aritmética de Presburger , que no creo que ningún estudiante de introducción de CS realmente entienda o pueda relacionarse.
Mi pregunta es si existe un problema conocido cuya solución más conocida tenga un tiempo de ejecución superexponencial; al menos ω (n!) o ω (n n ). Realmente espero que haya algún problema "razonable" que cumpla con esta descripción, pero no conozco ninguno.
Este no es un problema práctico cotidiano, pero es una forma de construir problemas relativamente sencillos de complejidad creciente.
- La complejidad de Kolmogorov K (x) es el tamaño del programa más pequeño que genera la cadena $ x $ en una computadora universal predeterminada U. Es fácil mostrar que la mayoría de las cadenas no se pueden comprimir (ya que hay más cadenas de longitud n que los programas de longitud n).
- Si le damos a U un tiempo de ejecución máximo (por ejemplo, alguna función polinomial P), obtenemos una complejidad de Kolmogorov limitada en el tiempo. El mismo argumento de conteo es válido: hay algunas cadenas que son incompresibles bajo esta complejidad de Kolmogorov limitada por el tiempo. Llamemos a la primera cadena de este tipo (de cierta longitud n) x P
- Dado que la complejidad de Kolmogorov limitada en el tiempo es computable, podemos probar todas las cadenas y encontrar x P
- Encontrar x P no se puede hacer en tiempo polinomial, o podríamos usar este algoritmo para comprimirlo, por lo que encontrarlo debe ser un problema superpolinomial. Sin embargo, sí sabemos que podemos encontrarlo en el tiempo exp (P). (Saltando sobre algunos detalles técnicos aquí)
- Así que ahora tenemos un límite de tiempo E = exp (P). Podemos repetir el procedimiento para encontrar x E , y así sucesivamente.
Este enfoque nos da un problema de super-F decidible para cada función F construible en el tiempo: encuentre la primera cadena de longitud n (alguna constante grande) que es incompresible en la F con límite de tiempo.
Mostrando toda la permutación de la cadena de longitud n es n !, ¡encontrando el ciclo hamiltoniano es n !, coloración mínima del gráfico, ...
Edición : funciones de Ackerman aún más rápidas. De hecho parece que no tienen función encuadernada.
A(x,y) = y+1 (if x = 0)
A(x,y) = A(x-1,1) (if y=0)
A(x,y) = A(x-1, A(x,y-1)) otherwise.
from wiki:
A(4,3) = 2^2^65536,...
Parsimonia máxima es el problema de encontrar un árbol evolutivo que conecte n secuencias de ADN (que representan a las especies) que requiera la menor cantidad de mutaciones de un solo nucleótido. Las n secuencias dadas están limitadas a aparecer en las hojas; La topología del árbol y las secuencias en los nodos internos son lo que podemos elegir.
En más términos de CS: se nos da un montón de cadenas de longitud-k que deben aparecer en las hojas de algún árbol, y tenemos que elegir un árbol, más una cadena de longitud-k para cada nodo interno en el árbol, a fin de Minimiza la suma de las distancias de Hamming en todos los bordes.
Cuando también se proporciona un árbol fijo, la asignación óptima de secuencias a los nodos internos se puede determinar de manera muy eficiente utilizando el algoritmo de Fitch . Pero en el caso habitual, no se da un árbol (es decir, se nos pide que encontremos el árbol óptimo), y esto hace que el problema sea difícil de hacer, lo que significa que, en principio, todo árbol debe intentarse. A pesar de que un árbol evolutivo tiene una raíz (que representa el ancestro hipotético), solo debemos considerar distintos árboles sin raíces, ya que el número mínimo de mutaciones requerido no se ve afectado por la posición de la raíz. Para n especies hay 3 * 5 * 7 * ... * (2n-5) árboles binarios sin raíz etiquetados en hoja. (Hay un solo árbol con 3 especies, que tiene un solo vértice interno y 3 bordes; la 4ª especie se puede insertar en cualquiera de los 3 bordes para producir un árbol de 5 bordes; la 5ª especie se puede insertar en cualquier de estos 5 bordes, y así sucesivamente, este proceso genera todos los árboles exactamente una vez.) ¡Esto a veces se escribe (2n-5)! , con !! que significa "factorial doble".
En la práctica, se utiliza la rama y el límite, y en la mayoría de los conjuntos de datos reales, esto se logra para evitar evaluar la mayoría de los árboles. ¡Pero los datos aleatorios altamente "no treelike" requieren todos, o casi todos (2n-5)! árboles a examinar - ya que en este caso muchos árboles tienen un conteo mínimo de mutaciones casi iguales.