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 vários 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

Material de apoio

Dicionário de termos técnicos
Índice remissivo
Alguns livros
Alguns recursos na rede WWW
O que é uma prova matemática?
O que eles dizem: citações relativas a algoritmos e sua análise
Exames de Qualificação em Análise de Algoritmos no IME-USP

Acredito que o material deste sítio pode ser útil nos cursos de graduação e pós-graduação em Ciência da Computação e Engenharia de Computação. Também pode ser usado por quem esteja se preparando para o POSCOMP (exame nacional para ingresso na pós-graduação em Computação).