Teorema Mestre-Guia Completo para Resolução de Recorrências

Teorema Master Prof Felipe Zeiser Teorema Mestre Teorema Mestre Fornece um livro de receitas para resolver algumas equações de recorrência Resolve recorrências no formato 𝑇 𝑛 𝑎𝑇 𝑛 𝑏 𝑓𝑛 onde 𝑎 1 e 𝑏 1 são constantes e 𝑓𝑛 é uma função assintoticamente positiva podem ser resolvidas usando o Teorema Mestre Generalizando 𝑇 𝑛 𝑎𝑇 𝑛 𝑏 𝑓𝑛 O 𝑛 é o tamanho da nossa entrada O 𝑎 é a quantidade de chamadas recursivas O 𝑏 é a quantidade de partes que você está dividindo o seu problema O 𝑓𝑛 é a quantidade de operações a mais realizadas em cada chamada for ifs somas subtrações etc Teorema Mestre 𝑇 𝑛 𝑎𝑇 𝑛 𝑏 𝑓𝑛 Se 𝑓 𝑛 Ο 𝑛𝑙𝑜𝑔𝑏𝑎𝜀 para alguma constante 𝜀 0 então T 𝑛 Θ 𝑛𝑙𝑜𝑔𝑏𝑎 Se 𝑓 𝑛 Θ 𝑛𝑙𝑜𝑔𝑏𝑎 então T 𝑛 Θ 𝑛𝑙𝑜𝑔𝑏𝑎 log 𝑛 Se 𝑓 𝑛 Ω 𝑛𝑙𝑜𝑔𝑏𝑎𝜀 para alguma constante 𝜀 0 E se 𝑎𝑓 𝑛 𝑏 𝑐𝑓𝑛 para alguma constante 𝑐 1 e para todo 𝑛 suficientemente grande então T 𝑛 Θ 𝑓𝑛 Exemplo 1 𝑇 𝑛 𝑎𝑇 𝑛 𝑏 𝑓 𝑛 𝑇 𝑛 9𝑇 𝑛 3 𝑛 𝑎 𝑏 𝑓 𝑛 Em qual caso se encaixa Exemplo 1 𝑇 𝑛 9𝑇 𝑛 3 𝑛 𝑎 9 𝑏 3 𝑓 𝑛 𝑛 Exemplo 1 𝑇 𝑛 9𝑇 𝑛 3 𝑛 𝑎 9 𝑏 3 𝑓 𝑛 𝑛 Primeiro caso 𝑓 𝑛 Ο 𝑛𝑙𝑜𝑔𝑏𝑎𝜀 𝑛 Ο 𝑛𝑙𝑜𝑔93𝜀 𝑛 Ο 𝑛2𝜀 𝑛 𝑐𝑛2𝜀 𝜀 1 𝑛 𝑐𝑛1 VERDADEIRO Exemplo 1 𝑇 𝑛 9𝑇 𝑛 3 𝑛 𝑎 9 𝑏 3 𝑓 𝑛 𝑛 Aplicando o Teorema T 𝑛 Θ 𝑛𝑙𝑜𝑔𝑏𝑎 T 𝑛 Θ 𝑛𝑙𝑜𝑔39 T 𝑛 Θ 𝑛2 Exemplo 2 𝑇 𝑛 𝑎𝑇 𝑛 𝑏 𝑓 𝑛 𝑇 𝑛 2𝑇 𝑛 4 𝑛 𝑎 𝑏 𝑓 𝑛 Exemplo 2 𝑇 𝑛 𝑎𝑇 𝑛 𝑏 𝑓 𝑛 𝑇 𝑛 2𝑇 𝑛 4 𝑛 𝑎 2 𝑏 4 𝑓 𝑛 𝑛 Primeiro caso 𝑓 𝑛 Ο 𝑛𝑙𝑜𝑔𝑏𝑎𝜀 𝑛 Ο 𝑛𝑙𝑜𝑔42𝜀 𝑛 Ο 𝑛05𝜀 𝑛 𝑐𝑛05𝜀 𝜀 01 𝑛 𝑐𝑛04 FALSO Exemplo 2 𝑇 𝑛 𝑎𝑇 𝑛 𝑏 𝑓 𝑛 𝑇 𝑛 2𝑇 𝑛 4 𝑛 𝑎 2 𝑏 4 𝑓 𝑛 𝑛 Segundo caso 𝑓 𝑛 Θ 𝑛𝑙𝑜𝑔𝑏𝑎 𝑛 Θ 𝑛𝑙𝑜𝑔42 𝑛 Θ 𝑛05 𝑛 Θ 𝑛𝑙𝑜𝑔42 𝑛 𝑛05 𝑐1𝑛05 𝑛05 𝑐2𝑛05 𝑐1 𝑐2 1 VERDADEIRO Exemplo 2 𝑇 𝑛 9𝑇 𝑛 3 𝑛 𝑎 9 𝑏 3 𝑓 𝑛 𝑛 Aplicando o Teorema T 𝑛 Θ 𝑛log𝑎 𝑏 log 𝑛 T 𝑛 Θ 𝑛𝑙𝑜𝑔42 log 𝑛 T 𝑛 Θ 𝑛05 log 𝑛 Exemplo 3 𝑇 𝑛 𝑎𝑇 𝑛 𝑏 𝑓 𝑛 𝑇 𝑛 3𝑇 𝑛 4 𝑛 log 𝑛 𝑎 𝑏 𝑓 𝑛 Em qual caso se encaixa Exemplo 3 𝑇 𝑛 3𝑇 𝑛 4 𝑛 log 𝑛 𝑎 3 𝑏 4 𝑓 𝑛 𝑛 log 𝑛 Primeiro caso 𝑓 𝑛 Ο 𝑛𝑙𝑜𝑔43𝜀 𝑛 log 𝑛 Ο 𝑛𝑙𝑜𝑔43𝜀 𝑛 log 𝑛 Ο 𝑛079𝜀 𝑛 log 𝑛 𝑐𝑛079𝜀 𝜀 001 𝑛 log 𝑛 𝑐𝑛078 FALSO Exemplo 3 𝑇 𝑛 3𝑇 𝑛 4 𝑛 log 𝑛 𝑎 3 𝑏 4 𝑓 𝑛 𝑛 log 𝑛 Segundo caso 𝑓 𝑛 Θ 𝑛𝑙𝑜𝑔43 𝑛 log 𝑛 Θ 𝑛𝑙𝑜𝑔43 𝑛 log 𝑛 Θ 𝑛079 𝑐1𝑛079 𝑛 log 𝑛 𝑐2𝑛079 𝜀 001 𝑐1𝑛079 𝑛 log 𝑛 Verdadeiro 𝑛 log 𝑛 𝑐2𝑛079 Falso FALSO Exemplo 3 𝑇 𝑛 3𝑇 𝑛 4 𝑛 log 𝑛 𝑎 3 𝑏 4 𝑓 𝑛 𝑛 log 𝑛 Terceiro caso 𝑓 𝑛 Ω 𝑛𝑙𝑜𝑔𝑏𝑎𝜀 𝑛 log 𝑛 Ω 𝑛𝑙𝑜𝑔43𝜀 𝑛 log 𝑛 Ω 𝑛079𝜀 𝑛 log 𝑛 𝑐𝑛079𝜀 𝜀 021 𝑛 log 𝑛 𝑐𝑛079021 𝑛 log 𝑛 𝑐𝑛1 log 𝑛 𝑐 VERDADEIRO Exemplo 3 𝑇 𝑛 3𝑇 𝑛 4 𝑛 log 𝑛 𝑎 3 𝑏 4 𝑓 𝑛 𝑛 log 𝑛 𝑎𝑓 𝑛 𝑏 𝑐𝑓 𝑛 3𝑓 𝑛 4 𝑐𝑓 𝑛 3𝑛 4 𝑙𝑜𝑔 𝑛 𝑏 𝑐𝑛 log 𝑛 3𝑛 4 log 𝑛 log 4 𝑐𝑛 log 𝑛 3𝑛 4 log 𝑛 2 𝑐𝑛 log 𝑛 c 3 4 3𝑛 4 log 𝑛 2 3𝑛 4 log 𝑛 log 𝑛 2 log 𝑛 VERDADEIRO Exemplo 3 𝑇 𝑛 3𝑇 𝑛 4 𝑛 log 𝑛 𝑎 3 𝑏 4 𝑓 𝑛 𝑛 log 𝑛 Aplicando ao caso T 𝑛 Θ 𝑓𝑛 T 𝑛 Θ 𝑛 log 𝑛 Referências 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