Algoritmos otimos

Revisão e Introdução

Tipos de dados
 Simples: Caracteres (char), Inteiros (int), Reais (float), Booleanos (bool), ...
 Compostos: Cadeias, Vetores, ... * Operação: Aritméticas, Inserção, Remoção, Ordenação, Máximo, Mínimo, Inversão, Transposição, etc.
Tipos abstratos de dados
 Separação conceitual entre implementação e utilização de estruturas de dados
 Dados e operações sobre os dados encapsuladas em um único componente
 E.g. Listas, Pilhas, Árvores, Números Complexos, ...

Avaliação de desempenho de um algoritmo
Métodos Empíricos * Dificuldade para reproduzir experimentos (ambientes multitarefa, compiladores, sistemas operacionais, etc). * Necessidade de implementação do algoritmo.
Métodos Analíticos * Aproximações através de modelos matemáticos. * Não depende de implementações. * Resultados podem não ser relevantes na prática.
Análise de complexidade de algoritmos (introdução bastante informal) * Estimativa do tempo de execução (passos - operações atômicas) * Tamanho de um problema * Pior caso, melhor caso e caso médio * Análise assintótica * Ordem O, Omega e Theta (link interessante) * Algumas classes importantes de funções: * O(1) - Constante * O(logn) - Logarítmico * O(n) - Linear ou Polinomial de Ordem 1 * O(n²) - Polinomial de Ordem 2 * O(n³) - Polinomial de Ordem 3 * O(2n) - Exponencial Algoritmo | Complexidade | 2 | 10 | 100 | 10.000 | A | f(n)=1000 | 1000 | 1000 | 1000 | 1000 | B | f(n)=200logn | 200 | 600 | ~ 1.200 | ~ 2.600 | C | f(n)=50n | 100 | 500 | 5.000 | 500.000 | D | f(n)=n² | 4 | 100 | 10.000 | 100.000.000 | E | f(n)=2n | 4 | 1024 | 1030 | 103010 |
Observações
* 1 dia ~ 1014ns * 1 ano ~ 1016ns * 2000 anos ~ 1019ns
Gráfico ilustrando comportamento assintótico de certas classes de funções

* Para gerar o gráfico acima utilizando o SciLab faça download do arquivo assintotico.sci e