mc458-complexidade-notacao-assintotica

Prévia do material em texto

MC458 - Complexidade e Notação Assintótica
Instituto de Computação - Unicamp
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 1 / 59
Multiplicação de inteiros
Problema
Problema: Ler inteiros m e n e calcular m · n. Assuma que não há
instrução de multiplicação dispońıvel.
m · n = m + m + · · ·+ m︸ ︷︷ ︸
n vezes
1 load r0, 0 carrega 0 no reg. r0
2 read r1 carrega m no reg. r1
3 read r2 carrega n no reg. r2
4 jmpz r2, 8 jump para linha 8 se r2 = 0
5 add r0, r0, r1 adiciona r0 e r1, armazena o resultado em r0
6 sub r2, r2, 1 decrementa r2
7 jmp 4 jump para linha 4
8 write r0 escreve o valor de r0 na sáıda
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 2 / 59
Multiplicação de inteiros
Complexidade I
Supondo que cada instrução tem custo 1, a complexidade é:
Custo
1 load r0, 0 1
2 read r1 1
3 read r2 1
4 jmpz r2, 8 n + 1
5 add r0, r0, r1 n
6 sub r2, r2, 1 n
7 jmp 4 n
8 write r0 1
T (n) = 4n + 5
Se invertermos n e m, calculando m · n:
T (m) = 4m + 5
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 3 / 59
Multiplicação de inteiros
Complexidade II
Supondo que o custo é proporcional ao comprimento (em bits) do valor
armazenado, a complexidade é:
Custo
1 load r0, 0 1
2 read r1 lgm
3 read r2 lg n
4 jmpz r2, 8 lg n + lg(n − 1) + · · ·+ lg 2 + 1
5 add r0, r0, r1 lgm + lg(2m) + · · ·+ lg(nm)
6 sub r2, r2, 1 lg(n + 1) + · · ·+ lg 1
7 jmp 4 n
8 write r0 lg(mn)
T (n)
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 4 / 59
Multiplicação de inteiros
Complexidade II (Cont.)
T (n) = 1 + lg(mn) +
n∑
i=1
lg i + 1 +
n∑
i=1
lg(im) +
n+1∑
i
lg i + n + lg(mn)
= 2 + n + 2 lg(mn) + lg(n!) + lg(m · 2m · · · nm) + lg(n!)
= 2 + n + 2 lg(mn) + 2 lg(n!) + lg(mnn!)
= 2 + n + 2 lg(mn) + 2 lg(n!) + n lg(m) + lg(n!)
Usando a aproximação de Stirling, n! ≈
(n
e
)n√
2πn
≈ 2 + n + 2 lg(mn) + 3n lg n + n lgm
≈ 2 + n + 3n lg n + n lgm
O cálculo da complexidade fica bem mais complicado.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 5 / 59
Análise de Algoritmos
Problemas
Quanto usa de um recurso (tempo/memória), depende das entradas.
Problemas:
1 Expressão exata é complexa e dif́ıcil de obter.
2 Como medir “tamanho” da entrada?
3 Entradas de mesmo tamanho, mas com valores diferentes, podem
usar mais ou menos recursos.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 6 / 59
Análise de Algoritmos
Problemas (Cont.)
1 Expressão exata é complexa e dif́ıcil de obter.
I Solução exata não é necessária. Pode-se ignorar:
F constantes (comparando algoritmos);
F termos de crescimento menor (“embutidos” nos termos principais);
F casos particulares iniciais (comportamento assintótico)
Alg1 : T1(n) = 100n→≤ k1n(k1 = 1000)
Alg2 : T2(n) = 6n
2 + 300→≤ k2n2(k2 = 10, n ≥ 8)
Alg1 “cresce” na razão de k1n.
Alg2 “cresce” na razão de k2n
2.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 7 / 59
Análise de Algoritmos
Problemas (Cont.)
0
20000
40000
60000
80000
100000
120000
140000
160000
180000
200000
0 20 40 60 80 100 120 140
te
m
p
o
n
T1(n)
T2(n)
Figura 1: Assintoticamente, Alg1 é “melhor”.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 8 / 59
Análise de Algoritmos
Problemas (Cont.)
2 Como medir o “tamanho” da entrada?
Soluções:
I no. de elementos.
Ex: vetor de n números inteiros ⇒ tamanho n.
I no. de bits para armazenar a entrada.
Ex: vetor de n números de tamanho ≤ k ⇒ n lg k (maior precisão, mas
envolve limite k).
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 9 / 59
Análise de Algoritmos
Problemas (Cont.)
3 Entradas de mesmo tamanho, mas com valores diferentes podem usar
mais ou menos recursos. Soluções:
1 Avaliar uso de recursos no pior caso.
2 Avaliar uso de recursos no caso médio
F Precisa de uma distribuição de probabilidades para as instâncias de
entrada.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 10 / 59
Notação Assintótica: O, Ω, Θ
Para lidar com o problema (1).
Sejam f e g funções (crescentes) que medem gasto de recursos.
1 g é O(f ) sse existir constantes c e n0 tais que g(n) ≤ c f (n), para
todo n ≥ n0.
0
50
100
150
200
250
300
n0
c·f(n)
g(n)
Figura 2: c f “domina” g a partir de n0.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 11 / 59
Notação Assintótica: O, Ω, Θ (Cont.)
Exemplos:
1 g(n) = 1000n
f (n) = 5n2 + 300.
g é O(f ), pois:
g(n) ≤ cf (n) ∀n ≥ n0, se c = 1 e n0 = 200
ou se c = 20 e n0 = 10.
2 g(n) = 5n2 + 40
g é O(n2), é O(n3), é O(2n),é O(n!)...
cotas superiores mais frouxas
−−−−−−−−−−−−−−−−−−−−−−→
cotas superiores mais justas
←−−−−−−−−−−−−−−−−−−−−−
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 12 / 59
Notação Assintótica: O, Ω, Θ (Cont.)
Exemplos:
1 p(n) ≡ polinômio de grau k (k ≥ 0)
p(n) é O(nk)
p(n) =
∑k
i=0 ain
i ≤ (k + 1)a︸ ︷︷ ︸
c
nk , onde a é o máximo dentre os ai s
∴ p(n) ≤ cnk ,∀n ≥ 0
c = max{|a0|, |a1|, ..., |ak |} > 0.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 13 / 59
Notação Assintótica: O, Ω, Θ (Cont.)
Usando limite:
Se f (n)>0 e g(n)>0 são tais que lim
n→∞
f (n)
g(n)
=L<∞ então f (n) é O(g(n)).
Limite: ∀� > 0, ∃n� tal que −� < f (n)g(n) − L < �, ∀n ≥ n�.
∴ f (n) < (L + �)g(n), ∀n ≥ n�.
Exemplo: Seja f crescente e diferenciável com lim
n→∞
f (n) =∞ e constantes
c > 0 e a > 1. Se F (n) = [f (n)]c e G (n) = af (n) então F (n) é O(G (n)).
Considere n0 suficientemente grande para que f (n) > 0, ∀n ≥ n0.
lim
n→∞
[f (n)]c
af (n)
= lim
n→∞
c [f (n)]c−1
ln(a)af (n)
(obtida usando regra de L’Hôpital)
... reaplicando enquanto expoente de f for positivo
= lim
n→∞
c(c − 1) · · · (c − k + 1)[f (n)]c−k
(ln(a))kaf (n)
= 0 ∴ [f (n)]c é O(af (n))
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 14 / 59
Notação Assintótica: O, Ω, Θ (Cont.)
Exemplos:
n = 1000
Alg. 1000 passos/seg. 8000 passos/seg
lg n 0.01 0.001
n 1 0.125
n1.5 32 4
n3 106 125 · 103
1.1n 1039 1038
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 15 / 59
Notação Assintótica: O, Ω, Θ (Cont.)
II g é Ω(f ) sse existe c > 0 e n0 ≥ 1 tais que:
g(n) ≥ cf (n), para n ≥ n0
⇒ f é dominada por g a partir de n0.
Exemplos:
I n2 é Ω(n2 − 100), pois n2 ≥ 1 · (n2 − 100) , para n ≥ 1
I n2 é Ω(n0.8), pois n2 ≥ 1 · n0.8, para n ≥ 1
I n3 é Ω(n2), é Ω(n), é Ω(log n), ...
cotas inferiores mais fracas−−−−−−−−−−−−−−−−−−−−→
cotas inferiores mais justas
←−−−−−−−−−−−−−−−−−−−−
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 16 / 59
Notação Assintótica: O, Ω, Θ (Cont.)
III g é Θ(f ) sse existem c1, c2 > 0 e n0 ≥ 1 tais que:
c2f (n) ≤ g(n) ≤ c1f (n), n ≥ n0
f e g “crescem na mesma razão” a partir de n0
⇒ g é Θ(f ) sse g é O(f ) e g é Ω(f )
Exemplo:
I 5n lg n + 3 é Θ(n lg n)
n lg n é cota justa para 5n lg n + 8: só diferem por uma constante
multiplicativa e a partir de um certo n ≥ n0.
∴ para n grande, 5n lg n + 3 é ≈ proporcional à n lg n.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 17 / 59
Notação Assintótica: O, Ω, Θ (Cont.)
IV Cotas estritas:
1 Superior: g é o(f ) sse para todo c > 0, existe n0 tal que
g(n) < cf (n),∀n ≥ n0. Note que se f > 0, lim
n→∞
g(n)/f (n) = 0
Exemplo:
2n2 + 1 é O(n3), mas não é o(n2), pois não temos 2n2 + 1 < cn2 para
todo c (p. ex., não vale para c = 1).
2 Inferior: g é ω(f ) sse para todo c > 0, existe n0 tal que
g(n) > cf (n),∀n ≥ n0.
n3 é ω(n2 log n).
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 18 / 59
Obtenção de cotaspara somatórios
1 Método direto: S(n) =
n∑
i=0
2i
S(n) = 2n+1 − 1 e 2n+1 ≤ 2n+1 = 2 · 2n ∴ S(n) é Θ(2n)
2 Método do deslocamento: S(n) =
n∑
i=1
i2i
S(n) = 1 · 2 + 2 · 22 + 3 · 23 + ...+ (n − 1)2n−1 + n2n
2S(n) = 1 · 22 + 2 · 23 + ...+ (n − 2)2n−1 + (n − 1)2n + n2n+1
2S(n)− S(n) = n2n+1 − 2n − 2n−1 − ...− 23 − 22 − 2
⇒ S(n) = n2n+1 −
n∑
i=1
2i = n2n+1 − (2n+1 − 2)
= (n − 1)2n+1 + 2 ∴ S(n) é Θ(n2n)
Exerćıcio: Calcule (a) S(n) =
∑n
i=1 ia
i para a > 0 e
(b) S =
∑∞
i=1 ia
i para 0 < a < 1.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 19 / 59
Exemplo de obtenção de cotas (Cont.)
3 Método indutivo: mostrar que
∑n
i=0 3
i é O(3n).
Preciso de c > 0 e n0 ≥ 0 tais que
∑n
i=0 3
i ≤ c3n, n ≥ n0.
⇒ escolha de c e n0 ainda em aberto.
Base: 30 ≤ c30 (quando n = 0).
∴ preciso de c ≥ 1.
H.I.:
∑n
i=0 3
i ≤ c3n.
Passo indutivo:
n+1∑
i=0
3i =
n∑
i=0
3i + 3n+1 ≤ c3n + 3n+1,por H.I.
= c3n+1 (1/3 + 1/c)︸ ︷︷ ︸
d
.
Preciso d ≤ 1⇒ 1/3 + 1/c ≤ 1⇔ c ≥ 3/2
Base + passo indutivo se c ≥ 1 e c ≥ 3/2.
∴ Escolho c = 1,5 e n0 = 0.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 20 / 59
Exemplo de obtenção de cotas (Cont.)
4 Somatórios: cota superior quando razão entre termos é < 1
S =
∞∑
k=1
k
3k
=
1
3
+
2
32
+
3
33
+ ... =
∞∑
k=1
ak , onde ak =
k
3k
⇒ ak+1ak =
(k+1)/3k+1
k/3k
= 13
k + 1
k︸ ︷︷ ︸
≤2
≤ 2/3, k ≥ 1
⇒ ak+1 ≤ a1(2/3)k = 13 (2/3)
k
⇒
∞∑
k=1
ak ≤ 1/3
∞∑
k=1
(2/3)k =
1
3
2/3
(1− 2/3)
< 1
∴
∞∑
k=1
k
3k
≤ 1
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 21 / 59
Exemplo de obtenção de cotas (Cont.)
5 Método dos blocos: Hn =
∑n
k=1
1
k , n ≥ 1
0, 1︸︷︷︸
t0
, 2, 3︸︷︷︸
t1
, 4, 5, 6, 7︸ ︷︷ ︸
t2
, 8, ..., 15︸ ︷︷ ︸
t3
t0 =
0∑
j=0
1
20 + j
, t1 =
1∑
j=0
1
21 + j
,
t2 =
3∑
j=0
1
22 + j
, t3 =
23−1∑
j=0
1
23 + j
Último bloco teria, no máximo, blg nc (talvez incompleto)
⇒ Hn ≤
blg nc∑
i=0
2i−1∑
j=0
1
2i + j

(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 22 / 59
Exemplo de obtenção de cotas (Cont.)
Limitando superiormente o somatório interno:
2i−1∑
j=0
1
2i + j
≤
2i−1∑
j=0
1
2i
=
1
2i
(2i − 1 + 1) = 1
∴ Hn ≤
blg nc∑
i=0
1 ≤ blg nc+ 1
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 23 / 59
Exemplo de obtenção de cotas (Cont.)
6 Método de aproximação por integrais
1 f crescente
F Quero f (m) + f (m + 1) + ... + f (n) =
n∑
i=m
f (i)(n > m)
Limitante inferior:
n∑
i=m
f (i) ≥
n∫
m−1
f (x)dx
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 24 / 59
Exemplo de obtenção de cotas (Cont.)
Limitante superior:
n∑
i=m
f (i) ≤
n+1∫
m
f (x)dx
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 25 / 59
Exemplo de obtenção de cotas (Cont.)
6 Método de aproximação por integrais (Cont.)
1 f decrescente
F Analogamente ao caso em que f é crescente, os seguintes limitantes
podem ser obtidos:
Limitante superior:
n∑
i=m
f (i) ≤
n∫
m−1
f (x)dx
Limitante inferior:
n∑
i=m
f (i) ≥
n+1∫
m
f (x)dx
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 26 / 59
Exemplo de obtenção de cotas (Cont.)
Exemplo: Hn =
n∑
k=1
1
k
Fato: 1/k é decrescente.
Hn ≥
n+1∫
1
1
x dx = ln(n + 1)
n∑
i=2
1
k
= Hn − 1 ≤
n∫
1
1
x
dx = ln(n)
⇒ Hn ≤ ln(n) + 1
∴ ln(n + 1) ≤ Hn ≤ ln(n) + 1
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 27 / 59
Recorrências
Ideia geral: T(n) em função de n ≥ 1.
1 T(1),T(2),...,T(k) → alguns casos iniciais (casos base).
2 T(n) em função de T(n-1),T(n-2),...,T(2),T(1), n ≥ k + 1→ casos
recursivos.
⇒ mecanismos para calcular T(n) baseado em casos ”da história passada”.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 28 / 59
Recorrências
Exemplos
Exemplo 1. Fatorial: f (n) = n!, n ≥ 1.
1 f (1) = 1
2 f (n) = n × f (n − 1), n ≥ 1
→ casos bases: n = 1.
→ recorrência: f(n) depende do ”valor anterior” f(n-1), para n ≥ 2.
→ posso obter f(n), n ≥ 1.
Exemplo 2. Sequência de Fibonacci
1 F (1) = 1 e F (2) = 1
2 F (n) = F (n − 1) + F (n − 2), n ≥ 3
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 29 / 59
Recorrências
Exemplo 2. Sequência de Fibonacci
Modelos de crescimento populacional (primitiva)
→ Começo com 1 casal de coelhos.
→ Cada casal de coelho está maduro para reprodução após 1 peŕıodo.
→ Cada casal gera outro casal, em casa peŕıodo.
→ Coelhos não morrem.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 30 / 59
Recorrência
⇒ A complexidade de muitos algoritmos é expressa através de
equações de recorrência.
→ Algoritmos apresentam passos diretos, que dão origem naturalmente
as recorrências.
⇒ Dada a recorrência para T(n), n ≥ 1:
1 Posso obter expressões exatas para T(n)?
2 Posso obter boas cótas para T(n)?
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 31 / 59
Recorrência
Exemplos
→ Calculando T (n) para n = 2k , k ≥ 1:
T (n) =
{
3, para n = 2
2T (n/2) + n − 1, para n ≥ 4
→ Obter solução/cótas para T(n):
T (2) = 3
T (4) = 2 · 3 + 4− 1 = 9
T (8) = 2 · 9 + 8− 1 = 25
T (16) = 2 · 25 + 8− 1 = 57
...
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 32 / 59
Recorrência
Exemplos
→ Calculando T (n) para n = 2k , k ≥ 1:
T (2) = 3
T (n) = 2T (
n
2
) + n − 1
≤ 2T (n
2
) + n
≤ 2[2T (n
4
) +
n
2
] + n = 4T (
n
4
) + 2n
≤ 4[2T (n
8
) +
n
4
] + 2n = 8T (
n
8
) + 3n
(use indução)
T (n) ≤ 2iT ( n
2i
) + i n, i ≥ 1, n
2i
≥ 1,⇒ 2i ≤ n⇒ i ≤ k
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 33 / 59
Recorrências
Exemplos
→ Quando i = k :
T (n) ≤ 2kT ( n
2k
) + kn
= 2kT (1) + kn
= 2k + kn
∴ T (n) ≤ n + n log(n) ∴ T (n) é O(n lg(n))←
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 34 / 59
Recorrências
Ou será que T (n) ≤ cn lg(n) para algum c > 0 e n ≥ n0?
⇒ Escolho c e n0 após completar a demonstração:
Não vale para T (1), assim n ≥ 2 (restrição n0 ≥ 2).
Por indução em n:
Base:
T (2) = 3
≤ c2 lg(2)
= 2c
⇒ c ≥ 3
2
(primeira restrição sobre c)
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 35 / 59
Indução:
Suponha válido para T (m) ∀ 2 ≤ m < n. Provamos para n:
T (n) ≤ 2T (n
2
) + n − 1
≤ 2(c n
2
lg(
n
2
)) + n
≤ cn(lg(n)− 1)
≤ cn lg(n)
∴ T (n) ≤ cn lg(n), como desejado.
∴ Ok, se c ≥ 32 e n0 ≥ 2. Escolho n0 = 2 e c = 2.
∴ T (n) é O(n lg(n)).
⇒ Afirmativa T (n) ≤ cn lg(n), para algum c > 0 e n0 ≥ 1, provada.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 36 / 59
Para afirmar que T (n) = Θ(n ln(n)) preciso mostrar que T(n) é Ω(n lg(n)):
T (n) = 2T (
n
2
) + n − 1
≥ 2T (n
2
) +
n
2
, se n ≥ 2
≥ 2 [2T (n
4
) +
n
4
] +
n
2
= 22T (
n
22
) + 2
n
2
≥ 22[2T ( n
23
) +
n
23
] + 2
n
2
= 23T (
n
23
) + 3
n
2
...
≥ 2iT ( n
2i
) + i
n
2
, 1 ≤ i ≤ k , onde n = 2k , k ≥ 1
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 37 / 59
Quando k = i :
T (n) ≥ 2kT ( n
2k
) + k
n
2
= nT (1) +
n
2
lg(n)
≥ 1
2
n lg(n), n ≥ 2
∴ T(n) é Ω(n lg(n).
⇒ T(n) é Θ(n lg(n))
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 38 / 59
Recorrência
Generalizando o caso anterior
n não é potência de 2 e uso de funções de piso b·c e/ou de teto d·e;
base da recorrência definida para n ≤ n0 para alguma constante n0;
tempo para dividir+combinar é não-decrescente assintoticamente.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 39 / 59
Recorrência
n não é potência de 2 e uso de funçõesde piso b·c e/ou de teto d·e
• Seja 2k−1<n<2k e T (n)=2T (〈n/2〉) +n, onde 〈·〉 é função b·c ou d·e
• Supomos T (n) e f (n) não-decrescentes e ∃α ≥ 1:
T (m)=O(f (m))∀m=2i e i ≥ 1 e f (t)≤αf (bt/2c)∀ t ≥ 2 inteiro (*).
T (n) ≤ T (2k) (T é não-decrescente)
≤ c f (2k) (∀ 2k ≥ n0, onde c e n0 definidos em T (n)=O(f (n)))
≤ cα f (2k−1)
≤ cα f (n)
∴ se β = cα, T (n) ≤ β f (n), ∀n ≥ n0 ⇒ T (n) é O(f (n)
Exerćıcio: Faça prova análoga para provar T (n) = Ω(f (n)).
Exerćıcio: Generalize (*): Sejam constantes c > 0, c ′ ≥ 0 e c ′′ ≥ 0 e
inteiro b ≥ 2. Mostre que se f (n) = cnc ′(log n)c ′′ então
∃α ≥ 1: f (n) ≤ αf (〈n/b〉), ∀n ≥ n0.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 40 / 59
Recorrência
Com base “grande”, mas ainda de tamanho constante
Dadas constantes C > 0 e n0 ≥ 2, considere T (n) não-decrescente:
T (n) =
{
tn, onde 0 < tn ≤ C , ∀n < n0,
2T (n/2) + n, ∀n ≥ n0.
Considere n0 =2
p (senão, redefina T com n′0 e C
′ no lugar de n0 e C tal
que C ′=max{C ,T (n0),T (n0+1), . . . ,T (n′0)} onde 2p−1<n<2p =n′0).
Primeiro, considere n potência de 2:
T (n) = 2T (n/2) + n = 22T (n/22) + 2n = . . . = 2tT (n/2t) + tn
(onde n/2t = 2p ⇒ t=log(n)−p.)
= 2log(n)−pT (2p) + (log(n)− p)n
≤ (log(n)− p)C + n log(n)− pn
≤ n log(n) + C log(n)
∴ T (n) é O(n log n).
Exerćıcio: Mostre que isto também vale quando n não é potência de 2.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 41 / 59
Recorrência
Tempo para dividir+combinar é não-decrescente assintoticamente
Em T (n) = aT (〈n/b〉) + f (n), supomos T não-decrescente.
Porém, basta que f (n) seja não-decrescente assintoticamente:
Defina T ′ como T , mudando a base da recorrência para B = [n0, n
′
0], tal
que:
n′0 = db ∗ n0e+ 1 e
f é não-nula e não-decrescente a partir de n0.
T ′(n) = max{T (b) : b ∈ B} ∀ n ∈ B.
Temos T ′ não-decrescente (exerćıcio) e T (n) ≤ T ′(n) para todo n ≥ n0.
Disso temos que se T ′(n) é O(t(n)), então T é O(t(n)).
Exerćıcio: Analogamente, mostre que T (n) é Ω(t(n)).
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 42 / 59
Método da Substituição
Desenvolvendo T (n)=2T (dn/2e) + n p/ n = 2k indica T (n) é O(n log n).
“Chutamos” e usamos indução: ∃c > 0 e n0 ≥ 1 tal que T (n) ≤ cn log n
∀n ≥ n0.
Base: ∀ constante n0 ⇒ ∃D: T (n) ≤ D para todo 2 ≤ n ≤ n0.
Assim, T (n) ≤ D ≤ Dn log n para n ≥ 2 e a base vale se c ≥ D.
H.I.: Supomos T (m) ≤ cm logm para todo m < n.
Primeira tentativa:
T (n) = 2T (dn/2e) + n
≤ 2cdn/2e log(dn/2e) + n
≤ 2c(n/2 + 1) log(n/2 + 1) + n
≤ (cn + 2c) log(n) + n
= cn log(n) + 2c log(n) + n
Não conseguimos T (n) ≤ cn log(n) pois 2c log(n) + n é positivo.
Exageramos quando fizemos log(n/2 + 1) ≤ log(n)
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 43 / 59
Método da Substituição
Segunda tentativa, continuando de T (n) ≤ 2c(n/2 + 1) log(n/2 + 1) + n.
T (n) ≤ 2c(n/2 + 1) log(n/2 + 1) + n
≤ (cn + 2c) log(n/2 + n/6) + n , para n ≥ 6 (*)
≤ (cn + 2c) log(n(2/3)) + n
= cn log(n) + 2c log(n) + cn log(2/3) + 2c log(2/3) + n
= cn log(n) + (1 + c log(2/3))n + 2c log(n) + 2c log(2/3)︸ ︷︷ ︸
negativo para c e n0 suficientemente grandes
≤ cn log n
Ponto crucial (*) foi obter parâmetro βn no log com β < 1 (β = 2/3).
Com isso log(βn) = log(β) + log(n) e obtivemos o termo negativo log(β)
que será multiplicado por c . Obs.: 0 < a < 1 e b > 1 ⇒ logb(a) < 0.
Exerćıcio: Considerando D > 0 e C > 0 constantes, resolva a recorrência
T (n) = 2T (n/2 + f (n)) + Cn para as seguintes funções de f (n):
(a) f (n) = D; (b) f (n) = C log(n) + D
√
(n); (c) f (n) = o(n).
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 44 / 59
Método da Substituição
Generalizações: Aprendendo com a prova anterior e dividindo em partes diferentes
Seja T (n) =
∑p
i=1 T (〈αin〉) + n, onde 0 < αi < 1 e
∑p
i=1 αi = 1.
Exemplo: T (n) = T (〈n/10〉) + T (〈9n/10〉) + n.
Suponha T (n) = O(n log n), com αin inteiros e β = max{αi}.
Indução
T (n) ≤ c
p∑
i=1
αin log(αin) + n ≤ c
p∑
i=1
αin log(βn) + n
≤ cn log(βn)
p∑
i=1
αi + n = cn log(βn)1 + n
= cn log(n) + (1 + c log(β))n
≤ cn log n (para c suficientemente grande)
Exerćıcio: Analogamente, mostre que T (n) é Ω(n log n).
Exerćıcio: Considere T (n) =
∑p
i=1 T (αin) + n
k . (i) Mostre que se∑p
i=1 αi < 1 e k = 1, então T (n) é Θ(n). Mostre condições suficientes
para que (ii) T (n) seja Θ(nk) e para que (iii) T (n) seja Θ(nk log n).
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 45 / 59
Sequências de Fibonacci
F (1) = F (2) = 1
F (n) = F (n − 1) + F (n − 2), n ≥ 3
Quero cotas para F(n).
Conjectura: F(n) ”dobra”a cada iteração (+,-)
1)
F (n) = c2n
∴ c2n = c2n−1 + c2n−2, n ≥ 3
∴ 2n = 2n−1 + 2n−2 ⇒ NÃO
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 46 / 59
2) Outra base?
F (n) = an
∴ an = an−1 + an−2
∴ a2 = a + 1, a2 − a− 1 = 0
∴ a1 =
1 +
√
5
2︸ ︷︷ ︸
>0
, a2 =
1−
√
5
2︸ ︷︷ ︸
<0
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 47 / 59
Mostrar: F (n) ≤ cak1 , para algum c > 0 e n ≥ n0
Base:
F (1) = 1 ≤ ca1
F (2) = 1 ≤ ca21
∴ c ≥ max( 1
a1
,
1
a21
) =
1
a1
Indução
F (n) ≤ can−11 + ca
n−2
1
≤ c(an−11 + a
n−2
1 )
≤ can1, n ≥ 3
∴OK!
F(n) é O(an1)
∴ F(n) é O(2n), com a1 = 1.61 < 2
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 48 / 59
F(n) é Θ(an1) ?
Mostrar que F(n) é Ω(an1)→ mesma ideia!
Base:
F (1) = 1 ≥ da1
F (2) = 1 ≥ da21
∴d ≤ 1
a1
, d ≤ 1
a21
→ d = 1
a21
Indução
F (n) ≥ dan−11 + da
n−2
1 (H.I )
= d(an−11 + a
n−2
1 )
= dan1
∴OK!
∴ F(n) é Ω(an1).
Logo, F(n) é Θ(an1).
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 49 / 59
Método das substituições sucessivas
T (1) = α
T (n) = aT (
n
b
) + cnk , k ≥ 0, b > 1, a ≥ 0
⇒ T́ıpica recorrência que ocorre em projetos de algoritmos:
T (n)⇐ T (nb )⇐ T (
n
b2
)⇐ T ( n
b3
)⇐ . . .
Todos inteiros de n = bp, para algum p ≥ 1
∴ Assumir n = bp, p ≥ 1.
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 50 / 59
∴ T (n) = a[aT (
n
b2
) + c
nk
bk
] + cnk
= a2T (
n
b2
) + cnk(
a
bk
) + cnk(
a
bk
)0
= a2[aT (
n
b3
) +
cnk
b2k
] + cnk(
a
bk
) + cnk(
a
bk
)0
= a3T (
n
b3
) + cnk(
a
bk
)2 + cnk(
a
bk
) + cnk(
a
bk
)0
... (indução)
T (n) = aiT (
n
bi
) + cnk [r i−1 + r i−2 + · · ·+ r + 1], r = a
bk
, 1 ≤ k ≤ p
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 51 / 59
⇒ Quando i = p:
T (n) = apT (1) + cnk
p−1∑
j=0
r j
⇒ 3 casos:
(i) a = bk , r = 1
(ii) a < bk , r < 1
(iii) a > bk , r > 1
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 52 / 59
Caso (i): r=1,
p−1∑
j=0
r j = p
ap = (bk)p = (bp)k = nk
bp = n
∴ p = logbn
∴ T (n) = nkT (1) + cnk logbn
∴ T(n) é O(nk logbn)
∴ T(n) é O(nk lg(n))
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 53 / 59
Caso (ii): r < 1,
p−1∑
j=0
r j ≤
∞∑
j=0
r j = 11−r
ap = alogbn = nlogba
∴ T (n) = apT (1) +
cnk
1− r
mas r < 1, ∴ a
bk
< 1, ∴ a < bk , ∴ logba < k .
∴ T(n) = nlogbaT (1) +
cnk
1− r
∴ T(n) é O(nk)
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 54 / 59
Caso (iii): r > 1,
p−1∑
j=0
r j = r
p−1
r−1 ≤
rp
r−1
rp = (
a
bk
)p =
ap
bkp
=
ap
nk
=
nlogba
nk
T (n) ≤ T (1)nlogba +
cnknlogba
nk
r − 1
= T (1)nlogba +
cnlogba
r − 1
∴ T(n) é O(nlogba)
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 55 / 59
E se n não é potência de 2?
⇒ Use a mesma ideia: br < n < br+1, para algum r ≥ 1
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 56 / 59
Exemplos
1)
T (1) = 1
T (n) = 3T (
n
4
) + n, n ≥ 1
⇒a = 3, b =4, k = 1, a < bk .Caso(ii))
T (n) é O(n1)
∴ T (n) é O(n)
2)
T (1) = 1
T (n) = 2T (
n
2
) +
√
n, n ≥ 2
⇒a = 2, b = 2, k = 1
2
, a > bk .Caso(iii)
T (n) é O(nlogba)
∴ T (n) é O(n)
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 57 / 59
Dependência completa da história passada

T (1) = k
T (n) = c +
n−1∑
i=1
T (i), n ≥ 1
∴ T(n) depende de T(n-1),T(n-2),. . . ,T(1), n ≥ 2.
⇒ T (n + 1) = c +
n−1∑
i=1
T (i)︸ ︷︷ ︸
T (n)
+T (n) = 2T (n)
∴ T (n + 1) = 22T (n − 1) = 23T (n − 2) = . . . (indução)
T (n + 1) = 2i+1T (n − i), 0 ≤ i < n
∴ Quando i=n-1
T (n + 1) = 2nT (1)
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 58 / 59
⇒ e a constante c? Desaparece?
T (2) = T (1 + 1) = 21T (1) = 2T (1)
Mas T (2) = c + T (1)
⇒ Base (que não foi verificada) não é verdade.
Base:
T (2) = c + T (1)
Indução:
T (n + 1) = 2n−1T (2), n ≥ 2
T (n + 1) = (c + T (1))2n−1, n ≥ 1
T (n) = (c + T (1))2n−2, n ≥ 2
=
c + T (1)
4
2n, k ≥ 2
∴ T (n) é Θ(2n)
(Instituto de Computação - Unicamp) MC458 - Complexidade e Notação Assintótica 59 / 59
	Introdução