exerInacabadoAula1209

Prévia do material em texto

�
�
“livroAlgoritmosSanderson” — 2011/9/13 — 10:11 — page 18 — #28
�
�
�
�
�
�
18 1 Complexidade de tempo de algoritmos por divisa˜o e conquista
Quarto exemplo do me´todo da a´rvore de recursa˜o
O exemplo a seguir resolve a recorreˆncia
T (n) = 2T
�n
3
�
+ cn · lg n, (1.26)
considerando-se n= 3⇒ T (n) = Θ(1).
Teorema. 2T
�
n
3
�
+ cn · lg n= O(n·lg n).
Demonstrac¸a˜o. A primeira chamada da execuc¸a˜o de um algoritmo que tenha tempo de
execuc¸a˜o expresso pela recorreˆncia (1.26) tera´ tempo cn·lg n. Com isso, coloca-se esse
termo na raiz da a´rvore. A contribuic¸a˜o para o tempo de execuc¸a˜o deste nı´vel tambe´m e´
cn·lg n.
A cada chamada recursiva, o algoritmo faz duas novas chamadas recursivas, sendo
o nu´mero de elementos passados para cada uma dessas chamadas e´ um terc¸o. Com isso,
o segundo nı´vel da a´rvore de recursa˜o da Figura ?? tem dois nodos (falta fazer a figura!).
Cada nodo contribui com cn
3
lgn
3
. A contribuic¸a˜o de um nı´vel e´ a soma dos tempos de
execuc¸o˜es de cada nodo do nı´vel. A contribuic¸a˜o do segundo nı´vel da a´rvore e´ a soma
dos dois termos, resultando em c2n
3
·lgn
3
.
Cada uma das duas chamadas do segundo nı´vel de recursa˜o faz duas novas chama-
das recursivas. Com isso, o terceiro nı´vel da a´rvore de recursa˜o da Figura 1.3 tem quatro
nodos. Cada nodo contribui com cn
9
lgn
9
. A contribuic¸a˜o do terceiro nı´vel da a´rvore e´ a
soma dos quatro termos, resultando em c4n
9
·lg n
4
.
Devem-se escrever nı´veis na a´rvore de recursa˜o ate´ que o padra˜o seja percebido.
Neste exemplo, percebe-se, sem necessidade de se desenhar o quarto nı´vel na a´rvore,
que a contribuic¸a˜o do quarto nı´vel e´ c8n
27
·lg n
27
e que a contribuic¸a˜o e´ c(2
3
)in·lg n
3i
para o
i-e´simo nı´vel, em que a raiz e´ o nı´vel 0.
Cada nodo folha da a´rvore de recursa˜o contribui com 3·lg 3=Θ(1). Perceba que,
como a base do logaritmo e´ 3, enta˜o, neste exemplo, lg n = log3n. Ha´ 3c
n
log32
2
=
Θ(nlog32) nodos folhas nessa a´rvore de recursa˜o.
�
�
“livroAlgoritmosSanderson” — 2011/9/13 — 10:11 — page 19 — #29
�
�
�
�
�
�
1.2 Ana´lise de algoritmos divisa˜o e conquista 19
Precisa-se tambe´m descobrir a quantidade de nı´veis da a´rvore de recursa˜o. Clara-
mente, o nu´mero de elementos da entrada do algoritmo e´ n. O nu´mero de itens a cada
nı´vel de recursa˜o e´ dividido por 3 ate´ que n=3. Com isso, a altura da a´rvore de recursa˜o
e´ log3n-1. Deve-se considerar tambe´m a raiz, resultando em log3n nı´veis.
A construc¸a˜o da a´rvore de recursa˜o mostra que ha´ log3n nı´veis e o nı´vel i contribui
c(2
3
)in·log3
n
3i
para o tempo de execuc¸a˜o, em que a raiz e´ o nı´vel 0. Pode-se, enta˜o,
reescrever a recorreˆncia (1.26) como
T (n) = cn
log3n−1
∑
i=0
(
2
3
)ilog3
n
3i
. (1.27)
Note que a contribuic¸a˜o do u´ltimo nı´vel e´ cn(2
3
)log3n−1·log3
n
3log3n−1
=
c 3
2
nlog32·log3
n
n
3
= 3c
2
nlog32. A equac¸a˜o (1.27) pode ser reescrita como
T (n) = cn
log3n−1
∑
i=0
�
2
3
�i
(log3n− i) (1.28)
Aplicando-se propriedades de logaritmos, pode-se reescrever a equac¸a˜o (1.28) como
T (n) = cn(

log3n
log3n−1
∑
i=0
�
2
3
�i
−
log3n−1
∑
i=0
�
2
3
�i
i

 (1.29)
Note que no primeiro somato´rio da equac¸a˜o (1.29), o fator logarı´tmico na˜o consta no
somato´rio porque na˜o depende do ı´ndice do somato´rio. Utilizando-se a fo´rmula fechada
para a se´rie geome´trica (veja a sec¸a˜o de revisa˜o de matema´tica ba´sica no capı´tulo ??),
obte´m-se (tem que provar por induc¸a˜o!)
T (n) = cn

−3 · log3n(nlog3 23 −1)−
log3n−1
∑
i=0
�
2
3
�i
i

 (1.30)
Sabendo-se que
n−1
∑
i=0
ixi = x−nx
n+(n−1)xn+1
(1−x)2
, escreve-se a equac¸a˜o 1.30 como (tem que
�
�
“livroAlgoritmosSanderson” — 2011/9/13 — 10:11 — page 20 — #30
�
�
�
�
�
�
20 1 Complexidade de tempo de algoritmos por divisa˜o e conquista
provar por induc¸a˜o!)
T (n) = cn
�
−3 · log3n ·n
log3
2
3 +3 · log3n−6+9 · log3n ·n
log3
2
3 −6 ·nlog3
2
3 (log3n−1)
�
(1.31)
ou
T (n) = 3cn · log3n−6cn+6cn
log32 = O(n · lg n) (1.32)
O custo total 3c
2
nlog32 das chamadas recursivas no u´ltimo nı´vel e´ assintoticamente
menor que a contribuic¸a˜o da primeira chamada recursiva.
SeO(n·lg n) e´ um limite superior para a recorreˆncia, enta˜o, a mesma func¸a˜o tambe´m
deve ser um limite estrito Θ(n·lg n). Como T (n) ≤ 2T
�
n
3
�
+ cn·log3n ≤ 2d
n
3
·log3
n
3
+
cn·log3n=
2d
3
n(log3n−1)+cn·log3n=
2d
3
n · log3n−
2dn
3
+cn·log3n= p ·n·log3n−
2dn
3
,
em que p= 2d
3
+c, para n suficientemente grande, enta˜o, e´ possı´vel encontrar, para essa
u´ltima func¸a˜o:
• uma constante real maior ou igual a` p para que a func¸a˜o pertenc¸a a` O(n · lg n);
• uma constante real positiva que seja menor ou igual a` p para que a`
func¸a˜o pertenc¸a a Ω(n · lg n).