Quando encontramos limites melhores para algoritmos conhecidos?

Existem exemplos interessantes de algoritmos que foram publicados com limites comprovados e onde limites estritamente melhores foram publicados posteriormente? Algoritmos não melhores com limites melhores - obviamente, isso aconteceu! Mas uma melhor análise leva a uma melhor ligação a um algoritmo existente

Eu pensei que a multiplicação de matrizes fosse um exemplo disso, mas eu me convenci disso (talvez incorretamente!) Depois de tentar entender melhor o Coppersmith – Winograd e seus amigos.

O algoritmo Union-Find, que Tarjan ¹ mostrou ter complexidade $n \alpha(n)$ , onde $\alpha(n)$ é a função inversa de Ackermann, havia sido analisado anteriormente por várias pessoas. Segundo a Wikipedia, foi inventado por Galler e Fischer ² , mas isso parece estar incorreto, pois eles não tinham todos os componentes do algoritmo necessários para fazê-lo funcionar tão rapidamente.

Com base em breves varreduras dos artigos, parece que o algoritmo foi inventado por Hopcroft e Ullman ³ , que deram um limite de tempo (incorreto) para $O(n)$ . Fischer ⁴ então encontrou o erro na prova e deu um tempo $O(n \log\log n)$ . Em seguida, Hopcroft e Ullman ⁵ deram um limite de tempo $O(n \log ^*n)$ , após o qual Tarjan ¹ encontrou o limite de tempo $O(n \alpha(n))$ ideal) O ( n α ( n ) ) .

¹ RE Tarjan, "Eficiência de um algoritmo de união de conjuntos bom, mas não linear" (1975).
² BS Galler e MJ Fischer, "Um algoritmo de equivalência aprimorado" (1964).
³ JE Hopcroft e JD Ullman, "Um algoritmo de fusão de lista linear" (1971).
⁴ MJ Fischer, "Eficiência de algoritmos de equivalência" (1972).
⁵ JE Hopcroft e JD Ullman, "Algoritmos de fusão de conjuntos" (1973).

Sabe-se que o algoritmo de Paturi, Pudlák, Saks e Zane (PPSZ) para $k\text{-} \mathrm{SAT}$ possui um tempo de execução de $O(1.364^n)$ para $3\text{-}\mathrm{SAT}$ , com um limite melhor de $O(1.308^n)$ para fórmulas com garantia de uma atribuição satisfatória exclusiva. Mais tarde, Hertli fez uma análise aprimorada, mostrando que esse limite aprimorado de tempo de execução também vale para o caso geral, mostrando assim o PPSZ como o melhor algoritmo para $3\text{-}\mathrm{SAT}$ conhecido na época.

O Ataque impasse menciona que a análise da peneira número campo geral (quando aplicado a computação logaritmos discretos ao longo $\mathbb{F}_p$ ) passo descida foi tightend, ver parte superior esquerda da página 3. Como esta é a única etapa que não pode ser pré-calculada (se $\mathbb{F}_p$ é fixa), a sua eficácia foi fundamental para o seu ataque.

A análise inicial parece estar em Gordon 92 , onde descida foi orçado semelhante ao precomputation, em $L_p(1/3, 3^{2/3})$ . A análise mais apertado parece ser a partir da tese de Barbulescu , onde é descida orçado em $L_p(1/3, 1.232)$ , onde:

$k$$O(n^{k+o(1)})$$O(n^{2k-2})$$O(n^{1.98k+O(1)})$

$\Omega(n^k)$

Nota: Uma palestra de Jason Li (e os slides correspondentes) pode ser encontrada no site do TCS + .

$k$

$k$$(2k-1)$$k$

$3$ forneça uma análise mais refinada (contando subproblemas / subestruturas), levando a melhores recorrências e, portanto, melhores tempos de execução. Acho que existem vários exemplos na literatura de complexidade parametrizada, em que adicionar outra variável à análise pode levar a tempos de execução aprimorados, mas estou fora desse jogo há vários anos e não consigo pensar em exemplos específicos em o momento. Existem vários trabalhos nas áreas do FPT e PTAS que surgem quando se busca "análise aprimorada" nos títulos dos trabalhos.

Se especificar escolhas conta como o mesmo algoritmo (como a heurística de rank de profundidade da union-find), o algoritmo Edmonds-Karp é uma 'análise aprimorada' de Ford-Fulkerson, e eu imagino que existem muitos outros problemas que possuem algoritmos que viram melhorias no tempo de execução das novas regras de escolha.

Depois, há um monte de análises amortizadas dos algoritmos existentes (acho que a união-busca se encaixa nessa descrição, aqui está outra https://link.springer.com/article/10.1007/s00453-004-1145-7 )