MC458 - Complexidade e Notação Assintóticardahab/cursos/mc458/2014-2s/... · 2014-09-16 · Multiplica˘c~ao de inteiros Complexidade I Supondo que cada instruc˘~ao tem custo

MC458 - Complexidade e Notacao Assintotica

Instituto de Computacao - Unicamp

(Instituto de Computacao - Unicamp) MC458 - Complexidade e Notacao Assintotica 1 / 59

Multiplicacao de inteirosProblema

Problema: Ler inteiros m e n e calcular m · n. Assuma que nao hainstrucao de multiplicacao disponıvel.

m · n = m + m + · · ·+ m︸︷︷︸n vezes

1 load r0, 0 carrega 0 no reg. r02 read r1 carrega m no reg. r13 read r2 carrega n no reg. r24 jmpz r2, 8 jump para linha 8 se r2 = 05 add r0, r0, r1 adiciona r0 e r1, armazena o resultado em r06 sub r2, r2, 1 decrementa r27 jmp 4 jump para linha 48 write r0 escreve o valor de r0 na saıda


Multiplicacao de inteirosComplexidade I

Supondo que cada instrucao tem custo 1, a complexidade e:Custo

1 load r0, 0 12 read r1 13 read r2 14 jmpz r2, 8 n + 15 add r0, r0, r1 n6 sub r2, r2, 1 n7 jmp 4 n8 write r0 1

T (n) = 4n + 5Se invertermos n e m, calculando m · n:

T (m) = 4m + 5


Multiplicacao de inteirosComplexidade II

Supondo que o custo e proporcional ao comprimento (em bits) do valorarmazenado, a complexidade e:

Custo

1 load r0, 0 12 read r1 lgm3 read r2 lg n4 jmpz r2, 8 lg n + lg(n − 1) + · · ·+ lg 2 + 15 add r0, r0, r1 lgm + lg(2m) + · · ·+ lg(nm)6 sub r2, r2, 1 lg(n + 1) + · · ·+ lg 17 jmp 4 n8 write r0 lg(mn)

T (n)


Multiplicacao de inteirosComplexidade 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 aproximacao de Stirling, n! ≈(ne

)n√2πn

≈ 2 + n + 2 lg(mn) + 3n lg n + n lgm

≈ 2 + n + 3n lg n + n lgm

O calculo da complexidade fica bem mais complicado.


Analise de AlgoritmosProblemas

Quanto usa de um recurso (tempo/memoria), depende das entradas.

Problemas:

1 Expressao exata e complexa e difıcil de obter.

2 Como medir “tamanho” da entrada?

3 Entradas de mesmo tamanho, mas com valores diferentes, podemusar mais ou menos recursos.


Analise de AlgoritmosProblemas (Cont.)

1 Expressao exata e complexa e difıcil de obter.I Solucao exata nao e necessaria. Pode-se ignorar:

F constantes (comparando algoritmos);F termos de crescimento menor (“embutidos” nos termos principais);F casos particulares iniciais (comportamento assintotico)

Alg1 : T1(n) = 100n→≤ k1n(k1 = 1000)Alg2 : T2(n) = 6n2 + 300→≤ k2n

2(k2 = 10, n ≥ 8)Alg1 “cresce” na razao de k1n.Alg2 “cresce” na razao de k2n

2.



0

20000

40000

60000

80000

100000

120000

140000

160000

180000

200000

0 20 40 60 80 100 120 140

tempo

n

T1(n)T2(n)

Figura 1: Assintoticamente, Alg1 e “melhor”.



2 Como medir o “tamanho” da entrada?Solucoes:

I no. de elementos.Ex: vetor de n numeros inteiros ⇒ tamanho n.

I no. de bits para armazenar a entrada.Ex: vetor de n numeros de tamanho ≤ k ⇒ n lg k (maior precisao, masenvolve limite k).



3 Entradas de mesmo tamanho, mas com valores diferentes podem usarmais ou menos recursos. Solucoes:

1 Avaliar uso de recursos no pior caso.2 Avaliar uso de recursos no caso medio

F Precisa de uma distribuicao de probabilidades para as instancias deentrada.


Notacao Assintotica: O, Ω, Θ

Para lidar com o problema (1).Sejam f e g funcoes (crescentes) que medem gasto de recursos.

1 g e O(f ) sse existir constantes c e n0 tais que g(n) ≤ c f (n), paratodo 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.


Notacao Assintotica: O, Ω, Θ (Cont.)

Exemplos:

1 g(n) = 1000nf (n) = 5n2 + 300.g e O(f ), pois:g(n) ≤ cf (n) ∀n ≥ n0, se c = 1 e n0 = 200ou se c = 20 e n0 = 10.

2 g(n) = 5n2 + 40g e O(n2), e O(n3), e O(2n),e O(n!)...cotas superiores mais frouxas−−−−−−−−−−−−−−−−−−−−−−→cotas superiores mais justas←−−−−−−−−−−−−−−−−−−−−−



Exemplos:

1 p(n) ≡ polinomio de grau k (k ≥ 0)p(n) e O(nk)p(n) =

∑ki=0 ain

i ≤ (k + 1)a︸︷︷︸c

nk , onde a e o maximo dentre os ai s

∴ p(n) ≤ cnk ,∀n ≥ 0c = max|a0|, |a1|, ..., |ak | > 0.


Notacao Assintotica: O, Ω, Θ (Cont.)Usando limite:

Se f (n)>0 e g(n)>0 sao tais que limn→∞

f (n)

g(n)=L<∞ entao f (n) e 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 diferenciavel com limn→∞

f (n) =∞ e constantes

c > 0 e a > 1. Se F (n) = [f (n)]c e G (n) = af (n) entao F (n) e O(G (n)).

Considere n0 suficientemente grande para que f (n) > 0, ∀n ≥ n0.

limn→∞

[f (n)]c

af (n)= lim

n→∞

c [f (n)]c−1

ln(a)af (n)(obtida usando regra de L’Hopital)

... reaplicando enquanto expoente de f for positivo

= limn→∞

c(c − 1) · · · (c − k + 1)[f (n)]c−k

(ln(a))kaf (n)

= 0 ∴ [f (n)]c e O(af (n))



Exemplos:n = 1000

Alg. 1000 passos/seg. 8000 passos/seg

lg n 0.01 0.001n 1 0.125n1.5 32 4n3 106 125 · 103

1.1n 1039 1038



II g e Ω(f ) sse existe c > 0 e n0 ≥ 1 tais que:g(n) ≥ cf (n), para n ≥ n0

⇒ f e dominada por g a partir de n0.Exemplos:

I n2 e Ω(n2 − 100), pois n2 ≥ 1 · (n2 − 100) , para n ≥ 1I n2 e Ω(n0.8), pois n2 ≥ 1 · n0.8, para n ≥ 1I n3 e Ω(n2), e Ω(n), e Ω(log n), ...

cotas inferiores mais fracas−−−−−−−−−−−−−−−−−−−−→cotas inferiores mais justas←−−−−−−−−−−−−−−−−−−−−



III g e Θ(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 razao” a partir de n0

⇒ g e Θ(f ) sse g e O(f ) e g e Ω(f )Exemplo:

I 5n lg n + 3 e Θ(n lg n)n lg n e cota justa para 5n lg n + 8: so diferem por uma constantemultiplicativa e a partir de um certo n ≥ n0.∴ para n grande, 5n lg n + 3 e ≈ proporcional a n lg n.



IV Cotas estritas:1 Superior: g e o(f ) sse para todo c > 0, existe n0 tal que

g(n) < cf (n),∀n ≥ n0. Note que se f > 0, limn→∞

g(n)/f (n) = 0

Exemplo:2n2 + 1 e O(n3), mas nao e o(n2), pois nao temos 2n2 + 1 < cn2 paratodo c (p. ex., nao vale para c = 1).

2 Inferior: g e ω(f ) sse para todo c > 0, existe n0 tal queg(n) > cf (n),∀n ≥ n0.n3 e ω(n2 log n).


Obtencao de cotas para somatorios

1 Metodo direto: S(n) =n∑

i=0

2i

S(n) = 2n+1 − 1 e 2n+1 ≤ 2n+1 = 2 · 2n ∴ S(n) e Θ(2n)

2 Metodo 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) e Θ(n2n)

Exercıcio: Calcule (a) S(n) =∑n

i=1 iai para a > 0 e

(b) S =∑∞

i=1 iai para 0 < a < 1.


Exemplo de obtencao de cotas (Cont.)

3 Metodo indutivo: mostrar que∑n

i=0 3i e O(3n).Preciso de c > 0 e n0 ≥ 0 tais que

∑ni=0 3i ≤ c3n, n ≥ n0.

⇒ escolha de c e n0 ainda em aberto.Base: 30 ≤ c30 (quando n = 0).∴ preciso de c ≥ 1.H.I.:

∑ni=0 3i ≤ 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/2Base + passo indutivo se c ≥ 1 e c ≥ 3/2.∴ Escolho c = 1,5 e n0 = 0.



4 Somatorios: cota superior quando razao entre termos e < 1

S =∞∑k=1

k

3k=

1

3+

2

32+

3

33+ ... =

∞∑k=1

ak , onde ak =k

3k

⇒ ak+1

ak= (k+1)/3k+1

k/3k= 1

3

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



5 Metodo dos blocos: Hn =∑n

k=11k , 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

Ultimo bloco teria, no maximo, blg nc (talvez incompleto)

⇒ Hn ≤blg nc∑i=0

2i−1∑j=0

1

2i + j



Limitando superiormente o somatorio 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


Exemplo de obtencao de cotas (Cont.)6 Metodo de aproximacao 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



Limitante superior:

n∑i=m

f (i) ≤n+1∫m

f (x)dx



6 Metodo de aproximacao por integrais (Cont.)1 f decrescente

F Analogamente ao caso em que f e crescente, os seguintes limitantespodem 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



Exemplo: Hn =n∑

k=1

1

k

Fato: 1/k e decrescente.

Hn ≥n+1∫1

1x dx = ln(n + 1)

n∑i=2

1

k= Hn − 1 ≤

n∫1

1

xdx = ln(n)

⇒ Hn ≤ ln(n) + 1∴ ln(n + 1) ≤ Hn ≤ ln(n) + 1


Recorrencias

Ideia geral: T(n) em funcao de n ≥ 1.

1 T(1),T(2),...,T(k) → alguns casos iniciais (casos base).

2 T(n) em funcao de T(n-1),T(n-2),...,T(2),T(1), n ≥ k + 1→ casosrecursivos.

⇒ mecanismos para calcular T(n) baseado em casos ”da historia passada”.


RecorrenciasExemplos

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.

→ recorrencia: f(n) depende do ”valor anterior” f(n-1), para n ≥ 2.

→ posso obter f(n), n ≥ 1.

Exemplo 2. Sequencia de Fibonacci

1 F (1) = 1 e F (2) = 1

2 F (n) = F (n − 1) + F (n − 2), n ≥ 3


RecorrenciasExemplo 2. Sequencia de Fibonacci

Modelos de crescimento populacional (primitiva)

→ Comeco com 1 casal de coelhos.

→ Cada casal de coelho esta maduro para reproducao apos 1 perıodo.

→ Cada casal gera outro casal, em casa perıodo.

→ Coelhos nao morrem.


Recorrencia

⇒ A complexidade de muitos algoritmos e expressa atraves deequacoes de recorrencia.

→ Algoritmos apresentam passos diretos, que dao origem naturalmenteas recorrencias.

⇒ Dada a recorrencia para T(n), n ≥ 1:1 Posso obter expressoes exatas para T(n)?2 Posso obter boas cotas para T(n)?


RecorrenciaExemplos

→ Calculando T (n) para n = 2k , k ≥ 1:

T (n) =

3, para n = 22T (n/2) + n − 1, para n ≥ 4

→ Obter solucao/cotas 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...


RecorrenciaExemplos

→ 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 inducao)

T (n) ≤ 2iT (n

2i) + i n, i ≥ 1,

n

2i≥ 1,⇒ 2i ≤ n⇒ i ≤ k


RecorrenciasExemplos

→ Quando i = k :

T (n) ≤ 2kT (n

2k) + kn

= 2kT (1) + kn

= 2k + kn

∴ T (n) ≤ n + n log(n) ∴ T (n) e O(n lg(n))←


Recorrencias

Ou sera que T (n) ≤ cn lg(n) para algum c > 0 e n ≥ n0?

⇒ Escolho c e n0 apos completar a demonstracao:Nao vale para T (1), assim n ≥ 2 (restricao n0 ≥ 2).Por inducao em n:Base:

T (2) = 3

≤ c2 lg(2)

= 2c

⇒ c ≥ 3

2(primeira restricao sobre c)


Inducao:Suponha valido para T (m) ∀ 2 ≤ m < n. Provamos para n:

T (n) ≤ 2T (n

2) + n − 1

≤ 2(cn

2lg(

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) e O(n lg(n)).

⇒ Afirmativa T (n) ≤ cn lg(n), para algum c > 0 e n0 ≥ 1, provada.


Para afirmar que T (n) = Θ(n ln(n)) preciso mostrar que T(n) e Ω(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


Quando k = i :

T (n) ≥ 2kT (n

2k) + k

n

2

= nT (1) +n

2lg(n)

≥ 1

2n lg(n), n ≥ 2

∴ T(n) e Ω(n lg(n).

⇒ T(n) e Θ(n lg(n))


RecorrenciaGeneralizando o caso anterior

n nao e potencia de 2 e uso de funcoes de piso b·c e/ou de teto d·e;

base da recorrencia definida para n ≤ n0 para alguma constante n0;

tempo para dividir+combinar e nao-decrescente assintoticamente.


Recorrencian nao e potencia de 2 e uso de funcoes de piso b·c e/ou de teto d·e

• Seja 2k−1<n<2k e T (n)=2T (〈n/2〉) +n, onde 〈·〉 e funcao b·c ou d·e

• Supomos T (n) e f (n) nao-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 e nao-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) e O(f (n)

Exercıcio: Faca prova analoga para provar T (n) = Ω(f (n)).Exercıcio: Generalize (*): Sejam constantes c > 0, c ′ ≥ 0 e c ′′ ≥ 0 einteiro b ≥ 2. Mostre que se f (n) = cnc

′(log n)c

′′entao

∃α ≥ 1: f (n) ≤ αf (〈n/b〉), ∀n ≥ n0.


RecorrenciaCom base “grande”, mas ainda de tamanho constante

Dadas constantes C > 0 e n0 ≥ 2, considere T (n) nao-decrescente:

T (n) =

tn, onde 0 < tn ≤ C , ∀n < n0,2T (n/2) + n, ∀n ≥ n0.

Considere n0 =2p (senao, redefina T com n′0 e C ′ no lugar de n0 e C talque C ′=maxC ,T (n0),T (n0+1), . . . ,T (n′0) onde 2p−1<n<2p =n′0).

Primeiro, considere n potencia 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) e O(n log n).Exercıcio: Mostre que isto tambem vale quando n nao e potencia de 2.(Instituto de Computacao - Unicamp) MC458 - Complexidade e Notacao Assintotica 41 / 59

RecorrenciaTempo para dividir+combinar e nao-decrescente assintoticamente

Em T (n) = aT (〈n/b〉) + f (n), supomos T nao-decrescente.Porem, basta que f (n) seja nao-decrescente assintoticamente:

Defina T ′ como T , mudando a base da recorrencia para B = [n0, n′0], tal

que:

n′0 = db ∗ n0e+ 1 e

f e nao-nula e nao-decrescente a partir de n0.

T ′(n) = maxT (b) : b ∈ B ∀ n ∈ B.

Temos T ′ nao-decrescente (exercıcio) e T (n) ≤ T ′(n) para todo n ≥ n0.Disso temos que se T ′(n) e O(t(n)), entao T e O(t(n)).

Exercıcio: Analogamente, mostre que T (n) e Ω(t(n)).


Metodo da Substituicao

Desenvolvendo T (n)=2T (dn/2e) + n p/ n = 2k indica T (n) e O(n log n).“Chutamos” e usamos inducao: ∃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

Nao conseguimos T (n) ≤ cn log(n) pois 2c log(n) + n e positivo.Exageramos quando fizemos log(n/2 + 1) ≤ log(n)


Metodo da SubstituicaoSegunda 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 parametro βn no log com β < 1 (β = 2/3).Com isso log(βn) = log(β) + log(n) e obtivemos o termo negativo log(β)que sera multiplicado por c . Obs.: 0 < a < 1 e b > 1 ⇒ logb(a) < 0.Exercıcio: Considerando D > 0 e C > 0 constantes, resolva a recorrenciaT (n) = 2T (n/2 + f (n)) + Cn para as seguintes funcoes de f (n):(a) f (n) = D; (b) f (n) = C log(n) + D

√(n); (c) f (n) = o(n).


Metodo da SubstituicaoGeneralizacoes: 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.Inducao

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)

Exercıcio: Analogamente, mostre que T (n) e Ω(n log n).Exercıcio: Considere T (n) =

∑pi=1 T (αin) + nk . (i) Mostre que se∑p

i=1 αi < 1 e k = 1, entao T (n) e Θ(n). Mostre condicoes suficientespara que (ii) T (n) seja Θ(nk) e para que (iii) T (n) seja Θ(nk log n).(Instituto de Computacao - Unicamp) MC458 - Complexidade e Notacao Assintotica 45 / 59

Sequencias 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 iteracao (+,-)1)

F (n) = c2n

∴ c2n = c2n−1 + c2n−2, n ≥ 3

∴ 2n = 2n−1 + 2n−2 ⇒ NAO


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


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

Inducao

F (n) ≤ can−11 + can−2

1

≤ c(an−11 + an−2

1 )

≤ can1, n ≥ 3

∴OK!

F(n) e O(an1)∴ F(n) e O(2n), com a1 = 1.61 < 2


F(n) e Θ(an1) ?Mostrar que F(n) e Ω(an1)→ mesma ideia!Base:

F (1) = 1 ≥ da1

F (2) = 1 ≥ da21

∴d ≤ 1

a1, d ≤ 1

a21

→ d =1

a21

Inducao

F (n) ≥ dan−11 + dan−2

1 (H.I )

= d(an−11 + an−2

1 )

= dan1

∴OK!

∴ F(n) e Ω(an1).Logo, F(n) e Θ(an1).


Metodo das substituicoes sucessivas

T (1) = α

T (n) = aT (n

b) + cnk , k ≥ 0, b > 1, a ≥ 0

⇒ Tıpica recorrencia que ocorre em projetos de algoritmos:T (n)⇐ T (nb )⇐ T ( n

b2 )⇐ T ( nb3 )⇐ . . .

Todos inteiros de n = bp, para algum p ≥ 1∴ Assumir n = bp, p ≥ 1.


∴ 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

... (inducao)

T (n) = aiT (n

bi) + cnk [r i−1 + r i−2 + · · ·+ r + 1], r =

a

bk, 1 ≤ k ≤ p


⇒ Quando i = p:

T (n) = apT (1) + cnkp−1∑j=0

r j

⇒ 3 casos:

(i) a = bk , r = 1

(ii) a < bk , r < 1

(iii) a > bk , r > 1


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) e O(nk logbn)

∴ T(n) e O(nk lg(n))


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, ∴ abk< 1, ∴ a < bk , ∴ logba < k .

∴ T(n) = nlogbaT (1) +cnk

1− r

∴ T(n) e O(nk)


Caso (iii): r > 1,p−1∑j=0

r j = rp−1r−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) e O(nlogba)


E se n nao e potencia de 2?⇒ Use a mesma ideia: br < n < br+1, para algum r ≥ 1


Exemplos1)

T (1) = 1

T (n) = 3T (n

4) + n, n ≥ 1

⇒a = 3, b = 4, k = 1, a < bk .Caso(ii))

T (n) e O(n1)

∴ T (n) e 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) e O(nlogba)

∴ T (n) e O(n)


Dependencia completa da historia 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) = . . . (inducao)

T (n + 1) = 2i+1T (n − i), 0 ≤ i < n

∴ Quando i=n-1

T (n + 1) = 2nT (1)


⇒ e a constante c? Desaparece?

T (2) = T (1 + 1) = 21T (1) = 2T (1)

Mas T (2) = c + T (1)

⇒ Base (que nao foi verificada) nao e verdade.Base:

T (2) = c + T (1)

Inducao:

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)

42n, k ≥ 2

∴ T (n) e Θ(2n)


Documents

MC458 - Complexidade e Notação Assintóticardahab/cursos/mc458/2014-2s/... · 2014-09-16 · Multiplica˘c~ao de inteiros Complexidade I Supondo que cada instruc˘~ao tem custo