Algoritmo determinístico simples e prático, tempo de execução complicado

18

Muitas vezes, se o tempo de execução de um algoritmo for uma expressão complicada, o próprio algoritmo também será complicado e impraticável. Cada uma das raízes do cubo e fatores no tempo de execução assintótico tende a adicionar complexidade ao algoritmo e também ocultar fatores constantes no tempo de execução. $\log \log n$

Temos exemplos impressionantes em que essa regra geral falha?

É claro que é fácil encontrar exemplos de algoritmos que são muito difíceis de implementar, apesar de terem um tempo de execução no pior dos casos muito simples. Mas e o inverso?

Temos exemplos de algoritmos determinísticos muito simples e práticos, fáceis de implementar, mas que apresentam uma expressão muito complicada como seu pior caso de tempo de execução assintótico?

Observe as palavras-chave "determinística" e "pior caso"; a análise de algoritmos aleatórios simples leva facilmente a expressões complicadas.

Claro que o que é "complicado" é uma questão de gosto. De qualquer forma, eu preferiria ver uma expressão que é feia demais para colocar no título do seu trabalho. E eu preferiria uma função complicada de um parâmetro natural (tamanho da entrada, número de nós etc.).

PS. Eu pensei que não faria disso uma "questão da grande lista", e não da CW. Eu gostaria de encontrar um único exemplo excelente (se existir). Portanto, publique outra resposta apenas se você achar que é "melhor" do que qualquer uma das respostas até agora.

ds.algorithms soft-question recreational Jukka Suomela
fonte

2

O algoritmo de teste de primalidade da AKS está qualificado como resposta? Eu estou hesitando porque a "complicação" de seu tempo de execução é, em certo sentido, resultado da pseudo-aleatoriedade da distribuição dos números primos ...

arnab

Meu sentimento é que o pior caso é, na maioria dos casos, algo que causa "atropela tudo" e tudo é o que medimos no tempo de execução. Portanto, naturalmente, algoritmos fáceis têm tempos de execução de WC fáceis. Tempos de execução complicados surgem se tentarmos economizar um pouquinho com algum truque. Mas sua pergunta é interessante; Estou certamente curioso para ver se meu sentimento está certo.

Raphael

@arnab: Obrigado, AKS é uma boa ideia. Mas não tenho certeza se podemos chamá-lo de "prático"?

Jukka Suomela

Os esquemas de transmissão de mensagens como propagação de pesquisa, propagação de restrição ou TRW seqüencial contam como "algoritmos"? Fácil de implementar, em tempo de execução é difícil de prever

Yaroslav Bulatov

Opa, eu sempre gosto do método rho de Pollard, é simples e prático, e a análise é realmente difícil, mas a aleatoriedade do algoritmo o torna desqualificado como resposta ao post ...

Hsien-Chih Chang 之之

20

O melhor exemplo em que posso pensar é em um algoritmo (descrito abaixo) para calcular o nível em um arranjo de linhas no plano, ou seja, a linha poligonal formada pelos pontos que possuem exatamente linhas verticalmente acima dele. Este não é o algoritmo mais eficiente conhecido para o problema. Existem algoritmos mais eficientes com complexidades mais simples, mas acredito que este seja mais prático do que a maioria (se não todos). A análise provavelmente não é rígida, porque usa a complexidade do nível , que é um famoso problema aberto (acho que todos os outros termos da análise são rígidos). Mesmo assim, duvido que limites aprimorados para o nível tornem o tempo de execução muito mais simples. Eu vou assumir $k$ $n$ $k$ $k$ $k$ para escrever a complexidade em função de sozinho. $k=n/2$ $n$

O algoritmo é baseado no paradigma de varredura de linha e usa dois torneios cinéticos -ary como filas de prioridade cinética. Inserções e exclusões são realizadas quando uma linha fica acima ou abaixo do nível , movendo uma linha de um torneio cinético para outro. Portanto, existem inserções e deleções (usando ligado para o de Dey complexidade -level). Cada evento é processado em de tempo e existem $(\log n)$ $k$ $O(n^{4/3})$ $k$ $O(\log n)$ eventos (o vem da complexidade do envelope superior dos arranjos dos segmentos de linha, enquanto o vem da altura de umaárvore -ary ) O tempo total de execução é $O(n^{4/3} \alpha(n) \log n / \log \log n)$ $\alpha(n)$ $\log n / \log \log n$ $(\log n)$

O (n^{4 / 3} α (n) \log^{2} n / \log \log n) .

$O(n^{4/3} \alpha(n) \log^2 n / \log \log n).$

Consulte o manuscrito de Timothy Chan http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz para obter mais detalhes e referências. O fator pode ser removido usando um torneio cinético binário (em vez de -ary), mas na verdade acelera a fila de prioridade cinética nos testes que eu executei. A complexidade deve ficar um pouco mais feia e pior (embora o algoritmo ainda seja prático) se um heap cinético for usado em vez de um torneio cinético (um dentro de uma raiz quadrada deve aparecer). $1/\log \log n$ $(\log n)$ $\log$

Guilherme D. da Fonseca
fonte

Excelente exemplo, obrigado! Isso não vai ser fácil de vencer. :)

Jukka Suomela

1

Esse algoritmo é mais lento na prática do que os algoritmos aleatórios, que são muito fáceis de implementar (como alguém que implementou um desses algoritmos (veja meu artigo "Caminhando em um arranjo planar".)

Sariel Har-Peled

Aceitei esta resposta, pois parece estar mais próxima do que eu tinha em mente. Mas se alguém tiver novas idéias, eu ficaria feliz em ouvir!

Jukka Suomela

24

As operações da estrutura de dados de localização da união parecem atender aos seus critérios:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Kevin Wortman
fonte

2

Na verdade, eu postei a mesma resposta, mas a apaguei depois que percebi que você me venceu. :) Algoritmo simples e elegante que um não-teórico pode até descobrir, mas Ackermann inverso amortizou a complexidade.

Warren Schudy

O (α (n))

$O(\alpha(n))$

O (n^{4 / 3} α (n) \log^{2} n / \log \log n)

$O(n^{4/3} \alpha(n) \log^2 n / \log \log n)$

A proporção entre o comprimento do algoritmo e a complexidade da prova para encontrar a união é provavelmente imbatível - todas as três operações são o que, nove linhas de código?

Neel Krishnaswami

1

Não acho que a pergunta seja sobre um algoritmo simples e prático com análises complexas . Penso que a pergunta é sobre um algoritmo simples e prático com tempo de execução complexo , ou seja, a expressão real obtida para o limite superior.

Guilherme D. da Fonseca

6

Algoritmo simplex. Fácil de implementar e funciona maravilhosamente na prática, mas é uma bagunça para analisar teoricamente.

Mohit Singh
fonte

n

$n$

na verdade, simplex é conhecido por levar um tempo exponencial, na pior das hipóteses, através da construção Klee-Minty. Penso que não é um exemplo do que Jukka está perguntando #

Suresh Venkat

1

Talvez eu devesse ter dito o método simplex, e não o algoritmo simplex. O cubo Klee-Minty e suas variações funcionam para algumas regras de giro da baunilha. Mas, por exemplo, a regra de rotação de faceta aleatória tem um limite superior e (recente) louco. Gil Kalai teve uma boa entrada no blog sobre os resultados recentes. gilkalai.wordpress.com/2010/11/09/…

Mohit Singh

bom ponto, Mohit. Eu também estava confuso.

Suresh Venkat

2

Não tenho certeza se você considera isso "prático", mas é um famoso problema aberto. Paul Erdos disse sobre a conjectura de Collatz: "A matemática ainda não está pronta para esses problemas"

$x=1$

Mohammad Al-Turkistany
fonte

E qual é o problema resolvido por esse algoritmo ...?

Jukka Suomela

Ele sugere procurar novas técnicas de análise em tempo de execução.

Mohammad Al-Turkistany

2

você poderia dizer que uma busca por força bruta por uma prova da conjectura de Collatz também motiva "novas técnicas de análise em tempo de execução"; em ambos os casos, o algoritmo está apenas explorando um dígrafo sem pensar. A conjectura de Collatz é divertida, mas não acho que este seja um exemplo interessante de "um algoritmo".

Niel de Beaudrap

2

Este exemplo, embora não atenda à letra da sua solicitação, pode ser interessante porque possui alguma afinidade espiritual. Especificamente, a questão de classificar pilhas de panquecas e panquecas queimadas por reversões.

http://en.wikipedia.org/wiki/Pancake_sorting

Uma área de aplicação é a biologia computacional (genética), onde perguntas sobre rearranjos genômicos podem ser apresentadas em termos da distância entre permutações, usando reversões de partes das permutações sujeitas a várias regras.

Joseph Malkevitch
fonte

Algoritmo determinístico simples e prático, tempo de execução complicado

Respostas: