Análise de Algoritmos

Computer science is no more about computers
than astronomy is about telescopes.

Edsger W. Dijkstra

 

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

 




 

Busca no sítio Análise de Algoritmos

Valid HTML 4.01 Strict Valid CSS!

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  |  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?  |  Opiniões e notícias