12-complexidade-recursividade

Prévia do material em texto

Algoritmos e Estrutura de Dados II 
Análise de Algoritmos Recursivos 
 Para cada procedimento recursivo é 
associada uma função de complexidade f(n) 
desconhecida, onde n mede o tamanho dos 
argumentos para o procedimento. 
 Por se tratar de um algoritmo recursivo, f(n) 
vai ser obtida através de uma equação de 
recorrência. 
 Equação de recorrência: maneira de definir 
uma função por uma expressão envolvendo 
a mesma função. 
 
Algoritmos e Estrutura de Dados II 
Equação de Recorrência. 
Exemplo 
Fat (int n) { 
 if (n<=0) 
 return 1; 
 else 
 return n * Fat(n-1); 
} 
 Se n <= 0 faz uma operação de custo 
constante 
 Se n > 0 faz uma operação de custo 
constante e chama recursivamente a função 
Algoritmos e Estrutura de Dados II 
Equação de Recorrência. 
Exemplo 
Fat (int n) { 
 if (n<=0) 
 return 1; 
 else 
 return n * Fat(n-1); 
} 
 Equação de recorrência para o Fatorial 
f(n) = c + f(n-1), para n > 0 
f(n) = d. para n  0 
Algoritmos e Estrutura de Dados II 
Resolvendo a Equação de Recorrência 
 Existem várias formas de se resolver uma equação 
de recorrência 
 A mais simples é expandir a equação e depois fazer 
uma substituição dos termos 
 Ex. Fatorial: 
f(n) = c + f(n-1) 
f(n-1) = c + f(n-2) 
f(n-2) = c + f(n-3) 
... 
f(1) = c + f(0) 
f(0) = d 
f(n) = c + c + c + ... + c + d 
n vezes 
f(n) = n.c + d  O(n) 
Algoritmos e Estrutura de Dados II 
Exercício 
 Determine a equação de recorrência para a 
função abaixo. Qual a sua complexidade? 
void ex(vetor X, int n){ 
 int i; 
 
 if (n > 0) { 
 for(i=0; i<n-1; i++) 
 X[i] = 0; 
 X[n] = n; 
 ex(X,n-1); 
 } 
} 
Algoritmos e Estrutura de Dados II 
Outro Exemplo 
 Considere a seguinte função: 
 
Pesquisa(n) 
{ 
(1) if (n <= 1) 
(2) ‘ inspecione elemento ’ e termine; 
 else 
 { 
(3) para cada um dos n elementos ‘ inspecione elemento’; 
(4) Pesquisa(n/3) ; 
 } 
} 
 
Algoritmos e Estrutura de Dados II 
Análise da Função Recursiva 
 Qual a equação de recorrência? 
T(n) = n + T(n/3) 
T(1) = 1 
 
 Resolva a equação de recorrência 
 Dicas: 
 Pode fazer a simplificação de n será sempre 
divisível por 3 
 Somatório de uma PG finita: 
 
 






n
i
n
i
r
r
r
0
1
1
1
Algoritmos e Estrutura de Dados II 
Resolvendo a equação 
 Substitui-se os termos T(k), k < n, até que todos os termos 
T(k), k > 1, tenham sido substituídos por fórmulas contendo 
apenas T(1). 
1 → n/3K = 1 → n = 3K 1 
Algoritmos e Estrutura de Dados II 
Resolvendo a Equação 
 Considerando que T(n/3K) = T(1) temos: 
 
 
 
 Aplicando a fórmula do somatório de uma PG 
finita temos: 
 
 
O(n) 






n
i
n
i
r
r
r
0
1
1
1
1
3
1
)1(
3
)(
1
0
1
0
 




k
i
i
k
i
i
nT
n
nT
2123
)3/2()1(1
)3/2())/1(1(1
)3/11())3/1(1(1




n
n
nn
n k
Algoritmos e Estrutura de Dados II 
Outro Exemplo 
 Equação : 
 
 
 
 
 Essa equação lembra que tipo de problema? 
 
 Como resolver essa equação? 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
Algoritmos e Estrutura de Dados II 
Resolvendo a Equação 
)log.(log.).(log1.2.)2(2)(
:Logo
log12
)1()2(
:Parada de Condição acolocar Para
.)2(2)(
: termosos doSubstituin
)2(2)2(2
)8(8)4(4
)4(4)2(2
)2(2)(
:equação a Expandindo
1)1(
)2(2)(
222
log
2
11
2 nnOnnnnnninTnT
nin
TnT
ninTnT
nnTnT
nnTnT
nnTnT
nnTnT
T
nnTnT
nii
i
i
ii
iiii











