Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Estrutura de Dados e Algoritmos 1 Análise de Algoritmos Recursivos Prof. Cláudio Campelo, PhD Departamento de Sistemas & Computação / UFCG Perguntas pertinentes 2 � Quais são as características de um algoritmo recursivo? � Como encontrar o número de chamadas recursivas? � Como saber o tamanho da entrada de cada chamada? � Como analisar um algoritmo recursivo? 2 Background Matemático 3 � Somatórios � Linearidade ∑ = +++= n k kk aaaa 1 21 ... ∑ ∑ ∞ = = ∞→ = 1 1 lim k n k k n k aa Background Matemático 4 � Progressão aritmética � Progressão geométrica ),...,,,( 321 naaaa rnaan ).1(1 −+= ,...)16,13,10,7,4,1(:Ex 2 )( 1 n n aanS += ),...,,,( 321 naaaa ,...)64,32,16,8,4,2(:Ex 1 1. − = n n qaa 1 )1(1 − − = q qaS n n Soma dos termos de uma PG finita crescente 1||, 1 1 < − = ∞ q q aS Soma dos termos de uma PG infinita decrescente 3 Background Matemático 5 � Logarítmos baab ccc loglog)(log += abba log= ana b n b log.log = 1log =aa nnn 2loglglog == an bb na loglog = a bb c c a log loglog = Relações de recorrência 6 � Equações ou inequações que descrevem uma função em termos de seus valores (recursão) considerando entradas menores (mais simples). � Exemplo: � Métodos de resolução a serem vistos: � Iterativo � Mestre � TODO algoritmo recursivo tem uma relação de recorrência associada! 4 Visão Geral: Análise de Algoritmos Recursivos 7 int XYZ(int n, …) { … XYZ(…) } T(n)=T(n-..)... Algoritmo Recursivo Relação de Recorrência Método Mestre T = Θ(...) n2 … Θ(1) n2 n2/2 … n2/4 n2/4 n2/16 n2/4 n2/2 Método Iterativo T(n) = aT(n/b) + f(n) Se Caso 1 Se Caso 2 Se Caso 3 T = Θ(...) T = Θ(...) T = Θ(...) Método Iterativo 8 � Intuição MERGE-SORT(A) if n = 1 done. MERGE-SORT(A[1.. �n/2�]) MERGE-SORT(A[�n/2�+1..n]) “Merge” the 2 sorted lists merge: O(n) merge-sort(n/2) merge-sort(n/2) 5 Método Iterativo 9 � Intuição merge: O(n) merge-sort(n/4) merge: O(n/2) merge-sort(n/4) merge-sort(n/4) merge: O(n/2) merge-sort(n/4) MERGE-SORT(A) if n = 1 done. MERGE-SORT(A[1.. �n/2�]) MERGE-SORT(A[�n/2�+1..n]) “Merge” the 2 sorted lists Método Iterativo 10 � Árvore de recorrência � Visualização conveniente da expansão de uma relação de recorrência processamento recursivo das partes menores combinar as respostas do processamento recursivo 6 Método Iterativo 11 � Árvore de recorrência Série geométrica decrescente )( 2 )2/1/( )2/11/( )1/(1 2 2 2 2 n n n n qaSn Θ= = = −= −= )2/1...4/12/11(2 hn nS ++++= n grande � PG infinita Número de chamadas recursivas Tamanho da entrada Encontrando Relação 12 MERGE-SORT(A) if n = 1 done. MERGE-SORT(A[ 1.. n/2 ]) MERGE-SORT(A[ n/2 +1..n ]) “Merge” the 2 sorted lists Θ(1) n é o tamanho de A T(⌊n/2⌋) T(�n/2�) Θ(n) T(n) = T(⌊n/2⌋) + T(�n/2�) + Θ(n) T(n) = 2T(n/2) + Θ(n) Abuso, mas não muda o resultado 7 Exercício 1 13 � Encontre a relação de recorrência do algoritmo a seguir. int fatorial (int n) { if (n == 0) return 1; else return n * fatorial(n-1); } Exercício 1 14 � Encontre a relação de recorrência do algoritmo a seguir. int fatorial (int n) { if (n == 0) return 1; else return n * fatorial(n-1); } 8 Exercício 1 15 � Encontre a relação de recorrência do algoritmo a seguir. T (n) { if (n == 0) return 1; else return n * T(n-1); } Exercício 1 16 � Encontre a relação de recorrência do algoritmo a seguir. T (n) { if (n == 0) T(1) = 1 return 1; else return n * T(n-1); } 9 Exercício 1 17 � Encontre a relação de recorrência do algoritmo a seguir. T (n) { if (n == 0) Θ(1) return 1; else return n * T(n-1); } Exercício 1 18 � Encontre a relação de recorrência do algoritmo a seguir. T (n) { Θ(1) T(n-1); } 10 Exercício 1 19 � Encontre a relação de recorrência do algoritmo a seguir. T (n) = Θ(1) T(n-1); Exercício 1 20 � Encontre a relação de recorrência do algoritmo a seguir. T (n) = T(n-1) + Θ(1) T (n) = Θ(1) T(n-1); 11 Método Iterativo 21 � Como resolver a recorrência do merge sort? T(n) = Θ(1), se n=1 2T(n/2) + Θ(n), se n>1 Procedimento: Método Iterativo 22 1. Desenhe a árvore de recursão com base na relação de recorrência (T) (EXPANSÃO) 2. Encontre a maior altura (h) até o caso base 3. Some os custos de cada nível 4. Analise o relacionamento entre os custos de cada nível (RESOLUÇÃO DE TERMOS) 5. Some o custo de todos os níveis com base na relação encontrada em 4. PA, PG (q>1), PG (q<1)? 12 Método Iterativo 23 � Como resolver a recorrência do merge sort? � Que tal subtituir Θ(n) por cn ? T(n) = 2T(n/2) + cn T(n) = Θ(1), se n=1 2T(n/2) + Θ(n), se n>1 Método Iterativo (Resolvendo os termos) 24 T(n)T(n) = 2T(n/2) + cn 13 Método Iterativo (Resolvendo os termos) 25 T(n) = 2T(n/2) + cn T(n/2) T(n/2) cn Método Iterativo (Resolvendo os termos) 26 T(n/2) T(n/2) cn T(n) = 2T(n/2) + cn T(n/2) = 2T(n/4) + cn/2 14 Método Iterativo (Resolvendo os termos) T(n/4) T(n/4) T(n/4) T(n/4) cn/2 cn/2 cn T(n) = 2T(n/2) + cn T(n/2) = 2T(n/4) + cn/2 Método Iterativo (Resolvendo os termos) 28 cn/4 cn/2 cn/2 cn T(n/8) T(n/8) ... T(n) = 2T(n/2) + cn T(n/2) = 2T(n/4) + cn/2 T(n/4) = 2T(n/8) + cn/4 cn/4 cn/4 cn/4 ... ... 15 Método Iterativo (Resolvendo os termos) 29 cn/4 cn/2 cn/2 cn cn/8 cn/8 ... T(n) = 2T(n/2) + cn T(n/2) = 2T(n/4) + cn/2 T(n/4) = 2T(n/8) + cn/4 cn/4 cn/4 cn/4 ... ... ... cn/??? ... ... ... ... ... ... ... Método Iterativo (Resolvendo os termos) 30 cn/4 cn/2 cn/2 cn cn/8 cn/8 ... cn/4 cn/4 cn/4 ... ... ... cn/??? ... ... ... ... ... ... h=0 h=1 h=2 h=3 16 Método Iterativo (Resolvendo os termos) 31 cn/4 cn/2 cn/2 cn cn/8 cn/8 ... cn/4 cn/4 cn/4 ... ... ... cn/2h ... ... ... ... ... ... h=0 h=1 h=2 h=3 Método Iterativo (Resolvendo os termos) 32 cn/4 cn/2 cn/2 cn cn/8 cn/8 ... cn/4 cn/4 cn/4 ... ... ... ... ... ... ... ... ... h=0 h=1 h=2 h=3 cn/2h = k )/log(/22 kcnhkcnk cn h h =⇒=⇒=⇒ 17 Método Iterativo (Resolvendo os termos) 33 cn/4 cn/2 cn/2 cn cn/8 cn/8 ... cn/4 cn/4 cn/4 ... ... ... ... ... ... ... ... ... h=0 h=1 h=2 h=3 cn/2h = k )/log(/22 kcnhkcnk cn h h =⇒=⇒=⇒ h = log n Método Iterativo (Resolvendo os termos) 34 cn/4 cn/2 cn/2 cn cn/8 cn/8 ... cn/4 cn/4 cn/4 ... ... ... ... ... ... ... h=0 h=1 h=2 h=3 cn/2h cnh. cn cn cn cn cn 18 Método Iterativo (Resolvendo os termos) 35 cn/4 cn/2 cn/2 cn cn/8 cn/8 ... cn/4 cn/4 cn/4 ... ... ... ... ... ... ... h=0 h=1 h=2 h=3 cn/2h )log()(log. nncnncnh Θ⇒⇒ cn cn cn cn cn Exercício 2 36 � Utilize o método iterativo (utilizando a árvore de recursão para visualização) para resolver a recorrência a seguir: T(n) = 3T(n/2) + n2 T = O(n2) 19 Exercício 3 37 � Faça um algoritmo recursivo que realize uma busca sequencial em um elemento de um vetor. Qual a relação de recorrência? � Utilize o método iterativo (árvore de recursão) para resolver a recorrência. T(n) = T(n-1) + Θ(1) T = O(n) Método Mestre 38 � Provê um livro de receitas paraum bom número de recorrências da forma: � Onde a≥1 e b>1 são constantes e f(n) é uma função assintoticamente positiva. � Os a problemas são resolvidos recursivamente em T(n/b) e o tempo de dividir e combinar os resultados dos subproblemas é dado por f(n). T(n) = aT(n/b) + f(n) a=Número de subproblemas b=Tamanho do subproblema 20 Comparação Básica do Método 39 f(n) < f(n) = f(n) > Caso 1 Caso 2 Caso 3 T(n) = aT(n/b) + f(n) )()( log abnnT Θ= ))(()( nfnT Θ= )log).(( )log()( log nnf nnnT b b ab Θ= Θ= Teorema Mestre (Caso 1) 40 T(n) = aT(n/b) + f(n) Exemplo: 8log2n 8log2 21000 nn < 21 Procedimento: Método Mestre 41 1. Identifique a, b, f(n), log a 2. Verifique as condições sobre a≥1 e b>1 e f(n) 3. Compare f(n) com para identificar o caso 4. Confirme a condição do caso 5. Encontre o Θ b Teorema Mestre (Caso 2) 42 T(n) = aT(n/b) + f(n) Exemplo: 2log2n 2log210 nn = 22 Teorema Mestre (Caso 3) 43 T(n) = aT(n/b) + f(n) Exemplo: 2log2n 2log2 2nn > Exercício 4 44 � O método mestre pode ser aplicado nas seguintes recorrências? Justifique. 23 Exercício 4 45 � O método mestre pode ser aplicado nas seguintes recorrências? Justifique. a=2n não é constante a=0.5<1 f(n) não é não-negativa X X X Exercício 5 46 � Indique o limite assintoticamente restrito da recorrência T(n) = 2T(n/2) + n utilizando o método mestre 24 Exercício 6 47 � Uma busca binária acontece em arrays ordenados. � Se o elemento a ser buscado é o do meio do array então a busca termina. Senão � Se o elemento buscado é menor do que o elemento do meio então a busca se dá na primeira metade. Senão a busca se dá na segunda metade. boolean search(int x, int v[], int l, int r) { int m = (l + r) / 2; if (l > r) return false; if (x == v[m]) return m; if (x < v[m]) return search(x, v, l, m-1); else return search(x, v, m+1, r); } T(n) = T(n/2)+c Θ(log n) Exercício 7 48 � Considerando uma entrada ordenada. Qual dos algoritmos você escolheria para uma busca: seqüencial ou binária? Considere os algoritmos implementados anteriormente. 25 Referências 49 � Capítulos 1-4 � 1a edição � 2a edição
Compartilhar