Recorrências em Ciência da Computação - Análise de Complexidade e Recursividade

UNO CHAPECÓ Recorrências Prof Felipe Zeiser Ciência da Computação Unochapecó Sistemas de Informação Unochapecó Retomando O define um limite superior Ω define um limite inferior θ define um limite restrito Curiosidade Supondo que uma operação em um computador gasta em média 106 segundos Curiosidade Função de custo Tamanho n 10 20 30 40 50 60 n 000001 s 000002 s 000003 s 000004 s 000005 s 000006 s Curiosidade Função de custo Tamanho n 10 20 30 40 50 60 n 000001 s 000002 s 000003 s 000004 s 000005 s 000006 s n2 00001 s 00004 s 00009 s 00016 s 0035 s 00036 s Curiosidade Função de custo Tamanho n 10 20 30 40 50 60 n 000001 s 000002 s 000003 s 000004 s 000005 s 000006 s n2 00001 s 00004 s 00009 s 00016 s 0035 s 00036 s n3 0001 s 0008 s 0027 s 064 s 0125 s 0316 s Curiosidade Função de custo Tamanho n 10 20 30 40 50 60 n 000001 s 000002 s 000003 s 000004 s 000005 s 000006 s n2 00001 s 00004 s 00009 s 00016 s 0035 s 00036 s n3 0001 s 0008 s 0027 s 064 s 0125 s 0316 s n5 01 s 32 s 243 s 17 min 52 min 13 min Curiosidade Função de custo Tamanho n 10 20 30 40 50 60 n 000001 s 000002 s 000003 s 000004 s 000005 s 000006 s n2 00001 s 00004 s 00009 s 00016 s 0035 s 00036 s n3 0001 s 0008 s 0027 s 064 s 0125 s 0316 s n5 01 s 32 s 243 s 17 min 52 min 13 min 2n 0001 s 1 s 179 min 127 dias 357 anos 366 séc Curiosidade Função de custo Tamanho n 10 20 30 40 50 60 n 000001 s 000002 s 000003 s 000004 s 000005 s 000006 s n2 00001 s 00004 s 00009 s 00016 s 0035 s 00036 s n3 0001 s 0008 s 0027 s 064 s 0125 s 0316 s n5 01 s 32 s 243 s 17 min 52 min 13 min 2n 0001 s 1 s 179 min 127 dias 357 anos 366 séc 3n 0059 s 58 min 65 anos 3855 séc 108 séc 1013 séc Recursividade Recorrência Quando um algoritmo contém uma chamadas recursivas seu tempo de execução pode ser descrito por uma recorrência Recorrência Quando um algoritmo contém uma chamadas recursivas seu tempo de execução pode ser descrito por uma recorrência Como a gente pode analisar a complexidade de uma recursividade Recorrência Quando um algoritmo contém uma chamadas recursivas seu tempo de execução pode ser descrito por uma recorrência Como a gente pode analisar a complexidade de uma recursividade Para os algoritmos recursivos a ferramenta principal desta análise não é uma somatória mas um tipo especial de equação chamada relação de recorrência Recorrência Uma recorrência é uma equação ou desigualdade que descreve uma função em termos de seu valor em entradas menores Recorrência Para cada procedimento recursivo é associada uma função de complexidade 𝑇𝑛 desconhecida onde 𝑛 mede o tamanho dos argumentos para o procedimento Equação de recorrência maneira de definir uma função por uma expressão envolvendo a mesma função Qual a complexidade deste algoritmo Algoritmo Pesquisavetor if vetorsize 1 then inspecione elemento else inspecione cada elemento recebido vetor PesquisavetorsubLista1 vetorsize 3 end if end Qual a complexidade deste algoritmo Tn 1 size 1 n Tn3 caso contrário L1 Algoritmo Pesquisavetor L2 if vetorsize 1 then L3 inspecione elemento L4 else L5 inspecione cada elemento recebido vetor L6 PesquisavetorsubLista1 vetorsize 3 L7 end if L8 end Recorrência Tn 1 size 1 n Tn3 caso contrário Tn n Tn3 Recorrência Tn 1 size 1 n Tn3 caso contrário Tn n Tn3 Tn3 n3 Tn33 Recorrência Tn 1 size 1 n Tn3 caso contrário Tn n Tn3 Tn3 n33 Tn33 Tn33 n333 Tn333 Tn333 n3333 Tn3333 Recorrência Tn 1 size 1 n Tn3 caso contrário Tn n Tn3 Tn3 n33 Tn33 Tn33 n333 Tn333 Tn333 n3333 Tn3333 Tn333 n3333 Tn3333 T1 1 Recorrência Tn 1 size 1 n Tn3 caso contrário Tn n Tn3 Tn3 n33 Tn33 Tn33 n333 Tn333 Tn333 n3333 Tn3333 Tn333 n3333 Tn3333 T1 1 Tn n n3 n33 n333 1 Recorrência A fórmula representa a soma de uma série geométrica de razão 1 3 multiplicada por 𝑛 e adicionada de 𝑇 𝑛 3 3 3 3 Recorrência A fórmula representa a soma de uma série geométrica de razão 1 3 multiplicada por 𝑛 e adicionada de 𝑇 𝑛 3 3 3 3 Recorrência A fórmula representa a soma de uma série geométrica de razão 1 3 multiplicada por 𝑛 e adicionada de 𝑇 𝑛 3 3 3 3 Constante Recorrência Logo Tn é θn Constante Não é tão trivial encontrar a complexidade de tempo de algoritmos recursivos Exercício Faça a análise de recorrência do algoritmo que calcula o fibonacci de um número Faça a análise de recorrência do algoritmo que calcula o fatorial de um número Exercício Implemente os algoritmos de fatorial e fibonacci nas versões Iterativa Recursiva Referência Slides do livro CORMEN T H LEISERSON C E RIVEST R L STEIN C 2022 Introduction to Algorithms London The MIT Press Dúvidas Mãos à obra Muito Obrigado felipezeiserunochapecoedubr