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:
Projeto de Algoritmos em C |
Livro Algoritmos em C
|
Algorithms Design in C |
Desenvolvimento de Algoritmos |
Estruturas de Dados |
Literate Programming & CWEB |
O que é uma prova? |
Uma Introdução Sucinta à Teoria dos Grafos |
Exercícios de Teoria dos Grafos |
Graph Theory Exercises |
Digrafos |
Algoritmos em Grafos com Stanford GraphBase |
Algoritmos para Grafos via Sedgewick |
Teoria dos Grafos via Diestel |
Minicurso de Análise de Algoritmos |
Algoritmos de Programação Linear |
Otimização Combinatória |
Algoritmos de Aproximação |
A conjectura de Woodall