Projeto e Análise de Algoritmos - Recorrência e relações de recorrência em algoritmos

[Música] Olá pessoal é nessa aula então a gente vai falar sobre recorrência né na verdade o assunto recorrência já apareceu né em outras aulas a gente inclusive vai relembrar né Um pouquinho na aula de hoje né mas a gente vai ver na aula de hoje que Normalmente quando eu tô trabalhando com algoritmo ser cursivos né eu consigo expressar o tempo de execução deles a partir de equações de recorrência tá então elas auxiliam a gente né a determinar o tempo de execução de um algoritmo né então a gente vai na aula de hoje né relembrar um

pouquinho né do uso da recorrência e no projeto de algoritmos e depois a gente vai inclusive pegar o algoritmo nerd sorte que foi o algoritmo que a gente viu né como um algoritmo recorrente aí né para ordenação de sequências e vamos analisar né o tempo de execução dele né aqui a equação de recorrência que descreve esse algoritmo Tá ok então vamos lá Então olha só que nem eu disse né formalmente nas aulas passadas né é a gente já se deparou com o assunto recorrência né a gente inclusive já deu uma breve definição para ela né

a gente disse que recorrência era uma expressão que descreve uma função em termos dela mesmo tá a gente viu também né que a indução e recorrência elas andam de mãos dadas né a gente viu quando a gente falou de indução né que a aplicação da indução vai me levar a o projeto de construção de algoritmo ser cursivos então a recorrência via de regra ela pode ajudar a gente a resolver problemas maiores a partir do conhecimento da solução de problemas menores relacionados àquele problema né então a estratégia de divisão em Conquista que a gente ainda vai

ver né ela soluciona problemas maiores dividindo os problemas né em problemas menores e utilizando a recorrência para combinar esses problemas então só para a gente ver alguns algumas situações né em que o uso da recorrência é importante tá então que nem a gente viu lá na aula de indução na aula de ordenação né aplicação da recursão ela pode ser uma estratégia poderosa aí no projeto que algoritmos né então algoritmo capaz de solucionar um problema para uma Instância menor né muitas vezes né se ele for progressivamente combinado né a gente pode obter uma solução para nossa

Instância de interesse né então quando o algoritmo contém uma chamada recursiva a si mesmo né a gente viu algoritmo recursivo né o tempo de execução que nem eu comentei no início da aula agora ele pode ser frequentemente descrito por uma equação de recorrência tá então o tempo de execução global para um problema de tamanho M Na verdade ele vai ser obtido a partir do tempo de execução para entradas de tamanho menor isso vai ficar mais claro a hora que a gente estudar o caso do nerd tá então para a gente aplicar né recorrência para um

determinado problema a gente precisa responder né seguinte pergunta né então dado uma Instância de tamanho M né existe uma estância menor que eu consigo né resolver e essa solução me ajuda a resolver nessa Instância de tamanho M tá então se a gente considerar lá o nosso o nosso algoritmo emerge sorte a gente viu que a resposta Era sim né Ou seja que que acontecia lá ele fazer na ordenação né para instâncias de tamanho menor na verdade a gente começou até com tamanho 1 né lá no último nível de recursão né eu conseguia resolver nesses problemas

eu conseguia resolver o problema de ordenação pro meu vetor de entrada né de tamanho M tá a gente viu também lá no cálculo do polinômio né quando a gente fez aquele algoritmo do polinômio na verdade né o processo de recorrência né Cada passo eu tava fazendo o quê calculando né um coeficiente do meu polinômio e eu ia somando né Essa soluções até obter a solução que correspondia ao meu polinômio como um todo né bom então vamos agora ver uma outra utilização da recorrência né que é na parte de análise de tempo né de algoritmo se

cursivos através de equações de recorrência tá então a gente vai utilizar a recorrência para calcular o tempo de execução do sorte que a gente viu né na aula sobre ordenação Então a gente tem que a gente tem que ter dinheiro né é o tempo de execução para um problema de tamanho M Então se a gente imaginar aqui primeiramente né Se eu tiver um problema de tamanho um né o tempo é constante então T de n seria simplesmente teta de um Por simplicidade né nessa análise que a gente vai fazer a gente vai supor né que

a nossa Instância de entrada é uma potência de dois tá porque é uma potência de dois Porque daí a hora que a gente for fazer é sempre que a gente dividir em subir problemas né a gente vai produzir sequência de tamanho n sobre dois tá não precisava ser assim mas uma questão de simplicidade tá no caso do algoritmo emerge sorte então cada passo em cada passo né o problema original ele é dividido em dois novos sobre problemas que tem metade do tamanho do problema original então para a gente analisar esses tempos a gente vai considerar

né que o tempo que a gente leva para dividir lá em cima naquele quando a gente tinha o algoritmo merge sorte quando eles chamam assim mesmo né então o que que ele precisa fazer ele precisa calcular o meio e precisa fazer duas chamadas cursivas a gente vai considerar que esse tempo é de Diene tá que é o tempo para dividir o problema em dois sobre problemas C de n a gente vai chamar como sendo o tempo né para ele combinar as soluções né então dado que ele recebeu o retorno né de duas recursões ele precisa

combinar aquilo ali então a gente vai chamar esse tempo de tempo CGN tá que é o tempo para combinar as soluções de 2 sobre problemas então a gente pode dizer que T de n né tirando que esse caso para n = 1 ele pode ser escrito como o tempo de execução para uma Instância de tamanho M vai ser duas vezes o tempo de execução para uma Instância de tamanho M sobre dois não porque eu divido né O meu problema em dois problemas exatamente iguais mas agora com metade do tamanho de entrada mas o tempo que

eu gasto para dividir mas o tempo que eu gasto para combinar tá então vamos tentar determinar quem são esses tempos aqui aqui só uma observação né sediane na verdade é o tempo do algoritmo combina daqui a pouco a gente vai analisar ele para ver que tempo que é esse então aqui a gente tem né A o pseu do código do combina Então se agora a gente for analisando linha a linha né que que eu tenho aqui na verdade nessas linhas aqui eu tenho simplesmente uma operação de som e atribuição na internet tempo constante tá aqui

quando eu crio aqueles vetores auxiliares que a gente que a gente viu quando a gente discutiu o algoritmo combina né simplesmente que que eu faço aqui de um até N1 eu simplesmente vou fazer a atribuição né dos valores que estão no vetor a para o vetor B né e de um de J né Igual a um até n2 eu vou fazer atribuição dos valores que estão né para o vetor C né então o que que eu vou gastar eu gasto executo essa linha aqui em uma vezes e essa linha duas vezes né se a gente

pegar aqui na verdade a gente sabe que N1 Mas n2 vai ser igual a n Então na verdade isso daqui é trata de n né Depois aqui eu tenho também né operações que tem tempo constante E aí eu tenho utilizar então agora né o tempo que eu gasto para executar esses laços aqui tá E aí tem um tempo se a gente perceber uma sutileza fica fácil da gente analisar esse tempo porque porque veja bem eu tenho esse primeiro laço E aí tenho um segundo laço aqui e um terceiro laço em J né no caso como

a gente até assumiu né que a nossa entrada era a potência de dois esses dois laços nem seriam executados né porque esses lados só executam quando na quebra um dos vetores tem tamanho diferente do outro tá Mas independente disso a gente percebe o que que o valor de k que corresponde ao que ao índice do vetor que está sendo ordenado tanto nesse laço quanto nesse laço quanto nesse laço ele é sempre incrementado cada vez que o laço é incrementado e a gente sabe que quantas vezes que ele vai ser incrementado ele vezes né porque o

vetor tem n posições então esses laços aqui Independente de da ordem que eles executem eles vão sempre gastar tempo ele né então eu tenho aqui n execuções né então ele execuções desses laços aqui então eu posso dizer que o tempo aqui é teta de n tá ok então CGN vai ser teta de bom então a gente já sabe que se a dieta de n bom a gente pode considerar que a etapa de dividir né ela apenas calcula o ponto médio né lembra ela simplesmente Calculava qualquer um meio e fazer a duas chamadas cursivas a gente

pode considerar que isso aqui tem tempo constante então somar a teta de n com teta de um né lembra lá da nossa discussão né que os termos de menor ordem eles não são significativos né então tetra Diene com teta de um a gente pode simplesmente dizer que isso daqui é teta de n Então a gente vai ter o que que o nosso tempo de execução vai ser né quando n é diferente de 1 vai ser dois t de n sobre dois mais teta de n né que esse daqui corresponde a parcela C de n mais

de n tá ok e aqui a gente tem né na verdade essa que seria o pior caso né para uma entrada de tamanho M Mas a questão que se coloca né como é que a gente resolve agora isso aqui não é porque eu resolvi essa parte aqui da equação mas essa daqui né como é que eu resolvo ela tá Então na verdade na próxima semana a gente vai estudar três estratégias para a gente resolver equações de recorrência né esse tipo de equação aqui tá a gente vai estudar o método da substituição vai estudar o método

da árvore de recursão e a gente vai também estudar o método mestre tá dependendo de como a minha equação de recorrência se apresenta né às vezes é mais interessante utilizar uma metodologia ou outra tá hoje só para a gente ter uma intuição né de qual que seria o tempo de execução dessa equação de recorrência aqui a gente vai utilizar eu vou contar para vocês aqui o método da árvore de recursão mas eu não vou formalizar ele a gente simplesmente vai tentar entender ele intuitivamente na semana que vem a gente formaliza e a gente vai verificar

que tgn nesse caso é a teta de n log n Tá então vamos ver como que a gente chega nesse resultado aqui Então olha só Então se a gente dá uma olhada aqui no nosso problema imaginando né as recursões ocorrendo que que vai acontecer lá no nível mais alto de recursão né aqui né onde eu ainda não fiz nenhuma recursão que que vai acontecer a minha entrada tem tamanho M E o tempo né o custo de execução né Essa é de n né é uma constante vezes n tá que é basicamente O que é operação

de divisão que a gente viu que era uma operação que levava tempo constante mas a execução do CN lá que era o nosso algoritmo combina que a gente viu que ele era um teta de n né um teta de n o que que é alguma coisa que eu consigo representar para uma função C vezes né uma constante vezes n tá então o meu custo aqui no nível mais alto é simplesmente E aí eu vou dividindo esses caras aqui a medida que eu vou descendo na recursão né então o que que vai acontecer aqui Eu tenho

esse custo C de n aqui e vou descer na recursão mas o que que acontece cada vez que eu faço uma chamada recursiva eu reparto o problema em dois né então agora eu tenho um problema com metade do tamanho do problema original e que vai ter metade do curso do problema original só que eu também tenho um outro problema né com metade do custo original Então na verdade esses dois problemas continuam tendo um custo seriene e a mesma coisa acontece aqui né eu divido por quatro mas eu multiplico por 4 então meu curso continua sendo

sempre ciente né então qual que vai ser o custo né Total aqui né o tempo total aqui quantos passos né na verdade a gente tá assim praticamente tentando responder que esse cara vai levar para resolver o meu problema né quanto tempo esse cara vai descer né eu vou fazer um recursões eu parto de n aí divido por n sobre dois depois n sobre 4 né dividindo sempre por potências até que eu chego no problema de tamanho 1 né então o que que eu tô dizendo na prática eu tô dizendo aqui olha eu tinha uma Instância

de tamanho M E eu vou dividir ela sucessivamente por dois por dois por dois até que eu chegue no tamanho 1 Então se a gente imaginar eu tô dizendo o que que n dividido por 2 elevado ao número de vezes que eu vou dividir esse problema tem que ser igual e aí fica fácil a continha então n é igual dois elevado a x né agora se aplicar log na base 2 dos dois lados eu vou chegar à conclusão o que né que x é igual a log de n Ou seja eu vou fazer log de

n recursões tá então eu tenho que eu tenho esse primeiro custo aqui mas esse custo C de n log de n vezes né que é o que está sendo dito aqui para gente né então a gente tem log de n recursões né então meu custo Global vai ser o quê vai ser CN log de n + né o primeiro custo lá no primeiro nível então ele vai ser CN log de n + CN tá isso daqui o que que é né eu posso desprezar esse cara Sobra para mim o que CN e log de n

isso daqui é tá Então essa é uma das maneiras né de da gente resolver Então na verdade o merge sorte ele tem tempo assim tóptico que n log de n tá então a gente já sabe agora qual que é o tempo de execução sintática do algoritmo de sorte bom nas próximas aulas né Na semana que vem a gente vai discutir né outras estratégias né para a partir de uma equação de recorrência que nem a gente viu aqui agora né a gente determinar o tempo de execução assintótipo de algoritmo Tá OK mas isso é assunto para

semana que vem até lá pessoal [Música] [Música]