Exemplo de um algoritmo em que um termo de ordem inferior domina o tempo de execução de qualquer entrada prática?

A notação Big-O esconde fatores constantes; portanto, existem alguns algoritmos inviáveis ​​para qualquer tamanho de entrada razoável, porque o coeficiente no termo é muito grande.$O(n)$$n$

Existem algoritmos conhecidos cujo tempo de execução é mas com algum termo de baixa ordem que é tão grande que, para tamanhos de entrada razoáveis, domina completamente o tempo de execução? Eu gostaria de usar um algoritmo como este e um exemplo em um curso de algoritmos, pois fornece uma boa razão para a notação big-O não ser tudo.$O(f(n))$$o(f(n))$

Obrigado!

A criptografia é um exemplo, se degenerado. Por exemplo, a quebra da criptografia AES é - tudo o que você precisa fazer é encontrar a chave correta entre um número finito, 2 128 ou 2 192 ou 2 256, dependendo do tamanho da chave (suponha que o texto simples seja conhecido por determinar a chave sem ambiguidade). No entanto, até 2 128 operações levariam todos os computadores hoje (um bilhão ou mais, cada um fazendo cerca de um bilhão de operações por segundo) mais do que a vida útil do universo (cerca de um bilhão de segundos).$O(1)$$2^{128}$$2^{192}$$2^{256}$$2^{128}$

Uma maneira ligeiramente diferente de ilustrar por que o big-O não é tudo é observar que às vezes usamos um algoritmo diferente para tamanhos de entrada pequenos. Por exemplo, tome quicksort. Com a escolha certa de pivô (que é um negócio complicado!), É . O Quicksort opera por meio de divisão e conquista: toda instância envolve fazer muita classificação de pequenas matrizes. Para matrizes pequenas, métodos quadráticos, como a classificação por inserção, têm melhor desempenho. Portanto, para obter o melhor desempenho, uma classificação rápida de uma grande variedade envolve várias execuções de classificação por inserção para tamanhos pequenos.$O(n \lg n)$

Dois exemplos vêm à mente do campo da complexidade parametrizada e dos algoritmos FPT. Pode não ser exatamente o que você está procurando, mas aqui vai.

Considere um problema gráfico, como 3-COLORING ou HAM-CYCLE. Ambos os problemas podem ser expressos na lógica monádica de segunda ordem e, portanto, podem ser decididos em tempo linear de gráficos com largura de árvore limitada. Isso é resultado de Bruno Courcelle , mas o algoritmo resultante está longe de ser prático.

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

Um pouco relacionados à sua pergunta, são algoritmos conhecidos por terem bom desempenho teoricamente, mas não são usados ​​em problemas reais devido à impraticabilidade em instâncias menores. em outras palavras, como você solicita, o "desempenho anunciado" só é possível para grandes entradas na teoria, não vistas em aplicações práticas. isso às vezes se reflete nas estimativas Big-Oh, outras vezes não exatamente. alguns algoritmos têm um bom "desempenho" teórico, mas são logicamente complexos e nunca foram implementados por ninguém; portanto, o "desempenho" em tamanhos de instância práticos nem sequer é conhecido, por exemplo, como no problema de Fluxo Máximo .

• teste de primalidade em P via algoritmo AKS

• Algoritmo de multiplicação de matrizes Coppersmith-Winograd

• veja também os algoritmos de fluxo máximo de ponta são práticos? tcs.se

• veja também algoritmos poderosos e complexos demais para implementar tcs.se

• algoritmos galácticos blog RJLipton

Isso é uma piada, mas tem um lado sério ...

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