Análise de Algoritmos - Aula 03 (Guilherme)

Prévia do material em texto

Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Roteiro da Aula 3
1 Notac¸a˜o Assinto´tica
Termos de menor ordem
Constantes multiplicativas
Por que Comportamento Assinto´tico?
2 Exerc´ıcios
3 Relac¸o˜es de Recorreˆncia
Provando por Induc¸a˜o
Poteˆncias de 2 ou Piso/Teto?
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Uso de notac¸a˜o assinto´tica em equac¸o˜es
• O que significa f(n) = 2n4 + O(n)?
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Uso de notac¸a˜o assinto´tica em equac¸o˜es
• O que significa f(n) = 2n4 + O(n)?
• f(n) e´ exatamente 2n4 + h(n), onde h(n) e´ alguma
func¸a˜o O(n);
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Uso de notac¸a˜o assinto´tica em equac¸o˜es
• O que significa f(n) = 2n4 + O(n)?
• f(n) e´ exatamente 2n4 + h(n), onde h(n) e´ alguma
func¸a˜o O(n);
• O que significa 2o(n)?
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Uso de notac¸a˜o assinto´tica em equac¸o˜es
• O que significa f(n) = 2n4 + O(n)?
• f(n) e´ exatamente 2n4 + h(n), onde h(n) e´ alguma
func¸a˜o O(n);
• O que significa 2o(n)?
• Igualmente, 2h(n), onde h(n) e´ alguma func¸a˜o o(n);
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Uso de notac¸a˜o assinto´tica em equac¸o˜es
• O que significa f(n) = 2n4 + O(n)?
• f(n) e´ exatamente 2n4 + h(n), onde h(n) e´ alguma
func¸a˜o O(n);
• O que significa 2o(n)?
• Igualmente, 2h(n), onde h(n) e´ alguma func¸a˜o o(n);
• O que significa 2n2 +Θ(n) = Θ(n2)?
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Uso de notac¸a˜o assinto´tica em equac¸o˜es
• O que significa f(n) = 2n4 + O(n)?
• f(n) e´ exatamente 2n4 + h(n), onde h(n) e´ alguma
func¸a˜o O(n);
• O que significa 2o(n)?
• Igualmente, 2h(n), onde h(n) e´ alguma func¸a˜o o(n);
• O que significa 2n2 +Θ(n) = Θ(n2)?
• 2n2 somado a qualquer func¸a˜o que seja Θ(n) resulta numa
func¸a˜o que e´ Θ(n2).
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Termos de menor ordem
• Exemplo: 3n3 + 2n2 + (log n)5 + 5 = O(n3)
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Termos de menor ordem
• Exemplo: 3n3 + 2n2 + (log n)5 + 5 = O(n3)
• Em geral:
f(n) + O(f(n)) + O(f(n)) + O(f(n)) = O(f(n))
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Termos de menor ordem
• Exemplo: 3n3 + 2n2 + (log n)5 + 5 = O(n3)
• Em geral:
f(n) + O(f(n)) + O(f(n)) + O(f(n)) = O(f(n))
f(n) + h1(n) + h2(n) + h3(n)
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Termos de menor ordem
• Exemplo: 3n3 + 2n2 + (log n)5 + 5 = O(n3)
• Em geral:
f(n) + O(f(n)) + O(f(n)) + O(f(n)) = O(f(n))
f(n) + h1(n) + h2(n) + h3(n) ≤ f(n) + c1f(n) + c2f(n) + c3f(n)
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Termos de menor ordem
• Exemplo: 3n3 + 2n2 + (log n)5 + 5 = O(n3)
• Em geral:
f(n) + O(f(n)) + O(f(n)) + O(f(n)) = O(f(n))
f(n) + h1(n) + h2(n) + h3(n) ≤ f(n) + c1f(n) + c2f(n) + c3f(n)
≤ (1 + c1 + c2 + c3)
| {z }
c
f(n)
para todo n ≥ max{n1, n2, n3}
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Constantes multiplicativas
• Direto da definic¸a˜o de O e Ω, temos:
• cf(n) = Θ(f(n)), para qualquer constante c > 0;
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Constantes multiplicativas
• Direto da definic¸a˜o de O e Ω, temos:
• cf(n) = Θ(f(n)), para qualquer constante c > 0;
• A notac¸a˜o assinto´tica compara duas func¸o˜es levando em
conta apenas seus crescimentos assinto´ticos, o que
desconsidera constantes multiplicativas e termos de menor
ordem!
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Termos de
menor ordem
Constantes
multiplicativas
Por que
Comportamento
Assinto´tico?
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Computador melhor ou Algoritmo melhor?
Tempos de execuc¸a˜o, em segundos, para n = 1000
1000 passos/s 2000 4000 8000
log n 0.010 0.005 0.003 0.001
n 1 0.5 0.25 0.125
n log n 10 5 2.5 1.25
n1.5 32 16 8 4
n2 1000 500 250 125
n3 1000000 500000 250000 125000
1.1n 1039 1039 1038 1038
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Exerc´ıcios
• Mostre que n
2
log n = ω(n(log n)
3);
• Quem e´ ω(de quem)? n2n e 3n;
• Mostre que, se f(n) e´ um polinoˆmio em n, enta˜o
log(f(n)) = O(logn).
• Verdadeiro ou falso? f(n) = Θ(f(n + 1))
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
• Resolvendo uma instaˆncia de tamanho n a partir da
soluc¸a˜o de uma de tamanho n− 1:
• T (n) = T (n− 1) + n, com T (1) = 1;
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
• Resolvendo uma instaˆncia de tamanho n a partir da
soluc¸a˜o de uma de tamanho n− 1:
• T (n) = T (n− 1) + n, com T (1) = 1;
• Resolvendo uma instaˆncia de tamanho n a partir da
soluc¸a˜o de duas de tamanho n/2:
• T (n) = 2T (n2 ) + n, com T (1) = 1;
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Me´todo da Iterac¸a˜o
T (n) = T (n− 1) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıciosRelac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Me´todo da Iterac¸a˜o
T (n) = T (n− 1) + n
= T (n− 2) + (n− 1) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Me´todo da Iterac¸a˜o
T (n) = T (n− 1) + n
= T (n− 2) + (n− 1) + n
= T (n− 3) + (n− 2) + (n− 1) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Me´todo da Iterac¸a˜o
T (n) = T (n− 1) + n
= T (n− 2) + (n− 1) + n
= T (n− 3) + (n− 2) + (n− 1) + n
...
= T (n− k) + (n− (k − 1)) + · · ·+ (n− 1) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Me´todo da Iterac¸a˜o
T (n) = T (n− 1) + n
= T (n− 2) + (n− 1) + n
= T (n− 3) + (n− 2) + (n− 1) + n
...
= T (n− k) + (n− (k − 1)) + · · ·+ (n− 1) + n
T (n− k) sera´ 1 quando n− k = 1, pois T (1) = 1
Enta˜o, substituindo k = n− 1 ...
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Me´todo da Iterac¸a˜o
T (n) = T (n− 1) + n
= T (n− 2) + (n− 1) + n
= T (n− 3) + (n− 2) + (n− 1) + n
...
= T (n− k) + (n− (k − 1)) + · · ·+ (n− 1) + n
T (n− k) sera´ 1 quando n− k = 1, pois T (1) = 1
Enta˜o, substituindo k = n− 1 ...
T (n) = T (n− (n− 1)) + (n− (n− 2)) + · · ·+ (n− 1) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Me´todo da Iterac¸a˜o
T (n) = T (n− 1) + n
= T (n− 2) + (n− 1) + n
= T (n− 3) + (n− 2) + (n− 1) + n
...
= T (n− k) + (n− (k − 1)) + · · ·+ (n− 1) + n
T (n− k) sera´ 1 quando n− k = 1, pois T (1) = 1
Enta˜o, substituindo k = n− 1 ...
T (n) = T (n− (n− 1)) + (n− (n− 2)) + · · ·+ (n− 1) + n
= T (1) + 2 + 3 + 4 + · · ·+ (n− 1) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Me´todo da Iterac¸a˜o
T (n) = T (n− 1) + n
= T (n− 2) + (n− 1) + n
= T (n− 3) + (n− 2) + (n− 1) + n
...
= T (n− k) + (n− (k − 1)) + · · ·+ (n− 1) + n
T (n− k) sera´ 1 quando n− k = 1, pois T (1) = 1
Enta˜o, substituindo k = n− 1 ...
T (n) = T (n− (n− 1)) + (n− (n− 2)) + · · ·+ (n− 1) + n
= T (1) + 2 + 3 + 4 + · · ·+ (n− 1) + n
= 1 + 2 + 3 + 4 + · · ·+ (n− 1) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Resolvendo a somato´ria
T (n) = 1 + 2 + 3 + 4 + · · ·+ (n− 1) + n
enta˜o
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Resolvendo a somato´ria
T (n) = 1 + 2 + 3 + 4 + · · ·+ (n− 1) + n
enta˜o
2T (n) = 1 + 2 + 3 + 4 + · · ·+ (n− 1) + n
+ n + (n− 1) + (n− 2) + (n− 3) + · · ·+ 2 + 1
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Resolvendo a somato´ria
T (n) = 1 + 2 + 3 + 4 + · · ·+ (n− 1) + n
enta˜o
2T (n) = 1 + 2 + 3 + 4 + · · ·+ (n− 1) + n
+ n + (n− 1) + (n− 2) + (n− 3) + · · ·+ 2 + 1
2T (n) = n(n + 1)
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Resolvendo a somato´ria
T (n) = 1 + 2 + 3 + 4 + · · ·+ (n− 1) + n
enta˜o
2T (n) = 1 + 2 + 3 + 4 + · · ·+ (n− 1) + n
+ n + (n− 1) + (n− 2) + (n− 3) + · · ·+ 2 + 1
2T (n) = n(n + 1)
T (n) =
1
2
n(n + 1)
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
Resolvendo a somato´ria
T (n) = 1 + 2 + 3 + 4 + · · ·+ (n− 1) + n
enta˜o
2T (n) = 1 + 2 + 3 + 4 + · · ·+ (n− 1) + n
+ n + (n− 1) + (n− 2) + (n− 3) + · · ·+ 2 + 1
2T (n) = n(n + 1)
T (n) =
1
2
n(n + 1)
T (n) = Θ(n2)
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Provando por Induc¸a˜o
O me´todo da iterac¸a˜o na˜o e´ rigoroso!
• A rigor, o que precisamos e´ uma prova por induc¸a˜o:
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Provando por Induc¸a˜o
O me´todo da iterac¸a˜o na˜o e´ rigoroso!
• A rigor, o que precisamos e´ uma prova por induc¸a˜o:
T (1) ≤ c12
︸ ︷︷ ︸
Base da Induc¸a˜o
T (n− 1) ≤ c(n− 1)2
︸ ︷︷ ︸
Hipo´tese da Induc¸a˜o
=⇒ T (n) ≤ cn2
︸ ︷︷ ︸
Tese da Induc¸a˜o
︸ ︷︷ ︸
Passo da Induc¸a˜o
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
T (n) = 2T (
n
2
) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
T (n) = 2T (
n
2
) + n
= 2(2T (
n
4
) +
n
2
) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
T (n) = 2T (
n
2
) + n
= 2(2T (
n
4
) +
n
2
) + n
= 2(2(2T (
n
8
) +
n
4
) +
n
2
) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
T (n) = 2T (
n
2
) + n
= 2(2T (
n
4
) +
n
2
) + n
= 2(2(2T (
n
8
) +
n
4
) +
n
2
) + n
...
= 2kT (
n
2k
) + n + · · ·+ n + n
︸ ︷︷ ︸
k termos
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
T (n) = 2T (
n
2
) + n
= 2(2T (
n
4
) +
n
2
) + n
= 2(2(2T (
n
8
) +
n
4
) +
n
2
) + n
...
= 2kT (
n
2k
) + n + · · ·+ n + n
︸ ︷︷ ︸
k termos
T ( n
2k
) sera´ 1 quando n
2k
= 1, pois T (1) = 1
Enta˜o, substituindo k = log n ...
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de RecorreˆnciaT (n) = 2log nT (1) + n + · · ·+ n + n
︸ ︷︷ ︸
k termos
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
T (n) = 2log nT (1) + n + · · ·+ n + n
︸ ︷︷ ︸
k termos
= n log n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Relac¸o˜es de Recorreˆncia
T (n) = 2log nT (1) + n + · · ·+ n + n
︸ ︷︷ ︸
k termos
= n log n
T (n) = Θ(n logn)
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Poteˆncias de 2 ou Piso/Teto?
• Por enquanto, mostramos T (n) = O(n logn) para
poteˆncias de 2: T (2i) ≤ c2i log 2i, para todo i ≥ i0
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Poteˆncias de 2 ou Piso/Teto?
• Por enquanto, mostramos T (n) = O(n logn) para
poteˆncias de 2: T (2i) ≤ c2i log 2i, para todo i ≥ i0
• Mas, na verdade, a recorreˆncia e´ T (n) = 2T (⌈n2 ⌉) + n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Poteˆncias de 2 ou Piso/Teto?
• Por enquanto, mostramos T (n) = O(n logn) para
poteˆncias de 2: T (2i) ≤ c2i log 2i, para todo i ≥ i0
• Mas, na verdade, a recorreˆncia e´ T (n) = 2T (⌈n2 ⌉) + n
• Mas note que sempre existe uma poteˆncia de 2 entre
qualquer n e 2n: n < 2k < 2n
Ana´lise de
Algoritmos
113859
Aula 3
Roteiro
Notac¸a˜o
Assinto´tica
Exerc´ıcios
Relac¸o˜es de
Recorreˆncia
Provando por
Induc¸a˜o
Poteˆncias de 2
ou Piso/Teto?
Poteˆncias de 2 ou Piso/Teto?
• Por enquanto, mostramos T (n) = O(n logn) para
poteˆncias de 2: T (2i) ≤ c2i log 2i, para todo i ≥ i0
• Mas, na verdade, a recorreˆncia e´ T (n) = 2T (⌈n2 ⌉) + n
• Mas note que sempre existe uma poteˆncia de 2 entre
qualquer n e 2n: n < 2k < 2n
Assim,
T (n) ≤ T (2k)
≤ c2k log 2k
≤ c2n log 2n
≤ c2n logn2
≤ 4c
︸︷︷︸
c1
n logn
	Roteiro
	Notação Assintótica
	Termos de menor ordem
	Constantes multiplicativas
	Por que Comportamento Assintótico?
	Exercícios
	Relações de Recorrência
	Provando por Indução
	Potências de 2 ou Piso/Teto?