analise de algoritmos parte 2 - slides

Prévia do material em texto

Teoria
Tamanho da entrada: n 
função de n: crescimento do 
custo (tempo), de acordo 
com a entrada
1
“o crescimento 
é da ordem 
de…”
Mapeamento de algoritmo para 
função matemática
2
n^2 
3/2 n^2 
n^2 + 1000 
n^2/100
3
Ordens mais comuns
n2
n
2n
n
log n
c
1 log n n n2 n3 ... nk ... 2n
constante logarítmica polinomial exponencial
4
Notação assintótica
5
•  Sejam duas funções f(n) e g(n). 
O(g(n)) = {f(n) | ∃c:R, n0:N | 0 ≤ f(n) ≤ cg(n), n ≥ n0} 
•  Exemplo: 2n + 10 é O(n) 
2n + 10 ≤ cn 
(c � 2) n ≥ 10 
n ≥ 10/(c � 2) 
–  escolher c = 3 e n0 = 10 f(n) = Ο(g(n))
Limite assintótico superior
6
•  Sejam duas funções f(n) e g(n). 
O(g(n)) = {f(n) | ∃c:R, n0:N | 0 ≤ f(n) ≤ cg(n), n ≥ n0} 
•  Exemplo: 2n + 10 é O(n) 
2n + 10 ≤ cn 
(c � 2) n ≥ 10 
n ≥ 10/(c � 2) 
–  escolher c = 3 e n0 = 10 f(n) = Ο(g(n))
7
•  Sejam duas funções f(n) e g(n). 
O(g(n)) = {f(n) | ∃c:R, n0:N | 0 ≤ f(n) ≤ cg(n), n ≥ n0} 
•  Exemplo: 2n + 10 é O(n) 
2n + 10 ≤ cn 
(c � 2) n ≥ 10 
n ≥ 10/(c � 2) 
–  escolher c = 3 e n0 = 10 f(n) = Ο(g(n))
8
20 + 10 <= 30 
30 <= 30
40 + 10 <= 60 
50 <= 60
f(n) = Ο(g(n))
f(n) = Ω(g(n))
f(n) = Θ(g(n))
Limite assintótico superior
Limite assintótico inferior
Limite assintótico restrito
9
10
f(n) = Ω(g(n))
Limite assintótico inferior
2n + 10 = Ω(n)
2n + 10 = Ω(n2)
2n + 10 = Ω(logn)
0 <= cn <= 2n + 10 
c = 1 e n0 = 1 
1 <= 12 
10 <= 30 
0 <= cn^2 <= 2n + 10
0 <= clogn <= 2n + 10 
c = 1 e n0 = 2 
1 <= 20 
3 <= 26
11
2n + 10 = Θ(n)
2n + 10 = Θ(n2)
0 <= c1n^2 <= 2n + 10 <= c2n^2
2n + 10 = Θ(logn)
0 <= c1logn <= 2n+10 <= c2logn
f(n) = Θ(g(n))
Limite assintótico restrito
0 <= c1n <= 2n + 10 <= c2n 
c1 = 1, c2 = 12, n0 = 1 
1 < = 12 <= 12 
10 <= 30 <= 120