Aqui estão algumas maneiras de analisar o tempo de execução de um algoritmo:
1) Análise de pior caso: tempo de execução na pior instância.
2) Análise de caso médio: tempo de execução esperado em uma instância aleatória.
3) Análise amortizada: tempo médio de execução na pior sequência de instâncias.
4) Análise suavizada: Tempo de execução esperado na pior instância perturbada aleatoriamente.
5) Análise de caso genérico: tempo de execução no pior de todos, exceto um pequeno subconjunto de instâncias.
Minha pergunta: esta é uma lista completa?
Eu acho que esse tipo de lista nunca pode ser exaustivo.
A otimização da instância é uma propriedade muito interessante dos algoritmos. Pode-se generalizar noções de otimalidade de instância e chegar a noções surpreendentemente interessantes que incluem análise de pior caso e de caso médio.
Embora não se enquadre estritamente no âmbito da análise tradicional de algoritmos, é interessante por si só. A idéia de um artigo de Afshani-Barbay-Chan (FOCS '09) que discute um algoritmo geométrico considera o desempenho do algoritmo alheio à ordem de entrada (que é relevante para o seu problema particular).
Isso pode generalizar da seguinte maneira: Para cada algoritmo particione as entradas em classes de equivalência e considere o desempenho do algoritmo como algum tipo de estatística coletiva sobre o desempenho médio de cada uma dessas classes de equivalência.
A análise de pior caso simplesmente analisa a entrada como classes de equivalência individuais e calcula o tempo máximo de execução. A análise de caso médio examina a classe de equivalência trivial, que é única, compreendendo todas as entradas. No artigo de Afshani-Barbay-Chan, seu algoritmo é ideal se a entrada for particionada em classes de permutações (isto é, ordem de desempenho inconsciente).
Não está claro se isso leva a novos paradigmas de análise de algoritmos. O curso de Tim Roughgarden tem excelentes exemplos motivadores e abrange diferentes métodos para analisar algoritmos.
Ananth, muito obrigado pelo link para o curso de Tim. Esse é exatamente o tipo de coisa que eu estava procurando.
— umar 5/09/10
Eu tenho mais dois para a lista, que são um pouco semelhantes.
O(cnnO(1))O(cnnO(1))1<c<21<c<2kkO(2knO(1))O(2knO(1))kknn
O(nlogn+k)O(nlog⁡n+k)kk
Parece com a Análise parametrizada para algoritmos de tempo polinomial e parece que a análise sensível à saída se enquadra nessa categoria.
Serge, obrigado pelo link para o post do Glencora no blog, muitos comentários interessantes por lá.
Há também uma análise de " alta probabilidade " (para algoritmos aleatórios), em que, em qualquer instância, você se preocupa com o desempenho do algoritmo na maioria das vezes, mas pode desistir completamente de uma pequena fração do tempo. Isso é comum na teoria da aprendizagem.
Você pode adicionar aleatoriedade ao seu algoritmo e combiná-lo com todos os itens acima. Em seguida, você obterá, por exemplo, o tempo de execução esperado no pior caso (instância do pior caso, mas em média em todas as seqüências possíveis de lançamentos aleatórios de moedas no algoritmo) e o tempo de execução no pior caso com alta probabilidade (novamente, no caso de pior caso, mas a probabilidade sobre a moeda aleatória vira no algoritmo).
A análise bijetiva é uma maneira de comparar dois algoritmos (Spyros Angelopoulos, Pascal Schweitzer: atualização de paginação e lista sob análise bijetiva. J. ACM 60, 2013): Grosso modo, o algoritmo A é melhor que o algoritmo A nas entradas de comprimento n, se houver um bijeção f das entradas de comprimento n, de modo que A atue na entrada x pelo menos tão bom quanto B em f (x).
Usado para comparar algoritmos online com os algoritmos offline de desempenho. Veja a página da Wikipedia . O problema de atualização de lista é um exemplo clássico.
Mas não é usado para analisar "o tempo de execução de um algoritmo" .
Análise competitiva No algoritmo de substituição de página , um método substitui o outro por menos páginas ausentes. Menos páginas ausentes ilustram "menos tempo de execução". Além disso, a análise competitiva é um método para comparar dois métodos relativamente. Um bom livro de referência é "COMPUTAÇÃO ONLINE E ANÁLISE COMPETITIVA" de Allan Borodin.