Método da árvore de recursão (resolvendo recorrências)

Se não desse vídeo A gente vai ver um terceiro método de resolução né de recorrências esse aqui é o aumento dos a árvore de recursão e a ideia é que a gente vai analisar uma árvore de recursão uma árvore que representa né a recursão que está sendo feita lá no no algoritmo Só que aí o que a gente vai deixar claro nessa árvore né bom cada nova certamente Vai representar um problema ou uma chamada recursiva é só que a gente vai rotular esse nor com o tempo que gasto naquela chamada desconsiderando então o tempo os

tempos nas chamadas recursivas né que os nossos algoritmos eles em geral quando eles vão cair no caso base né eles vão fazer alguma coisa até eventualmente fazer hoje eu mandei por cima né Isso gasta um certo tempo então esse é o tempo que vai ficar lá no rótulo como rótulo né do nome e um novo eventualmente ele vai ter filhos e as espelho significa Justamente que ele fez chamadas recursivas certo então se a árvore toda está representando todas as chamadas recursivas que estão sendo feitas né todas as chamadas estão sendo feitas durante toda a execução

do programa e cada nota tem o tempo que a gasto em cada chamada somar todos esses nós vai dar para a gente o tempo de execução do algoritmo porque a gente costuma fazer em geral é eu vou encontrar o tempo que gasto num nível da árvore E aí eu vou falar para todos os níveis da árvore Então como qualquer o que eu costumo dar aqui fica mais fácil de entender com o exemplo né é vão resolver essa recorrência aqui de dinheiro certo então é de novo né Qualquer ideia do que que está sendo descrito nas

recorrência o tempo para resolver uma entrada de tamanho n = o tempo de duas chamadas recursivas de entradas de tamanho sobre 2 mais um tempo de coisas que são feitas fora na chamada né antes de fazer uma chamada recursiva que nesse caso o que é certo então quando a gente vai fazer uma árvore recursão na em geral porque a gente fala ele tem esse nós que eu nova chamada para o problema de tamanho l esse problema aqui então ele faz uma chamada né para problema de tamanho ele sobre doenças no caso que ele faz duas

chamadas é para problemas de tamanho em sobre 2 E aí o problema de tamanho em São duas como é que ele é resolvido bom aí é uma chamada desse algoritmo também então vai também vai fazer duas chamadas recursivas para problemas com metade do tamanho dele né E se ele tem que tamanho ele sobre dois as chamadas vou segurar problemas de tamanho sobre quatro mesma coisa para os dois filhos desse desse desse problema aqui e a esses problemas esse como é que essa chamada vai agir como fazer duas chamadas de tamanho em sobre quatro olhar dois

duas chamadas né da problemas de tamanho ele sobre Oi bem como todas essas outras aqui só que isso não vai se dar para sempre né de atualmente a gente vai fazer tantas chamadas está reduzindo tanto né aqui a gente vai chegar lá em problemas de tamanho 17 Estação nossa árvore aqui vai ter um momento lá em que os programas o tamanho 1 e aí as chamadas para a árvore para né é só isso aqui não vai acontecer para sempre né a gente tá sempre reduzindo o tamanho do problema então ele atualmente a gente vai chegar

problemas de tamanho um certo a nossa árvore aqui tem um momento de todos os nossos vão ter tamanho um que faltou eu colocar nessa árvore né como eu disse lá na introdução a gente vai rosto lá os nós com o tempo que gasto naquele enorme então quando eu olho para esse não aqui né então ele referente aquele aquela Instância de tamanho n e eu tô vendo que para resolver isso a gente fez duas chamadas recursivas em problemas menores só que a recorrência aqui ela tá me dizendo que eu gasto mais tempo do que as duas

chamadas recursivas eu gosto um tempo que é proporcional ao tamanho da entrada que me foi passado Então nesse caso aqui eu ainda das um tempo com ele né além do tempo das duas chamadas recursivas aqui também cada um desses nozinhos aqui vai gastar um tempo proporcional ao tamanho da entrada dele bom então sei que o telefone um problema de tamanho sobre quatro tempo gasto vir em sobre quanto parece um pouco inútil que eu fiz né porque o tamanho da entrada é igual o negócio ficou querendo porque eu não escrevi só uma vez né mas faz

mais sentido quando a gente tem outras recorrências né Nem sempre a Kia vai ser certo então eu tô deixando aqui bem claro que é que tá acontecendo Então tá se eu somar cada Nozinho dessa árvore eu vou ter o tempo de execução do algoritmo dolci concorda então que a gente vai fazer vamos analisar por nível né Cada nível aqui ver o que está acontecendo quanto tempo a gente tá gastando a gente soma todos esses níveis e tenho tempo na da árvore toda ou do algoritmo todo só que eu tava linha aqui com essas informações vai

ajudar a gente alcançar esse objetivo certo então aqui inicialmente tão nível Zé a depois seu nível 1 depois nível 2 3 e assim por diante até o vigésimo nível aí ah e tem esse último nível aqui que a gente ainda não sabe tá a gente discutir bom qual é o tamanho dos problemas do nível zero né que eu tenho problemas de tamanho M o primeiro nível A gente tem problema de tamanho em sobre dois no nível 3 na Nível 2 aliás problemas tamanhos sobre 49 ou três problemas de tamanho e sub-8 e no nível II

qual vai ser o tamanho dos problemas pelo que está acontecendo aqui dá para ver que é do elevado é é dividido por 2 Levanta aí certo bom e no final o tamanho dos meus problemas é ruim quantos novos a gente tem punível né no nível zero tem um nó depois a gente tem dois depois de quatro depois oito ó aqui aparentemente né claramente a dois levar daí então aqui no último nível vai ter que ter dois elevado ao valor da muito livro e qual é o tempo que a gente gasta por nós né então no

primeiro nível o tempo gasto por não é n o segundo nível é n sobre dois depois ele sobre quatro ele sobre oito então também sobre 2 elevado aí e tem como uma como baixo certo então para descobrir quantos níveis tem a minha árvore uma das formas é olha se eu sei que o tamanho de todo o problema é do tipo em sobre 2 elevado aí bom então esse um aqui também vai poder ser escrito da forma em sobre 2 elevado a último nível não qual o valor de ir que eu preciso ter para que me

sobre dois elevadores seja igual a um bom ei sobre 2 elevado a n = 1 se 2 elevado a n = n ou seja e É logo em DN na voz de dois certo então aqui o último nível é blog e na base dois aqui vai ser dois elevado a log de e na base dois ou seja aqui a n mesmo né O que você ele eu poderia ter respondido é esse valor um pouquinho mais rápido se eu tivesse percebido o seguinte olha no nível zero é a gente tem problema de tamanho n no nível

no círculo próximo nível a gente dividiu no próximo dividiu de novo Até que a gente chegou em um e quantas vezes eu preciso dividir o erro dois pra chegar em mim logo e génova dois então agora que a gente sabe que a gente tem log.de na base dois níveis cada nível tem dois levado aí nós e eu gasto esse tempo pornô então a gente pode fazer uma soma aqui né e o tempo total da árvore e vai ser uma sogra para todos os níveis também sabe que tem nível de 0 até o óleo de e

na base 2 e eu vou calcular o tempo que eu gosto por nível e o tempo eu gasto por mim não vai ser o tempo eu gasto por problema que eu tenho né por nós que eu tenho ali naquele nível multiplicado pela quantidade de nós e aqui essa continha ficou um pouco simples né porque esses dois valores que ver se cancelar Então na verdade gente tá somando n na gente passou na do n para ir variando de log de 0 né até logo e na base dois log na base 2 e isso dá exatamente n

vezes a quantidade de vezes que eu tô somando né que é logo que ele na base dois mais um certo ou seja n log n na base 2 + n Oi e esse negócio aqui né na verdade essa expressão aqui né essa expressão é uma reta DN o ML tá isso aqui atleta de n log n agora é um detalhe aqui né Essa análise funciona bem se eu estiver assumindo que o n é uma potência de 2 que deu para dividir ele por dois no começo e depois deu para dividir ele por dois de novo

deu tudo certo e foi bem distribuído tá então aqui na verdade assim a gente estava literalmente provando que isso que essa recorrência é exatamente isso quando ele é uma potência de 2 mas não é muito difícil a gente mostrar que mesmo quando não for potência de 2 vai fazer também essa análise Porque se o meu número não é potência de 2 Ele está entre duas potências de 2 desse jeito Tem um ele aqui não é potência de dois eles só pode estar entre duas potências de nós é bom para esse valor eu sei que vale

o que a gente que eu vou demonstrar para ver se elevará teto e para esse também então né Dá para mostrar que mesmo se não for potência de 2 vai ser na reta de n log n mesmo assim como nós vamos fazer mais um exemplo tá então essa reconhece aqui de novo me que ela disse para gente que o tempo gasto na entrada de tamanho ele é o tempo gasto em duas chamadas feitas em problemas de tamanho sobre três e tem um tempo Extra além dos que a ligação né são chamados que nesse caso aqui

é um tempo constante que a gente tem lá nosso problema de tamanho n é ele vai fazer duas chamadas em problemas de tamanho ele sobre três certo o que vão por sua vez fazer chamadas para problemas de tamanho n sobre 9 e aí sobre o nome vão fazer duas chamadas para problemas de tamanho de sobre 27 e isso não vai para sempre da mesma forma eventualmente ele vai ter que chegar em um certo aí de novo né porque a gente tá assumindo que o Enem é uma potência de três Então vai dar certo para vocês

dividido por três só que acaba acaba a gente conseguindo mostrar que isso vale mesmo se não for potência de três Tá e aí quanto tempo é gasto em cada chamada em cada nova Qual é o rótulo de cada um desses nós é o tempo que me ha dado na própria recorrência né então cada Nozinho desse aqui leva tempo constante para ser perfeito né então agora sim eu não escrevi dois números à toa então velho é legal deixar esse lembrete aqui de lado tá então esse é o tamanho do problema que eu tô ligando uma coisa

o tamanho do problema que vem hoje eu vou te dado aqui e a outra coisa é o tempo que a gente gasta nessa em cima desse problema desse tamanho de novo a gente triste a mesma tabela né gente tem nível 0 1 2 3 tem um asimismo nem e tem o último nível Qual é o último nível a gente boa melhor responder a sua olhando o tamanho do problema então a gente começa com problema de tamanho ele vai reduzindo né Por um terço disso a gente tem isso nove no sobre 27n sobre três elevado a

Ina qualquer nível tem esse tamanho ali e último nível tem tamanho um tão partindo do n dividindo sempre o problema em três por três né sempre o tamanho do problema por três quantos quantas vezes a gente tem que fazer isso para chegar em um ou quando que essa trás quando que isso aqui fica igual uma quando n e quando o nível né log.de na fase 3 certo e quantos nós a gente tem por nível aqui continua Aparecido né 12482 e levava aí o tempo gasto por nós um certo independente do nível que a gente tá

igual aqui eu esqueci então na última a última no último nível A gente vai ter dois elevado a log de e na base três Nossa aqui não não não sei qual é o valor disso né mas uma simplificação que dá para fazer que a inveja escrever dessa forma eu posso trocar aqui né o dois com ele invés de Fica dois elevado alguma coisa fica em relevo atual log de 2 e é isso aqui fica bem mais claro que é é é uma é um polinômio né é elevado a um número em que número é esse

não vem não sei quantos quilômetros de dois a mais três mas certamente o menor do que um tá porque log de 2 na base 3 em menor km de 393 então eu sei que esse número aqui é o número menor do que um Então essas coisas né Para calcular o tempo a gente precisa somar então para todos os níveis a gente tem um nível de 0 Até logo higiene da base três morna quantos problemas a gente tem for nível a gente viu que tem dois levado aí nossa né o do elevador aí problemas por nível

cada um deles gastando o tempo um certo então é isso que a gasto que for por nível e Então qual que é o somatório de uma constante né turma somando basicamente noivado ir tomar vários uma constante maior do que una elevada aí vai ser sempre é essa constante elevado ao máximo do somatório mais um menos 1 sobre 2 menos 1 sobre a própria constante na zona E é isso que dá um né então só sobrou que a gente realmente se essa parte aqui de cima então 2 elevado a longe de n na base três mais

um a mesma coisa que isso multiplicando por 2 - um de nós continuar a ler ó e aqui de novo apareceu aquela coisa estranha né o Lenny lá no blog que tá lá no expoente isso a gente faz essa troca aqui e se virar em elevado a log de 2 na base 3 que multiplica dois anos o colocar dois aqui na frente fica mais bonito menos ou bom então quanto que é vale essa expressão de notação assintótica Oi tá de ele levar meu nome de 2 na base 3 porque eu não sei quanto é esse

valor mas não é um rolé menor do que um Ele é bem errado se você chegar aqui e falar que está teu dinheiro tá isso estaria muito muito errado agora eu não está errado se você fizer que pode ele porque é verdade né a gente eu acabei de falar isso que esse negócio aqui logo de dois abastecer é menor do que um Então essa expressão seria menor do que 2 elevado a n e nos olhos E aí isso como agora eu tô dando um limitante superior Eu só consigo usar outra são lá então isso aqui

seria Rosa onde é certo mas para que se eu posso dar peta né eu posso dar uma votação apertada É isso aí é levado ao longo de 2 na base 3 como último exemplo eu quero dar é se esse daqui que a gente já viu já resolveu usando o método da bom resolveu Aparecida usando o método da internação aqui a gente tem que o tempo gasto nenhum atraso também é no máximo o tempo gasto de uma chamada o tamanho menos ou bom aqui que é chamado né mas tempo um dá para fazer uma árvore de

reconhecer isso aqui também a gente tem problema de tamanho n ele vai ter um único filho porque ele só fez uma chamada recursiva e tamanho menos um vai ter um único filho de tamanho - 2 e assim por diante Até que a gente chega em um problema de tamanho um certo bom e cada um desses caneta gostando tempo né porque o valor que tá ali dado na própria recorrência para gente quantos níveis a gente tem aqui ele níveis cada um gastamos 51 então é que fica bem fácil de resolver né então é parece até que

a gente tá complicado demais então a gente tem nível 012 aqui totalmente a gente vai ter um nível é menos um a cada quantos problemas a gente tem né número de nós o número de problemas e o tempo gasto por problema o pornô um também então qual que é o tempo que eu tava somatório para os níveis variando de 0 até menos um um problema porque multiplique o tempo da Cilene que é um certo e talvez isso aqui ficasse um pouquinho Ou melhor se a gente tivesse trocado essa essa recorrência aqui para uma para essa

daqui tá então aqui eu já o nosso o tempo que a gente gasta pornô é proporcional ao tamanho né do problema então o tempo aqui muda me vira alguém a quem menos um ok menos dois no nível e qualquer a gente vai ter um nosso Ah mas o tempo vai ser em menos ir certo para que ele não é e até que a gente vai ter tempo como é que tá aqui é um Sanatório dinheiro e menos ir aí já ficou um pouquinho mais legal pensei que a gente pode quebrar em dois né somatório só

do n que independe do ir meu celular torna Due esse primeiro da n ao quadrado direto né que eu tô somando RN vezes e aí esse segundo fica ele precisando menos 1 sobre 2 igual mas esse é um exemplo tudo bem bobinho realmente só para gente ver que não dá para fazer Mas provavelmente vai estudo da interação sairia bem mais rápido do que fica fazendo as análises e toda aqui ó