Muy a menudo, si el tiempo de ejecución de un algoritmo es una expresión complicada, el algoritmo en sí también es complicado y poco práctico. Cada una de las raíces cúbicas y los factores en el tiempo de ejecución asintótico tienden a agregar complejidad al algoritmo y también a factores constantes ocultos en el tiempo de ejecución.
¿Tenemos ejemplos sorprendentes en los que esta regla general falla?
Por supuesto, es fácil encontrar ejemplos de algoritmos que son muy difíciles de implementar a pesar de que tienen un tiempo de ejecución muy simple en el peor de los casos. ¿Pero qué hay de lo contrario?
¿Tenemos ejemplos de algoritmos deterministas muy simples y prácticos que sean fáciles de implementar pero que tengan una expresión muy complicada como su peor tiempo de ejecución asintótico?
Tenga en cuenta las palabras clave "determinista" y "peor de los casos"; El análisis de algoritmos aleatorios simples conduce con bastante facilidad a expresiones complicadas.
Por supuesto, lo que es "complicado" es una cuestión de gustos. De todos modos, preferiría ver una expresión que sea demasiado fea para poner en el título de su artículo. Y preferiría una función complicada de un parámetro natural (tamaño de entrada, número de nodos, etc.).
PD. Pensé que no haría de esto una "pregunta de la lista grande", y no CW. Me gustaría encontrar un solo ejemplo excelente (si es que existe). Por lo tanto, publique otra respuesta solo si cree que es "mejor" que cualquiera de las respuestas hasta ahora.
fuente
Respuestas:
El mejor ejemplo que se me ocurre es un algoritmo (descrito a continuación) para calcular el nivel en una disposición de líneas en el plano, es decir, la línea poligonal formada por los puntos que tienen exactamente líneas verticalmente por encima. Este no es el algoritmo más eficiente conocido para el problema. Hay algoritmos más eficientes con complejidades más simples, pero creo que este es más práctico que la mayoría (si no todos) de ellos. El análisis probablemente no es estricto, porque utiliza la complejidad de nivel , que es un famoso problema abierto (creo que todos los demás términos en el análisis son estrictos). Aún así, dudo que los límites mejorados para -level harían el tiempo de ejecución mucho más simple. Asumirén k k k k = n / 2 nk norte k k k k = n / 2 para escribir la complejidad en función de solo.norte
El algoritmo se basa en el paradigma de barrido de línea y utiliza dos torneos cinéticos -ary como colas de prioridad cinéticas. Las inserciones y eliminaciones se realizan cuando una línea va por encima o por debajo del nivel , moviendo una línea de un torneo cinético a otro. Por lo tanto, hay inserciones y eliminaciones (usando el límite de Dey para la complejidad de nivel ). Cada evento se procesa en tiempo y hay eventos (el proviene del complejidad de la envoltura superior de arreglos de segmentos de línea, mientras que proviene de la altura de unk O ( n 4 / 3 ) k O ( log n ) O ( n 4 / 3 α ( n ) log n / log log n ) α ( n ) log n / log log n ( log n )( registron ) k O ( n4 / 3) k O ( logn ) O ( n4 / 3α ( n ) logn / logIniciar sesiónn ) α ( n ) Iniciar sesiónn / logIniciar sesiónnorte ( registron ) -ary tree). El tiempo total de ejecución es
Consulte el manuscrito de Timothy Chan http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz para obtener más detalles y referencias. El factor se puede eliminar mediante el uso de un torneo cinético binario (en lugar de -ary), pero en realidad acelera la cola de prioridad cinética en las pruebas que realicé. La complejidad debería ser un poco más fea y peor (mientras que el algoritmo seguirá siendo práctico) si se usa un montón cinético en lugar de un torneo cinético ( debería aparecer un dentro de una raíz cuadrada).( log n ) log1 / logIniciar sesiónnorte ( registron ) Iniciar sesión
fuente
Las operaciones de estructura de datos de búsqueda de unión parecen cumplir con sus criterios:
http://en.wikipedia.org/wiki/Disjoint-set_data_structure
fuente
Algoritmo simple. Fácil de implementar y funciona maravillosamente en la práctica, pero es un desastre analizarlo teóricamente.
fuente
No estoy seguro si considera esto "práctico", pero es un famoso problema abierto. Paul Erdos dijo sobre la conjetura de Collatz: "Las matemáticas aún no están listas para tales problemas"
fuente
Este ejemplo, si bien no cumple con la carta de su solicitud, puede ser de interés porque tiene cierta afinidad espiritual. Específicamente, la cuestión de clasificar pilas de panqueques y panqueques quemados por reversiones.
http://en.wikipedia.org/wiki/Pancake_sorting
Un área de aplicación es la biología computacional (genética) donde las preguntas sobre los reordenamientos del genoma pueden formularse en términos de la distancia entre permutaciones utilizando reversiones de piezas de permutaciones sujetas a varias reglas.
fuente