Computer science is no more about computers
than astronomy is about telescopes.
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.
Minicurso de Análise de Algoritmos
Outros assuntos: Minicurso de Análise de Algoritmos | Algoritmos de Aproximação | Projeto de Algoritmos em C | Estruturas de Dados | Uma Introdução Sucinta à Teoria dos Grafos | Exercícios de Teoria dos Grafos | Graph Theory Exercises | Fluxo em Redes | Digrafos | Algoritmos em Grafos com Stanford GraphBase | Algoritmos para Grafos via Sedgewick | Algoritmos de Programação Linear | Literate Programming & CWEB | O que é uma prova? | Uma Introdução Sucinta a Algoritmos de Aproximação | Opiniões e notícias