Baixe o app para aproveitar ainda mais
Prévia do material em texto
Algoritmos e Estrutura de Dados II Análise de Algoritmos Recursivos n Para cada procedimento recursivo é associada uma função de complexidade f(n) desconhecida, onde n mede o tamanho dos argumentos para o procedimento. n Por se tratar de um algoritmo recursivo, f(n) vai ser obtida através de uma equação de recorrência. n 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 Análise de Algoritmos Recursivos n Tempo de execução de um algoritmo recursivo: tamanho, número de subproblemas e o tempo para decomposição. n Capturado pela equação de recorrência. ⎩ ⎨ ⎧ ≤= >+= cnknT cn nfbnaTnT para ,)( para ),()/()( Algoritmos e Estrutura de Dados II Equação de Recorrência Fat (int n) { if (n <= 0) return 1; else return n * Fat(n-1); } Algoritmos e Estrutura de Dados II Fat (int n) { if (n <= 0) return 1; else return n * Fat(n-1); } n Equação de recorrência para o Fatorial T(n) = c + T(n-1), para n > 0 T(n) = d. para n ≤ 0 Equação de Recorrência Algoritmos e Estrutura de Dados II Equação de Recorrência void max(int *v, int e, int d){ int u, v; int m = (e+d)/2; if (e == d) return v[e]; u = max(v, e, m); v = max(v, m+1, d); if (u > v) return u; else return v; } Algoritmos e Estrutura de Dados II Equação de Recorrência void max(int *v, int e, int d){ int u, v; int m = (e+d)/2; if (e == d) return v[e]; u = max(v, e, m); v = max(v, m+1, d); if (u > v) return u; else return v; } T(n) = 2T(n/2) + 1, para n > 1 T(n) = 0. para n ≤ 1 Algoritmos e Estrutura de Dados II Exercício 1 n Determine a equação de recorrência para a função abaixo (operação relevante: atribuição para vetor X). 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 Exercício 1 n Determine a equação de recorrência para a função abaixo (operação relevante: atribuição para vetor X). 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); } } ⎩ ⎨ ⎧ ≤= >−+= 0 para ,0)( 0 para ),1()( nnT n nTnnT Algoritmos e Estrutura de Dados II Outro Exemplo n 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 Outro Exemplo n 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) ; } } ⎩ ⎨ ⎧ ≤= >+= 1 para ,1)( 1 para ),3/()( nnT n nTnnT Algoritmos e Estrutura de Dados II Análise de Algoritmos Recursivos n Abordagem para solução da recorrência: q Expande a árvore de recursão q Calcula o custo em cada nível da árvore q Soma os custos de todos os níveis q Calcula a fórmula fechada do somatório Algoritmos e Estrutura de Dados II Fat (int n) { if (n <= 0) return 1; else return n * Fat(n-1); } n Equação de recorrência para o Fatorial T(n) = c + T(n-1), para n > 0 T(n) = d. para n ≤ 0 Equação de Recorrência Algoritmos e Estrutura de Dados II Equação de Recorrência Fat (int n) { if (n <= 0) return 1; else return n * Fat(n-1); } n Se n <= 0 faz uma operação de custo constante n 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 Fat (int n) { if (n <= 0) return 1; else return n * Fat(n-1); } n Equação de recorrência para o Fatorial T(n) = c + T(n-1), para n > 0 T(n) = d. para n ≤ 0 Algoritmos e Estrutura de Dados II Resolvendo a Equação de Recorrência n Existem várias formas de se resolver uma equação de recorrência n A mais simples é expandir a equação e depois fazer uma substituição dos termos n Ex. Fatorial: T(n) = c + T(n-1) T(n-1) = c + T(n-2) T(n-2) = c + T(n-3) ... T(1) = c + T(0) T(0) = d T(n) = c + c + c + ... + c + d n vezes T(n) = n.c + d à O(n) Algoritmos e Estrutura de Dados II Equação de Recorrência void max(int *v, int e, int d){ int u, v; int m = (e+d)/2; if (e == d) return v[e]; u = max(v, e, m); v = max(v, m+1, d); if (u > v) return u; else return v; } T(n) = 2T(n/2) + 1, para n > 1 T(n) = 0. para n ≤ 1 Algoritmos e Estrutura de Dados II Exercício 1 n Determine a equação de recorrência para a função abaixo (operação relevante: atribuição para vetor X). 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); } } ⎩ ⎨ ⎧ ≤= >−+= 0 para ,0)( 0 para ),1()( nnT n nTnnT Algoritmos e Estrutura de Dados II Outro Exemplo n Equação : n Essa equação lembra que tipo de problema? n 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 =+=+=+= =→= → += += += += += = += −− Algoritmos e Estrutura de Dados II Exercício n 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 n Equação de recorrência n Resolva a equação de recorrência q Dicas: q Pode fazer a simplificação de n será sempre divisível por 3 q Somatório de uma PG finita: ∑ = + − − = n i n i r rr 0 1 1 1 ⎩ ⎨ ⎧ ≤= >+= 1 para ,1)( 1 para ),3/()( nnT n nTnnT Algoritmos e Estrutura de Dados II Resolvendo a equação n 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 rr 0 1 1 1 1 3 1)1( 3 )( 1 0 1 0 +=+= ∑∑ − = − = k i i k i i nT nnT 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 Teorema Mestre n Método “receita de bolo” para resolver recorrências do tipo n Este tipo de recorrência é típico de algoritmos“dividir para conquistar” q Dividem um problema em a subproblemas q Cada subproblema tem tamanho n/b q Custo para dividir e combinar os resultados é f(n) positiva )( e , onde )()/()( nfba nfbnaTnT 11 >≥ += Algoritmos e Estrutura de Dados II Teorema Mestre n Seja )()/()( nfbnaTnT += )).((Θ)( temos , para )()/( se e para )(Ω)( Se ).log(Θ)( temos ,)(Θ)( Se ).(Θ)( temos , com ,)()( Se log log log log log nfnT cncfbnafnnf nnnT nnf nnT nOnf a a a a a b b b b b = <≤>= = = = >= + − 10 0 � � � � Algoritmos e Estrutura de Dados II Teorema Mestre n O resultado da recorrência depende da comparação entre n Note que a diferença entre tem que ser polinomial, isto é, tem que ser pelo menos abnnf log e )( abnnf log e )( �n Teorema Mestre (1) n Resolva a recorrência usando o teorema mestre n Caso 1 se aplica, temos nnTnT += )/()( 39 )(Θ)( 2nnT = )).(()( temos ,1 para )()/( se e 0 para )()( Se 3. ).log()( temos ,)()( Se 2. ).()( temos ,0 com ,)()( Se 1. log log log log log nfnT cncfbnafnnf nnnT nnf nnT nOnf a a a a a b b b b b Θ= <≤>Ω= Θ= Θ= Θ= >= + − ε ε ε ε )()/()( nfbnaTnT += • g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m • g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m • g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m Teorema Mestre (2) n Resolva a recorrência usando o teorema mestre n Caso 2 se aplica, temos 132 += )/()( nTnT ))(log(Θ)( nnT = )).(()( temos ,1 para )()/( se e 0 para )()( Se 3. ).log()( temos ,)()( Se 2. ).()( temos ,0 com ,)()( Se 1. log log log log log nfnT cncfbnafnnf nnnT nnf nnT nOnf a a a a a b b b b b Θ= <≤>Ω= Θ= Θ= Θ= >= + − ε ε ε ε )()/()( nfbnaTnT += • g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m • g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m • g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m Teorema Mestre (3) n Resolva a recorrência usando o teorema mestre n Caso 3 se aplica, temos nnnTnT log)4/(3)( += )log()( nnnT Θ= )).(()( temos ,1 para )()/( se e 0 para )()( Se 3. ).log()( temos ,)()( Se 2. ).()( temos ,0 com ,)()( Se 1. log log log log log nfnT cncfbnafnnf nnnT nnf nnT nOnf a a a a a b b b b b Θ= <≤>Ω= Θ= Θ= Θ= >= + − ε ε ε ε )()/()( nfbnaTnT += • g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m • g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m • g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m Teorema Mestre (4) n Novamente a equação de recorrência: T(n) = 2T(n/2) + n; T(1) = 1; T(n) = 2T(n/2) + n; T(1) = 1; )).(()( temos ,1 para )()/( se e 0 para )()( Se 3. ).log()( temos ,)()( Se 2. ).()( temos ,0 com ,)()( Se 1. log log log log log nfnT cncfbnafnnf nnnT nnf nnT nOnf a a a a a b b b b b Θ= <≤>Ω= Θ= Θ= Θ= >= + − ε ε ε ε )()/()( nfbnaTnT += • g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m • g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m • g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m Algoritmos e Estrutura de Dados II Teorema Mestre (5) n Resolva a recorrência n Nenhum caso do teorema mestre de aplica nnnTnT log)/()( += 22 T(n) = 2T(n/2) + n; T(1) = 1; )).(()( temos ,1 para )()/( se e 0 para )()( Se 3. ).log()( temos ,)()( Se 2. ).()( temos ,0 com ,)()( Se 1. log log log log log nfnT cncfbnafnnf nnnT nnf nnT nOnf a a a a a b b b b b Θ= <≤>Ω= Θ= Θ= Θ= >= + − ε ε ε ε )()/()( nfbnaTnT += • g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m • g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m • g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m
Compartilhar