Algoritmos otimos

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (857 palavras )
  • Download(s) : 0
  • Publicado : 4 de julho de 2011
Ler documento completo
Amostra do texto
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çõessobre 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 parareproduzir experimentos (ambientes multitarefa, compiladores, sistemas operacionais, etc).
* Necessidade de implementação do algoritmo.
Métodos Analíticos
* Aproximações através de modelosmatemá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 deexecuçã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 classesimportantes 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 deOrdem 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
* 2000anos ~ 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...
tracking img