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 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

Material de apoio

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