Analise de Algoritmos Recursivos - Radix Quicksort e Fibonacci com Funcoes Geradoras

Análise de Algoritmos Berilhes Análise de Algoritmos Recursivos Radix Quicksort Análise de Algoritmos Recursivos Radix Quicksort Exemplo Análise de Algoritmos Recursivos Radix Quicksort Exemplo Análise de Algoritmos Recursivos Radix Quicksort Exemplo RADIXQUICKSORTA l r b 1 if l r and b 0 2 i l 3 j r 4 while i j 5 while BITSAi b 1 0 and i j i i 1 6 while BITSAj b 1 1 and j i j j 1 7 Ai Aj 8 if BITSAi b 1 0 9 j j 1 10 RADIXQUICKSORTA l j 1 b 1 11 RADIXQUICKSORTA l j b 1 Análise de Algoritmos Recursivos Radix Quicksort Exemplo RADIXQUICKSORTA l r b 1 if l r and b 0 2 i l 3 j r 4 while i j 5 while BITSAi b 1 0 and i j i i 1 6 while BITSAj b 1 1 and j i j j 1 7 Ai Aj 8 if BITSAi b 1 0 9 j j 1 10 RADIXQUICKSORTA l j 1 b 1 11 RADIXQUICKSORTA l j b 1 O custo Cn medido como número de comparações de bits Cn n 12n Σk n k Ck Cnk se n 1 0 se n 0 ou n 1 Análise de Algoritmos Recursivos Fibonacci Análise de Algoritmos Recursivos Fibonacci Exemplo Análise de Algoritmos Recursivos Fibonacci Exemplo Análise de Algoritmos Recursivos Fibonacci Exemplo Fibonaccin 1 if n 0 2 return 0 3 elseif n 1 4 return 1 5 else return Fibonaccin1 Fibonaccin2 Análise de Algoritmos Recursivos Fibonacci Exemplo Fibonaccin 1 if n 0 2 return 0 3 elseif n 1 4 return 1 5 else return Fibonaccin1 Fibonaccin2 O custo Cn medido como número de chamadas recursivas do algoritmo Fibonacci satisfaz a seguinte recorrência Cn Cn1 Cn2 2 se n 1 0 se n 0 ou n 1 Análise de Algoritmos Recursivos Ideia THE MOST POWERFUL WAY to deal with sequences of numbers as far as anybody knows is to manipulate infinite series that generate those sequences Donald E Knuth Análise de Algoritmos Recursivos Ideia THE MOST POWERFUL WAY to deal with sequences of numbers as far as anybody knows is to manipulate infinite series that generate those sequences Donald E Knuth Análise de Algoritmos Recursivos Funções Geradoras Uma das ferramentas mais úteis na análise de algoritmos é o conceito de funções geradoras Uma das ferramentas mais úteis na análise de algoritmos é o conceito de funções geradoras Uma sequência infinita a₀ a₁ a₂ que nós desejamos manipular pode ser convenientemente representada como uma série de potências em uma variável auxiliar z Uma das ferramentas mais úteis na análise de algoritmos é o conceito de funções geradoras Uma sequência infinita a₀ a₁ a₂ que nós desejamos manipular pode ser convenientemente representada como uma série de potências em uma variável auxiliar z Az a₀ a₁z a₂z² ₙ0 aₙzⁿ 1 Uma das ferramentas mais úteis na análise de algoritmos é o conceito de funções geradoras Uma sequência infinita a₀ a₁ a₂ que nós desejamos manipular pode ser convenientemente representada como uma série de potências em uma variável auxiliar z Az a₀ a₁z a₂z² n0 an zn 1 Az é chamada de função geradora ordinária da sequência a₀ a₁ a₂ Análise de Algoritmos Recursivos Funções Geradoras cont Uma função geradora é útil porque ela é uma fórmula única que representa uma sequência infinita Nós denotaremos por zn Az o coeficiente de zn em Az ou seja an Análise de Algoritmos Recursivos Funções Geradoras cont Uma função geradora é útil porque ela é uma fórmula única que representa uma sequência infinita Nós denotaremos por zn Az o coeficiente de zn em Az ou seja an Análise de Algoritmos Recursivos Funções Geradoras cont Uma função geradora é útil porque ela é uma fórmula única que representa uma sequência infinita Nós denotaremos por zn Az o coeficiente de zn em Az ou seja an Análise de Algoritmos Recursivos Funções Geradoras cont Dado uma função geradora Az como nós podemos encontrar recuperar seus coeficientes a0 a1 a2 Teorema Se Az é a função geradora ordinária para uma sequência a0 a1 a2 então an An0 n onde Anz é a nésima derivada de Az Análise de Algoritmos Recursivos Funções Geradoras cont Dado uma função geradora Az como nós podemos encontrar recuperar seus coeficientes a0 a1 a2 Teorema Se Az é a função geradora ordinária para uma sequência a0 a1 a2 então an An0 n onde Anz é a nésima derivada de Az Análise de Algoritmos Recursivos Funções Geradoras cont Dado uma função geradora Az como nós podemos encontrar recuperar seus coeficientes a0 a1 a2 Teorema Se Az é a função geradora ordinária para uma sequência a0 a1 a2 então an An0 n onde Anz é a nésima derivada de Az Análise de Algoritmos Recursivos Funções Geradoras cont O número de chamadas recursivas do algoritmo Fibonacci é n 0 1 2 3 4 5 6 7 8 9 Cn 0 0 2 4 8 14 24 40 66 108 A função geradora ordinária é Cz 2z2 1z1zz2 Series2z21 z1 z z2 z 0 8 2z2 4z3 8z4 14z5 24z6 40z7 Oz8 Análise de Algoritmos Recursivos Funções Geradoras cont O número de chamadas recursivas do algoritmo Fibonacci é n 0 1 2 3 4 5 6 7 8 9 Cn 0 0 2 4 8 14 24 40 66 108 A função geradora ordinária é Cz 2z2 1z1zz2 Series2z21 z1 z z2 z 0 8 2z2 4z3 8z4 14z5 24z6 40z7 Oz8 Análise de Algoritmos Recursivos Funções Geradoras cont O número de chamadas recursivas do algoritmo Fibonacci é n 0 1 2 3 4 5 6 7 8 9 Cn 0 0 2 4 8 14 24 40 66 108 A função geradora ordinária é Cz 2z2 1z1zz2 Series2z21 z1 z z2 z 0 8 2z2 4z3 8z4 14z5 24z6 40z7 Oz8 Análise de Algoritmos Recursivos Funções Geradoras cont O número de chamadas recursivas do algoritmo Fibonacci é n 0 1 2 3 4 5 6 7 8 9 Cn 0 0 2 4 8 14 24 40 66 108 A função geradora ordinária é Cz 2z2 1z1zz2 Series2z21 z1 z z2 z 0 8 2z2 4z3 8z4 14z5 24z6 40z7 Oz8 Análise de Algoritmos Recursivos Funções Geradoras cont O número de chamadas recursivas do algoritmo Fibonacci é n 0 1 2 3 4 5 6 7 8 9 Cn 0 0 2 4 8 14 24 40 66 108 A função geradora ordinária é Cz 2z2 1z1zz2 Series2z21 z1 z z2 z 0 8 2z2 4z3 8z4 14z5 24z6 40z7 Oz8 SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1 1 1 1 n0 zn 11z 0 1 2 3 4 n n0 n zn 11z² 0 0 1 3 6 10 n choose 2 n2 n choose 2 zn z²1z³ 0 0 1 m1 n choose m nm n choose m zn zm1zm1 1 m m choose 2 m choose n m 1 n0 m choose n zn 1zm 1 m1 m2 choose 2 m3 choose 3 n0 nm choose n zn 11zm1 1 0 1 0 1 0 n0 z2n 11z² Análise de Algoritmos Recursivos Operações sobre Funções Geradoras Ordinária BALANCEAMENTO Se Az n0 aₙzⁿ é a função geradora ordinária da sequência a₀ a₁ a₂ então Acz n0 cⁿzⁿ é a função geradora ordinária de c⁰a₀ c¹a₁ c²a₂ Sequência Função Geradora Ordinária 1111 n0 zⁿ 11z 124816 2ⁿ BALANCEAMENTO Se Az n0 aₙzⁿ é a função geradora ordinária da sequência a₀ a₁ a₂ então Acz n0 cⁿzⁿ é a função geradora ordinária de c⁰a₀ c¹a₁ c²a₂ Sequência Função Geradora Ordinária 1111 n0 zⁿ 11z 124816 2ⁿ n0 2ⁿzⁿ 112z Análise de Algoritmos Recursivos Operações sobre Funções Geradoras Ordinária cont Adição Se Az n0 an zn é a função geradora ordinária de a0 a1 a2 e Bz n0 bn zn é a FGO de b0 b1 b2 então Az Bz é a FGO de a0 b0 a1 b1 a2 b2 Sequência Função geradora ordinária 1 1 1 1 n0 zn 11z 1 2 4 2n n0 2n zn 112z 0 1 3 2n 1 Adição Se Az n0 an zn é a função geradora ordinária de a0 a1 a2 e Bz n0 bn zn é a FGO de b0 b1 b2 então Az Bz é a FGO de a0 b0 a1 b1 a2 b2 Sequência Função geradora ordinária 1 1 1 1 n0 zn 11z 1 2 4 2n n0 2n zn 112z 0 1 3 2n 1 n2 2n 1 zn 112z 11z Análise de Algoritmos Recursivos Operações sobre Funções Geradoras Ordinária cont DIFERENCIAÇÃO Se Az n0 aₙ zⁿ é a função geradora ordinária da sequência a₀ a₁ a₂ então zAz n1 naₙ zⁿ é a função geradora ordinária de 0 a₁ 2a₂ 3a₃ naₙ DIFERENCIAÇÃO Se Az n0 aₙ zⁿ é a função geradora ordinária da sequência a₀ a₁ a₂ então zAz n1 naₙ zⁿ é a função geradora ordinária de 0 a₁ 2a₂ 3a₃ naₙ Análise de Algoritmos Recursivos Operações sobre Funções Geradoras Ordinária cont DIFERENCIAÇÃO Se Az n0 an zn é a função geradora ordinária da sequência a0 a1 a2 então zAz n1 n an zn é a função geradora ordinária de 0 a1 2 a2 3 a3 n an SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1 1 1 1 n0 zn 11 z 0 1 2 3 4 n n0 n zn z 1 z2 0 0 1 3 6 n 2 n2 n 2 zn z2 1 z3 0 0 1 m 1 n m Análise de Algoritmos Recursivos Operações sobre Funções Geradoras Ordinária cont DIFERENCIAÇÃO Se Az n0 an zn é a função geradora ordinária da sequência a0 a1 a2 então zAz n1 n an zn é a função geradora ordinária de 0 a1 2 a2 3 a3 n an SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1 1 1 1 n0 zn 11 z 0 1 2 3 4 n n0 n zn z 1 z2 0 0 1 3 6 n 2 n2 n 2 zn z2 1 z3 0 0 1 m 1 n m nm n m zn zm 1 zm1