Análise de Algoritmos

A análise de algoritmos estuda a correção e o desempenho de algoritmos.  Em outras palavras, a análise de algoritmos procura respostas para perguntas do seguinte tipo:  Este algoritmo resolve o meu problema?  Quanto tempo o algoritmo consome para processar uma 'entrada' de tamanho n?.  (A resposta à segunda pergunta é necessariamente um tanto grosseira, algo como o consumo de tempo é proporcional a n² log n no pior caso.)

Além disso, a análise de algoritmos estuda certos paradigmas (como divisão e conquista, programação dinâmica, gula, busca local, aproximação, etc.) que se mostraram úteis na criação de algoritmos para diversos problemas computacionais.

A análise de algoritmos foi inventada e difundida por D.E. Knuth (veja a série de livros The Art of Computer Programming). Knuth foi o pai da ideia de prever o tempo de execução e o consumo de espaço de um algoritmo.

Material didático

• Aulas de Análise de Algoritmos
• Dicionário de termos técnicos
• Índice remissivo
• Livrinho Minicurso de Análise de Algoritmos

Material de apoio

• Alguns livros
• Alguns recursos na rede WWW
• O que é uma prova matemática?
• Repositório de exercícios de Análise de Algoritmos
• Wikipedia: List of terms relating to algorithms and data structures
• O que eles dizem: citações relativas a algoritmos e sua análise