Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos Thomas H.Cormen - Coggle Diagram
Algoritmos
Thomas H.Cormen
2-Análise de Algoritmos
Preve recursos que o algoritmo necessita
Frequentemente usado para medir o tempo de computação
Analisando vários algoritmos canditados
Considera o modelo generico de RAM
sem operações concorrentes
usa numeros inteiros e pontos flutuantes p/ armazenar dados
inteiros usa
c lg n bits
p/ constante c>= 1
instruições aritméticas... condicionais etc..
não modela a hierarquia da memória
os de hierarquia são bem mais complexos!
Já da exelentes previsões no desempenho
Análise da ordenação por inserção
O tempo gasto por um algoritmo
cresce com o T da entrada
normalmente o Tempo de execução e dado pelo T da entrada
T da entrada depende do problema estudado!
Tempo de execção
Passos executados
o
laço
executa 1x a mais do que o escopo
t(n) = tempo de execução
Pega-se o maior valor na função
algoritmos: insertion-sort O(n^2)...Merge t(n) = O(n)
Análise do pior caso e do caso médio
pior caso é o tempo de execução mais longo
3 razões para orientações
estabelece o limite superior
ocorre com bastante frequência
caso médio por vez pode ser pior que o pior caso
Ordem de Crescimento
Ordem de cresciment ou taxa de crescimento
Um algoritmo ser mais rápido que outro é essencial que sua taxa de crescimento seja menor que seu concorrente.
Projeto de Algoritmos
Divisão e Conquista
3 passos:
Conquista
Combinação
Divisão
Ordenação por intercalação
Merge sort
funciona bem quando é par
potência de 2
leva o tempo O(n log n)
Arvoré de recurssão
tem lg n +1 níveis
3-Crescimento de Função
Para entradas suficientemente grandes estamos estudando
a eficiência
Assintótica
Notação Asssintótica
Conjunto com dominio dos números naturais
N = {0,1,2,3...}
Coviniente para determinar o tempo
t(n) do pior caso
Tamanhos de entradas inteiras
Pode aplica funções medir a quantidade
de espaço dos algoritmos
Notação Assintótica, Funções e tempos de execução
Notação Θ
g(n) é um limite assintoticamente restrito de f(n)
Exige que sejá assintóticamente não negativo
f(n) percente ao O(g(n)
Onde existe costantes
c1 e c2
-> onde ele possa
se encaixada
entre eles
"f(n) e O(g(n)" ,"f n = O(g(n)" representar pertinência
O(g(n)) =
{ f(n): Existe costantes c1 c2 e n0 onde,
0 <= c1g(n) <= f(n) <= c2gn para todo n> n0
}
Notação O
Limite Superior
Usamos quando temos apenas um limite superior
Lê-se o
''Ó grande de g de n''
ou
"ó de g de n"
O(g(n)) =
{ f(n): Exites Constante c e n0 onde,
0 <= f(n) <= cg(n) para todo n >= n0
}
f(n) = O(g(n)) p/ indicar pertinência
Θ está contido em O
n = O(n**2)
descreve limites assintoticamentes justos
aquilo que definimos usando a
Notação Θ
Notação Ω
Limite Inferior
Ω (g(n) =
{ f(n): Existe Constantes positivas c e n0 onde,
0 <= cg(n <= f(n) para todo n >= n0
}
Lê-se
''ômega grande de g de n''
ou
''ômega de g de n''
Teorema:
para quais quer f(n) e g(n), onde
f(n)
=
Θ(g(n))
se somente se,
f(n) = O(g()n)
e
f(n) = Ω(g(n))
da pra ter o
limite assintóticamente superior e inferior apartir do limite assintoticamente preciso
e virse e versa
Notações Assintóticas em equações e desigualdades
Se a notação assintótica aparecer do lado esquerdo
o lado direito oferece mais detalhe
se o interesse é apenas no comportamento assintótico de T(n)
não tem sentido especificar os termos de ordem mais baixa, entende-se que eles estão incluido na f() anônima detonada pelo termo Θ(n)
quando a notação assintótica está sozinha
não está dentro de uma fórmula maior do lado direito de uma equação(desigualdade)
exemplo: n = Θ(n**2)
1 more item...
2(n
2) +3n +1 = 2(n
2) + Θ(n)
onde f(n) e alguma f() no conjunto o(n)
Pórem em geral Quando a notação assintótica
Representa uma
f() anônima
onde não nos preocupamos em nomealas
1 more item...
Notação o e w
o - lê-se o pequeno de g de n
ta para notação O
diferença entra O - f(n) < cg(n) para todo n > n0
w - lê-se ômega pequeno de g de n
ta para notação Ω
diferença entre Ω - cg(n) < fn() para todo n> n0
Se aplica a toda entrada, =! Θ
Função assintoticamente positiva
é f() positiva para todo
n
suficientemente grande
O(1) quando o grau é 0 - n**0
indica uma constante ou uma f() constante
Limites assintóticamente justos
NP-COMPLETUDE