Implementação do Algoritmo de Fatorial: Abordagens Iterativa e Recursiva

Introdução Implementação iterativa do algoritmo de fatorial Complexidade de tempo 1 Padrão de tipos por tamanho 2 include stdinth 3 Fatorial iterativo 4 uint64t fatorialuint32t n 5 uint64t r 1 6 foruint32t i 2 i n i 7 r r i 8 return r 9 fatorialn c1 c2 n 1 Θn C 2022 Bruno Prado Departamento de Computação UFS 2 42 Introdução Implementação iterativa do algoritmo de fatorial Complexidade de tempo 1 Padrão de tipos por tamanho 2 include stdinth 3 Fatorial iterativo 4 uint64t fatorialuint32t n 5 uint64t r 1 6 foruint32t i 2 i n i 7 r r i 8 return r 9 fatorialn c1 c2 n 1 Θn C 2022 Bruno Prado Departamento de Computação UFS 3 42 Introdução Implementação recursiva do algoritmo de fatorial Complexidade de tempo 1 Padrão de tipos por tamanho 2 include stdinth 3 Fatorial recursivo 4 uint64t fatorialuint32t n 5 ifn 0 6 return 1 7 else 8 return n fatorialn 1 9 fatorialn C 2022 Bruno Prado Departamento de Computação UFS 4 42 Introdução Implementação recursiva do algoritmo de fatorial Complexidade de tempo 1 Padrão de tipos por tamanho 2 include stdinth 3 Fatorial recursivo 4 uint64t fatorialuint32t n 5 ifn 0 6 return 1 7 else 8 return n fatorialn 1 9 fatorialn C 2022 Bruno Prado Departamento de Computação UFS 5 42 Relações de recorrência O que é uma relação recorrente É uma função recursiva que define uma sequência O que é uma função recursiva É uma função descrita em seus próprios termos Composta por duas partes Caso base Recorrência C 2022 Bruno Prado Departamento de Computação UFS 6 42 Relações de recorrência O que é uma relação recorrente É uma função recursiva que define uma sequência O que é uma função recursiva É uma função descrita em seus próprios termos Composta por duas partes Caso base Recorrência C 2022 Bruno Prado Departamento de Computação UFS 7 42 Relacdes de recorréncia Implementacdo recursiva do algoritmo de fatorial Caso base n 0 1 Padréo de tipos por tamanho 2 include stdinth 3 Fatorial recursivo 4 uint64t fatorialuint32t n 5 ifn 0 6 return 1 7 else 8 return n fatorialn 1 9 n0 fatorialn fatorialn11 nO C 2022 Bruno Prado Departamento de Computaado UFS 842 Relacdes de recorréncia Implementacdo recursiva do algoritmo de fatorial Recorréncia n 0 1 Padréo de tipos por tamanho 2 include stdinth 3 Fatorial recursivo 4 uint64t fatorialuint32t n 5 ifn 0 6 return 1 7 else 8 return n fatorialn 1 9 n0 fatorialn fatorialn11 nO C 2022 Bruno Prado Departamento de Computaado UFS 942 Relações de recorrência Como resolver estas relações de recorrência Método de substituição Método de árvore de recursão Método mestre C 2022 Bruno Prado Departamento de Computação UFS 10 42 Relagoes de recorréncia Método de substituicdo Tn fatorialn Tn n0 Tin11 nO0 C 2022 Bruno Prado Departamento de Computado UFS 1142 Relações de recorrência Método de substituição Encontrar um padrão nas substituições Tn Tn 1 1 Tn 2 1 1 Tn 3 1 2 Tn 4 1 3 Tn k k C 2022 Bruno Prado Departamento de Computação UFS 12 42 Relações de recorrência Método de substituição Encontrar um padrão nas substituições Tn Tn 1 1 Tn 2 1 1 Tn 3 1 2 Tn 4 1 3 Tn k k C 2022 Bruno Prado Departamento de Computação UFS 13 42 Relações de recorrência Método de substituição Encontrar um padrão nas substituições Tn Tn 1 1 Tn 2 1 1 Tn 3 1 2 Tn 4 1 3 Tn k k C 2022 Bruno Prado Departamento de Computação UFS 14 42 Relações de recorrência Método de substituição Encontrar um padrão nas substituições Tn Tn 1 1 Tn 2 1 1 Tn 3 1 2 Tn 4 1 3 Tn k k C 2022 Bruno Prado Departamento de Computação UFS 15 42 Relações de recorrência Método de substituição Encontrar um padrão nas substituições Tn Tn 1 1 Tn 2 1 1 Tn 3 1 2 Tn 4 1 3 Tn k k C 2022 Bruno Prado Departamento de Computação UFS 16 42 Relações de recorrência Método de substituição Aplicar o caso base para encontrar o valor de k Tn Tn k k Tn k 1 n k 0 k n Substituindo na equação Tn T0 n 1 n On C 2022 Bruno Prado Departamento de Computação UFS 17 42 Relações de recorrência Método de substituição Aplicar o caso base para encontrar o valor de k Tn Tn k k Tn k 1 n k 0 k n Substituindo na equação Tn T0 n 1 n On C 2022 Bruno Prado Departamento de Computação UFS 18 42 Relagoes de recorréncia Método de arvore de recursdo Tn fatorialn Tn n0 Tin11 nO0 C 2022 Bruno Prado Departamento de Computado UFS 1942 Relações de recorrência Método de árvore de recursão Solução gráfica Tn 1 Tn1 1 1 Tn2 1 1 1 T0 n 1 Tn n 1 On C 2022 Bruno Prado Departamento de Computação UFS 20 42 Relações de recorrência Método de árvore de recursão Solução gráfica Tn 1 Tn1 1 1 Tn2 1 1 1 T0 n 1 Tn n 1 On C 2022 Bruno Prado Departamento de Computação UFS 21 42 Relações de recorrência Método mestre Resolução de relações de recorrência no formato Tn aT n b fn a 1 número de subproblemas b 1 tamanho de cada subproblema fn assintoticamente positiva custo de combinar soluções C 2022 Bruno Prado Departamento de Computação UFS 22 42 Relações de recorrência Método mestre Caso 1 fn Onlogb aϵ com ϵ 0 Regra Tn Θnlogb a Exemplo Tn 4T n 2 n a 4 a 1 b 2 b 1 fn n n fn 0 fn n Onlogb aϵ 1 logb a ϵ ϵ log2 4 1 ϵ 1 Tn Θn2 C 2022 Bruno Prado Departamento de Computação UFS 23 42 Relações de recorrência Método mestre Caso 2 fn Θnlogb a Regra Tn Θnlogb a log n Exemplo Tn 2T n 2 n a 2 a 1 b 2 b 1 fn n n fn 0 fn n Θnlogb a 1 logb a 1 log2 2 1 1 Tn Θnlog2 2 log n Θn log n C 2022 Bruno Prado Departamento de Computação UFS 24 42 Relações de recorrência Método mestre Caso 3 fn Ωnlogb aϵ com ϵ 0 af n b cfn c 1 e n suficientemente grande Regra Tn Θfn Exemplo Tn 2T n 2 n2 a 2 a 1 b 2 b 1 fn n2 n fn 0 fn n2 Ωnlogb aϵ 2 logb a ϵ ϵ 2 log2 2 ϵ 1 C 2022 Bruno Prado Departamento de Computação UFS 25 42 Relações de recorrência Método mestre Caso 3 fn Ωnlogb aϵ com ϵ 0 af n b cfn c 1 e n suficientemente grande Regra Tn Θfn Exemplo Tn 2T n 2 n2 a 2 a 1 b 2 b 1 fn n2 n fn 0 af n b cfn n2 2 cn2 n c 1 2 Tn Θfn Θn2 C 2022 Bruno Prado Departamento de Computação UFS 26 42 Relações de recorrência Método mestre É preciso memorizar os casos Não resolve todas as recorrências como no cálculo do fatorial e da sequência de Fibonacci C 2022 Bruno Prado Departamento de Computação UFS 27 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Caso base n 1 1 Padrão de tipos por tamanho 2 include stdinth 3 Fibonacci recursivo 4 uint64t fibonacciuint32t n 5 ifn 1 6 return n 7 else 8 return fibonaccin 1 fibonaccin 2 9 fibonaccin 0 n 0 1 n 1 fibonaccin 1 fibonaccin 2 n 1 C 2022 Bruno Prado Departamento de Computação UFS 28 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Recorrência n 1 1 Padrão de tipos por tamanho 2 include stdinth 3 Fibonacci recursivo 4 uint64t fibonacciuint32t n 5 ifn 1 6 return n 7 else 8 return fibonaccin 1 fibonaccin 2 9 fibonaccin 0 n 0 1 n 1 fibonaccin 1 fibonaccin 2 n 1 C 2022 Bruno Prado Departamento de Computação UFS 29 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Método da substituição Tn Tn 1 Tn 2 2Tn 2 Tn 3 3Tn 3 2Tn 4 5Tn 4 3Tn 5 8Tn 5 5Tn 6 rn1Tn 1 rn2Tn 2 rn rn1 rn2 r2 r 1 0 r12 1 5 2 Recorrência de segunda ordem com raízes distintas C 2022 Bruno Prado Departamento de Computação UFS 30 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Método da substituição Tn Tn 1 Tn 2 2Tn 2 Tn 3 3Tn 3 2Tn 4 5Tn 4 3Tn 5 8Tn 5 5Tn 6 rn1Tn 1 rn2Tn 2 rn rn1 rn2 r2 r 1 0 r12 1 5 2 Recorrência de segunda ordem com raízes distintas C 2022 Bruno Prado Departamento de Computação UFS 31 42 Relagoes de recorréncia Implementacdo recursiva do algoritmo de Fibonacci Raizes distintas Tn ar Br 0 0 10 aLtv aetev o 2 2 1 1 14 V5 1v5 T1 a a54 n n rn 1v5 1 f1v5 5 ie 5 Tn x 16 06 O16 n 5 a 16 C 2022 Bruno Prado Departamento de Computado UFS 3242 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Método da árvore de recursão T5 T4 T3 T2 T1 T0 T1 T2 T1 T0 T3 T2 T1 T0 T1 Árvore com altura n e em cada nó existem 2 filhos Complexidade é O2n C 2022 Bruno Prado Departamento de Computação UFS 33 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Método da árvore de recursão T5 T4 T3 T2 T1 T0 T1 T2 T1 T0 T3 T2 T1 T0 T1 Árvore com altura n e em cada nó existem 2 filhos Complexidade é O2n C 2022 Bruno Prado Departamento de Computação UFS 34 42 Relações de recorrência Implementação iterativa do algoritmo de Fibonacci 1 Padrão de tipos por tamanho 2 include stdinth 3 Fibonacci iterativo 4 uint64t fibonacciuint32t n 5 uint64t r n tn2 0 tn1 1 6 foruint32t i 1 i n i 7 r tn2 tn1 8 tn2 tn1 9 tn1 r 10 11 return r 12 fibonaccin c1 3 c2 n 1 Θn C 2022 Bruno Prado Departamento de Computação UFS 35 42 Relações de recorrência Implementação iterativa do algoritmo de Fibonacci 1 Padrão de tipos por tamanho 2 include stdinth 3 Fibonacci iterativo 4 uint64t fibonacciuint32t n 5 uint64t r n tn2 0 tn1 1 6 foruint32t i 1 i n i 7 r tn2 tn1 8 tn2 tn1 9 tn1 r 10 11 return r 12 fibonaccin c1 3 c2 n 1 Θn C 2022 Bruno Prado Departamento de Computação UFS 36 42 Exemplo Identifique qual dos algoritmos jd visto possui a seguinte recorréncia Resolva a recorréncia para determinar a complexidade n Tn Tn1n n 1 C 2022 Bruno Prado Departamento de Computado UFS 3742 Exemplo Método da substituição Série aritmética Tn Tn 1 n Tn 2 n 1 n Tn 3 n 2 n 1 n T1 n 2 n 1 n nn 1 2 n2 n 2 On2 C 2022 Bruno Prado Departamento de Computação UFS 38 42 Exemplo Método da substituição Série aritmética Tn Tn 1 n Tn 2 n 1 n Tn 3 n 2 n 1 n T1 n 2 n 1 n nn 1 2 n2 n 2 On2 C 2022 Bruno Prado Departamento de Computação UFS 39 42 Exemplo Método da substituição Série aritmética Tn Tn 1 n Tn 2 n 1 n Tn 3 n 2 n 1 n T1 n 2 n 1 n nn 1 2 n2 n 2 On2 C 2022 Bruno Prado Departamento de Computação UFS 40 42 Exemplo Método da substituição Série aritmética Tn Tn 1 n Tn 2 n 1 n Tn 3 n 2 n 1 n T1 n 2 n 1 n nn 1 2 n2 n 2 On2 C 2022 Bruno Prado Departamento de Computação UFS 41 42