¿Ejemplo de un algoritmo en el que un término de bajo orden domina el tiempo de ejecución para cualquier entrada práctica?

La notación Big-O oculta factores constantes, por lo que existen algunos algoritmos que no son factibles para cualquier tamaño de entrada razonable porque el coeficiente en el término n es muy grande.$O(n)$$n$

¿Hay algún algoritmo conocido cuyo tiempo de ejecución sea pero con algún término de bajo orden o ( f ( n ) ) que sea tan grande que para tamaños de entrada razonables domine completamente el tiempo de ejecución? Me gustaría usar un algoritmo como este como un ejemplo en un curso de algoritmos, ya que da una buena razón por la cual la notación big-O no es todo.$O(f(n))$$o(f(n))$

¡Gracias!

La criptografía es un ejemplo, si es degenerada. Por ejemplo, romper el cifrado AES es : todo lo que tiene que hacer es encontrar la clave correcta entre un número finito, 2 128 o 2 192 o 2 256 dependiendo del tamaño de la clave (suponga que se conoce suficiente cantidad del texto plano) determinar la clave sin ambigüedades). Sin embargo, incluso 2 128 operaciones tomarían todas las computadoras hoy (mil millones o más o menos, cada una haciendo alrededor de mil millones de operaciones por escenario) más que la vida útil del universo (aproximadamente mil millones de segundos).$O(1)$$2^{128}$$2^{192}$$2^{256}$$2^{128}$

Una forma ligeramente diferente de ilustrar por qué big-O no lo es todo es comentar que a veces usamos un algoritmo diferente para tamaños de entrada pequeños. Por ejemplo, toma quicksort. Con la elección correcta de pivote (¡lo cual es un negocio complicado!), Es . Quicksort opera dividiendo y conquistando: cada instancia implica hacer una gran cantidad de arreglos pequeños. Para matrices pequeñas, los métodos cuadráticos, como la clasificación por inserción, funcionan mejor. Por lo tanto, para obtener el mejor rendimiento, una selección rápida de una gran matriz implica muchas ejecuciones de clasificación de inserción para tamaños pequeños.$O(n \lg n)$

Me vienen a la mente dos ejemplos del campo de la complejidad parametrizada y los algoritmos FPT. Puede que esto no sea exactamente lo que está buscando, pero aquí va.

Considere un problema gráfico, como 3-COLORING o HAM-CYCLE. Ambos problemas pueden expresarse en lógica monádica de segundo orden y, por lo tanto, pueden decidirse en tiempo lineal de gráficos con ancho de árbol acotado. Este es el resultado de Bruno Courcelle , pero el algoritmo resultante está lejos de ser práctico.

$O(p^{9p/2})L$$O(p^{2p}L)$$p$$L$

algo relacionado con su pregunta son los algoritmos que se sabe que tienen un buen rendimiento teóricamente pero que no se utilizan en problemas reales debido a la falta de practicidad en instancias más pequeñas. en otras palabras, como usted solicita, el "rendimiento anunciado" solo es posible para entradas grandes en teoría, que no se ven en aplicaciones prácticas. esto a veces se refleja en las estimaciones de Big-Oh, otras veces no exactamente. algunos algoritmos tienen un buen "rendimiento" teórico pero son muy complejos desde el punto de vista lógico y nunca han sido implementados por nadie, y por lo tanto, el "rendimiento" en tamaños de instancias prácticas ni siquiera se conoce, por ejemplo, como en el problema del flujo máximo .

• prueba de primalidad en P a través del algoritmo AKS

• Algoritmo de multiplicación de matriz de calderero-winograd

• vea también ¿ son prácticos los algoritmos de flujo máximo de última generación? tcs.se

• vea también algoritmos poderosos demasiado complejos para implementar tcs.se

• blog de algoritmos galácticos RJLipton

Esto es una especie de broma pero tiene un lado serio ...

$O(n\log n)$$O(n^2)$