Upload
ngodang
View
216
Download
0
Embed Size (px)
Citation preview
23/2/2010
1
Análise e Complexidade d Al itde AlgoritmosAnálise de complexidade pessimistaExemplos de análise de algoritmo iterativos e recursivos.
http://www.bolinhabolinha.comProf. Rodrigo [email protected]
Onde Estamos
Ementa• Revisão:
Estrutura de dados;Crescimento de funções;
Indução matemática e métodos matemáticos Indução matemática e métodos matemáticos.
Medidas de complexidade, análise assintótica de limites de complexidades.
Exemplos de análise de algoritmo iterativos e recursivos.
Análise de desempenho de alguns algoritmos clássicos de busca e ordenação.
Introdução aos principais paradigmas do projeto de algoritmos.
Complexidade do Problema: Limites de Complexidade, Intratabilidade, Classes P, NP, problemas Np completos e NP-difíceis.
23/2/2010
2
Relembrando
notação definição
Objeto de Estudo
Serão estudadas as operações básicas de algoritmos
Utilizaremos notações de complexidade Utilizaremos notações de complexidade pessimista
23/2/2010
3
Preliminares
Conceitos Preliminares
O desempenho de um algoritmo pode ser obtido a partir dos desempenhos das suas várias partes
A complexidade da mesma maneira
Componentes de um algoritmo• conjuntivas: sempre executada em qualquer execução do
algoritmo i := i + 1;
• disjuntiva: são executadas em algumas execuções do l i d d d d l d dalgoritmo, dependendo do valor da entrada se i<>j então
i := i+1;senão
I := i-1;
23/2/2010
8
Exemplos
Conceitos auxiliares
reduzir a complexidade do algoritmo às ordens de suas partes• conjuntivasconjuntivasabsorção
– A complexidade de uma parte pode ser absorvida pela complexidade de outra parte: a idéia é que a segunda domina a primeira, dando a contribuição principal para a soma.
– Uma complexidade é absorvida por outra, por exemplo, se ambas são polinômios na mesma variável. Nesse caso, a complexidade de menor grau é absorvidacomplexidade de menor grau é absorvida.
• disjuntivasmáximo assintótico
23/2/2010
10
Máximo assintótico (em ordem)
Equações de complexidade pessimista
metodologia• complexidade com base na sua estrutura complexidade de suas componentesp p
– devemos saber como combinar estas complexidades
analisaremos a complexidade das principais estruturas algoritmas
23/2/2010
11
Atribuição
A atribuição v := e pode ser:• atribuição simples, valor para v;
• atribuição complexa, atualização de uma matrizatribuição complexa, atualização de uma matriz
• inserção de um nodo no grafo
• inserção de um elemento em um conjunto
“e” pode ser uma expressão ou função, e deve ser avaliado
Atribuição