SLIDES AULA 2 ANÁLISE DE ALGORITMOS

Prévia do material em texto

EDA – Estrutura de Dados e Algoritmos 
Análise de Algoritmos 
Cleyton Caetano de Souza 
IFPB – Campus Monteiro 
Motivação 
• Existem múltiplas soluções para o mesmo 
problema 
• Como decidir qual é a melhor? 
– Análise de Algoritmos 
Qual dos dois algoritmos é o melhor? 
Algoritmo 1 Algoritmo 2 
Qual dos dois algoritmos é o melhor? 
Algoritmo 1 Algoritmo 2 
Análise de Algoritmos 
• Que fatores devem ser considerados para 
escolher qual algoritmo é o melhor? 
– Número de Linhas (✖) 
– Número de Testes (✖) 
– Número de Laços (✖) 
– Número de Variáveis (✖) 
– Tempo de Execução (✔) 
Tempo de Execução 
• Um algoritmo pode levar tempos diferentes 
para resolver determinado problema em 
diferentes execuções 
 
Tempo de Execução 
• Depende de 
– Características da Máquina 
– Tamanho de Entrada 
 
Análise Assintótica 
• É um método matemático de análise para 
descrever quantitativamente o 
comportamento de um algoritmo. 
Análise de Algoritmos 
• Funções matemáticas passam a representar o 
tempo de execução dos algoritmos! 
 
Principais Classes dos Algoritmos 
• Constance – c 
• Logarítmica – log n 
• Linear – n 
• Polinomiais – n2, n3... 
• Exponencial – 2n 
Tempo de Execução (1/s) 
Tempo de Execução (1000/s) 
Comparação 
• Como não faz sentido analisar um algoritmo 
para apenas um determinado conjunto de 
entradas e é impossível fazer esta análise para 
todas as entradas possíveis, normalmente, 
considera-se apenas dois cenários 
– Melhor caso 
• Entrada tendendo a zero (entrada pequena) 
– Pior caso 
• Entrada tendendo ao infinito (entrada grande) 
Classes de Algoritmos (Gráficos) 
Ordem de Crescimento 
1 < log 𝑛 < 𝑛 < 𝑛 log 𝑛 < 𝑛2 < 𝑛3 < 2𝑛 
Exercício 
• Ordene as funções por ordem de crescimento 
– 𝑛5 + 132𝑛2 
– 3𝑛 + 12 
– 8900 
– 400 log 𝑛 
– 45𝑛 log 𝑛 
– 132𝑛2 
– 3𝑛 
– log 45𝑛 
 
Relacionando Funções pelo seu 
Crescimento 
f 𝑛 h 𝑛 g 𝑛 
Relacionando Funções pelo seu 
Crescimento: Notações Assintóticas 
Θ f 𝑛 O f 𝑛 Ω f 𝑛 
Notação Assintótica: Notação Θ 
• Notação teta 
• Uma função f 𝑛 é Θ g 𝑛 , i.e. f 𝑛 =
Θ g 𝑛 , se existem três constantes positivas 
𝑐1, 𝑐2 e 𝑚 tais que 
0 ≤ c1 ∗ g 𝑛 ≤ f 𝑛 ≤ 𝑐2 ∗ g 𝑛 , para todo 𝑛 ≥ 𝑚 
• Diz-se que g 𝑛 é o limite assintoticamente 
restrito para f 𝑛 
f 𝑛 = Θ g 𝑛 
Exercícios 
• Qual o Θ das funções abaixo? 
– 5𝑛2 + 8 
– 8 
– 2𝑛6 + 5𝑛
15
2 + 8 
– 8𝑛 log 𝑛 + 5𝑛 
– 10000𝑛 
– 2𝑛+1 
 
Exercícios 
• Indique 5 funções que pertencem a Θ 𝑛3 
Exercícios 
• Justifique 
– 5𝑛2 + 8𝑛 ∈ Θ 𝑛 ? 
– 6𝑛3 + 2𝑛2 + 1 ∈ Θ 𝑛3 ? 
– 7 log 𝑛 ∈ Θ 𝑛 ? 
– 2𝑛 ∈ Θ 3𝑛 ? 
Notação Assintótica: Notação O 
• Notação Big O 
• Uma função f 𝑛 é 𝑂 g 𝑛 , i.e. f 𝑛 =
𝑂 g 𝑛 , se existem duas constantes positivas 
𝑐 e 𝑚 tais que 
f 𝑛 ≤ 𝑐 ∗ g 𝑛 para todo 𝑛 ≥ 𝑚 
• Diz-se que g 𝑛 é o limite superior de f 𝑛 
𝑓 𝑛 = 𝑂 𝑔 𝑛 
Exercícios 
• Qual o 𝑂 das funções abaixo? 
– 999 
– 5𝑛2 + 999 
– 7𝑛2 + 5𝑛2 + 999 
– 100𝑛 + 1 
– 7𝑛 log 𝑛 + 999𝑛 
Exercícios 
• Indique 5 funções que pertencem a 𝑂 log 𝑛 
 
Exercícios 
• Justifique 
– A) log 𝑛 ∈ 𝑂 𝑛 e log 𝑛 ∈ Θ 𝑛 
– B) n2 ∈ 𝑂 2𝑛 e n2 ∈ Θ 2𝑛 
– C) 
𝑛
100
∈ 𝑂 1 e 
𝑛
100
∈ Θ 1 
– D) 
𝑛
100
∈ 𝑂 log 𝑛 e 
𝑛
100
∈ Θ log 𝑛 
– E) 3𝑛 + 1 ∈ 𝑂 5𝑛 + 10 e 3𝑛 + 1 ∈ Θ 5𝑛 + 10 
 
Notação Assintótica: Notação Ω 
• Notação Ômega 
• Uma função f 𝑛 é Ω g 𝑛 , i.e. f 𝑛 =
Ω g 𝑛 , se existem duas constantes positivas 
𝑐 e 𝑚 tais que 
f 𝑛 ≥ 𝑐 ∗ g 𝑛 , para todo 𝑛 ≥ 𝑚 
• Diz-se que g 𝑛 é o limite inferior de f 𝑛 
 
 
f 𝑛 = Ω g 𝑛 
Exercícios 
• Qual o Ω das funções abaixo? 
– 8 
– 5𝑛2 + 8 
– 2𝑛6 + 𝑛
15
2 + 8 
– 8𝑛 log 𝑛 + 5𝑛 
– 10000𝑛 
Exercícios 
• Indique 5 funções que pertencem a Ω 𝑛3 
Exercícios 
• Justifique 
– A) log 𝑛 ∈ 𝑂 𝑛 , log 𝑛 ∈ Θ 𝑛 e log 𝑛 ∈ Ω 𝑛 
– B) 𝑛2 ∈ 𝑂 𝑛2 , 𝑛2 ∈ Θ 𝑛2 e 𝑛2 ∈ Ω 𝑛2 
– C) 
𝑛
103
∈ 𝑂 𝑛 + 1 , 
𝑛
103
∈ Θ 𝑛 + 1 e 
𝑛
103
∈
Ω 𝑛 + 1 
– D) 
𝑛
2
2
∈ 𝑂 log 𝑛 ,
𝑛
2
2
∈ Θ log 𝑛 e
𝑛
2
2
∈
Ω log 𝑛 
 
 
Notação Assintótica: Notação o 
• Notação o minúsculo 
• Uma função f 𝑛 é 𝑜 g 𝑛 , i.e. f 𝑛 =
𝑜 g 𝑛 , se para qualquer constate 𝑐 > 0 
temos 
0 ≤ f 𝑛 < 𝑐 ∗ g 𝑛 para todo 𝑛 ≥ 𝑚 
• g 𝑛 é um limite superior que não é 
assintoticamente restrito para f 𝑛 
Exercícios 
• Qual o 𝑜 das funções abaixo? 
– 999 
– 5𝑛2 + 999 
– 7𝑛2 + 5𝑛2 + 999 
– 100𝑛 + 1 
– 7𝑛 log 𝑛 + 999𝑛 
 
Notação Assintótica: Notação ω 
• Notação ômega minúsculo 
• Uma função f 𝑛 é ω g 𝑛 , i.e. f 𝑛 =
ω g 𝑛 , se para qualquer constate 𝑐 > 0 
temos 
0 ≤ 𝑐 ∗ g 𝑛 < f 𝑛 para todo 𝑛 ≥ 𝑚 
• g 𝑛 é um limite inferior que não é 
assintoticamente restrito para f 𝑛 
Exercícios 
• Qual o 𝜔 das funções abaixo? 
– 5𝑛2 + 999 
– 7𝑛2 + 5𝑛2 + 999 
– 100𝑛 + 1 
– 7𝑛 log 𝑛 + 999𝑛 
– 999 
 
Convenções 
• Princípio da Justeza 
– Deve-se utilizar as notações para estabelecer 
relações com a maior precisão possível 
– Evitar usar 𝑛2 = 𝑂 𝑛3 , pois, o mais preciso é 
𝑛2 = 𝑂 𝑛2 
• Princípio de Simplicidade 
– Também deve-se manter as funções o mais 
simples possível! 
– Evitar usar 𝑛 + 1 = 𝑂 𝑛 + 1 , pois o mais simples 
é 𝑛 + 1 = 𝑂 𝑛 
Relação entre as notações 
 
 
 
Θ f 𝑛 = Ω f 𝑛 ∩ O f 𝑛 
∅ = o f 𝑛 ∩ 𝜔 f 𝑛 
Propriedades das Comparações 
Assintóticas 
• Muitas das propriedades relacionais de números 
reais também se aplicam a comparações 
assintóticas 
– Transitividade 
– Reflexividade 
– Simetria 
– Simetria de Transposição 
• Essas propriedades só se verificam se as funções 
f 𝑛 e g 𝑛 , que estamos comparando, forem 
assintoticamente positivas. 
Propriedades das Comparações 
Assintóticas 
• Transitividade (válido também para 𝑂, Ω, 𝑜 e 
ω) 
– f 𝑛 = Θ g 𝑛 e g 𝑛 = Θ h 𝑛 implicam 
f 𝑛 = Θ h 𝑛 
Propriedades das Comparações 
Assintóticas 
• Reflexividade (válido também para 𝑂, Ω) 
– f 𝑛 = Θ f 𝑛 
Propriedades das Comparações 
Assintóticas 
• Simetria 
– f 𝑛 = Θ g 𝑛 se e somente se g 𝑛 = Θ f 𝑛 
Propriedades das Comparações 
Assintóticas 
• Simetria da Transposição 
– f 𝑛 = 𝑂 g 𝑛 se e somente se g 𝑛 = Ω f 𝑛 
– f 𝑛 = 𝑜 g 𝑛 se e somente se g 𝑛 = ω f 𝑛 
Analogia (Notações e Números Reais) 
Regras de Simplificação (Soma) 
• Se f1 𝑛 = O g1 𝑛 e f2 𝑛 = O g2 𝑛 
então f1 𝑛 + f2 𝑛 = O max g1 𝑛 , g2 𝑛 
– Exemplos 
 
2𝑛2 + 3𝑛 + 1 = 2𝑛2 + Θ 𝑛 = Θ 𝑛2 
 
 
 
 
Regras de Simplificação (Produto) 
• Se f1 𝑛 = O g1 𝑛 e f2 𝑛 = O g2 𝑛 
então f1 𝑛 ∗ f2 𝑛 = O g1 𝑛 ∗ g2 𝑛 
– Exemplos: 
O 𝑛 ∗ O 𝑛 = O 𝑛2 
𝑛 ∗ O 𝑛 = O 𝑛2 
 
 
 
 
 
Revisão Background Matemático 
• Progressão aritmética 
– (𝑎1, 𝑎2, … , 𝑎𝑛) (Ex.: (1, 3, 5, 7, 9, ...) 
– 𝑎𝑛 = 𝑎1 + 𝑛 − 1 ∗ 𝑟 
– 𝑆𝑛 =
𝑛∗ 𝑎1+𝑎𝑛
2
 
Revisão Background Matemático 
• Progressão Geométrica 
– (𝑎1, 𝑎2, … , 𝑎𝑛) (Ex.: (2, 4, 8, 16, 32, ...) 
– 𝑎𝑛 = 𝑎1 ∗ 𝑞
𝑛−1 
– 𝑆𝑛 =
𝑎1∗(𝑞
𝑛−1)
𝑞−1
, se a PG for finita e crescente 
( 𝑞 > 1) 
– 𝑆𝑛 =
𝑎1
1−𝑞
, se a PG for infinita decrescente 
( 𝑞 < 1) 
 
Revisão Background Matemático 
• Propriedade dos Logaritmos 
– lg 𝑛= log 𝑛 = log2 𝑛 
– 𝑏log𝑏 𝑎 = 𝑎 
– log𝑏 𝑎
𝑛 = 𝑛 ∗ log𝑏 𝑎 
– log𝑎 𝑎 = 1 
– log𝑐 𝑎 ∗ 𝑏 = log𝑐 𝑎 + log𝑐 𝑏 
– 𝑎log𝑏 𝑛 = 𝑛log𝑏 𝑎 
– log𝑎 𝑏 =
log𝑐 𝑏
log𝑐 𝑎
 
– log𝑏 𝑎 ∗ log𝑎 𝑏 = 1 
 
Revisão Background Matemático 
• Propriedade das Exponenciais 
– 𝑎1 = 𝑎 
– 𝑎0 = 1 
– 𝑎−𝑛 =
1
𝑎𝑛
 
– 𝑎𝑛 ∗ 𝑎𝑚 = 𝑎𝑛+𝑚 
– 𝑎 ∗ 𝑏 𝑛 = 𝑎𝑛 ∗ 𝑏𝑛 
– 𝑎𝑛 𝑚 = 𝑎𝑛∗𝑚 
– 𝑎𝑛
𝑚
=
𝑎𝑛
𝑎𝑚
 
Recursividade 
• Em ciência da computação, a recursividade é a 
definição de uma sub-rotina (função ou 
método) que pode invocar a si mesma. 
• Um algoritmo é chamado de recursivo se ele 
resolve um problema reduzindo-o a uma 
instância mais simples do mesmo problema 
 
Recursividade 
Recursividade 
• Que outros problemas poderiam ser 
resolvidos com recursividade? 
Recursividade 
• Fatorial 
• Torres de Hanói 
• Ordenação 
• Fibonacci 
• Pesquisa 
• MDC 
Exercício 
• Faça uma função recursiva que calcule e 
retorne o n-ésimo termo da sequência 
Fibonacci. Alguns números desta sequência 
são: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 
• Faça uma função recursiva que permita somar 
os elementos de um vetor de inteiros 
• Escreva uma função recursiva que inverta 
ordem dos elementos presentes em um vetor 
 
 
 
Análise de Algoritmos Recursivos 
• Como estimar o tempo de execução de 
algoritmo recursivo? 
– Método da Substituição 
– Método da Árvore de Recursão 
• Também chamado de Método Iterativo 
– Método Mestre 
• Para utilizar esses métodos... 
Relações de Recorrência 
• Uma relação de recorrência descreve como o 
problema é decomposto pelo algoritmo 
recursivo. 
 
Relações de Recorrência 
• Algoritmo do Fatorial 
T 𝑛 = 
1, se 𝑛 = 0
1 + T 𝑛 − 1 , caso contrário
 
 
Relações de Recorrência 
• Algoritmo do Fatorial (recorrência com mais elegância) 
T 𝑛 = 
Θ 1 , se 𝑛 = 0
Θ 1 + T 𝑛 − 1 , caso contrário
 
 
Relações de Recorrência 
• Como resolver essa recorrência? 
– T 𝑛 = 
1, se 𝑛 = 0
1 + T 𝑛 − 1 , caso contrário
 
• Como representar o custo/tempo de T 𝑛 
apenas em função de 𝑛? 
 
Relações de Recorrência 
• Em geral, existem três formas de resolver 
recorrências 
– Método da Substituição 
– Árvore de Recorrência 
– Método Mestre 
Procedimento: 
Método da Substituição 
• O método de substituição para resolver 
recorrências envolve duas etapas: 
1. Pressupor a forma da solução (chute!) 
2. Provar que a suposição é correta por indução 
Exemplo 
• Calculo do Fatorial 
T 𝑛 = T 𝑛 − 1 + 1 
• Usamos a abordagem (1) expandir, (2) 
conjecturar e (3) verificar. 
 
 
Exemplo - Expandir 
• Calculo do Fatorial 
T 𝑛 = T 𝑛 − 1 + 1 
T 𝑛 = T 𝑛 − 2 + 1 + 1 = T 𝑛 − 2 + 2 
T 𝑛 = T 𝑛 − 3 + 1 + 2 = T 𝑛 − 2 + 3 
⁞ 
 
 
 
Exemplo - Conjecturar 
• Calculo do Fatorial 
T 𝑛 = T 𝑛 − 1 + 1 
T 𝑛 = T 𝑛 − 2 + 1 + 1 = T 𝑛 − 2 + 2 
T 𝑛 = T 𝑛 − 3 + 1 + 2 = T 𝑛 − 2 + 3 
⁞ 
• Para onde estamos indo? 
 
Exemplo - Conjecturar 
• Calculo do Fatorial 
T 𝑛 = T 𝑛 − 1 + 1 
T 𝑛 = T 𝑛 − 2 + 1 + 1 = T 𝑛 − 2 + 2 
T 𝑛 = T 𝑛 − 3 + 1 + 2 = T 𝑛 − 2 + 3 
⁞ 
• Para onde estamos indo? 
T 𝑛 = T 𝑛 − 𝑘 + 𝑘 
• Quando essa expansão termina? 
 
Exemplo - Conjecturar 
• Calculo do Fatorial 
T 𝑛 = T 𝑛 − 1 + 1 
T 𝑛 = T 𝑛 − 2 + 1 + 1 = T 𝑛 − 2 + 2 
T 𝑛 = T 𝑛 − 3 + 1 + 2 = T 𝑛 − 2 + 3 
⁞ 
• Para onde estamos indo? 
T 𝑛 = T 𝑛 − 𝑘 + 𝑘 
• Quando essa expansão termina? 
𝑛 = 𝑘 
• O que isso significa? Quanto é T 𝑛 ? 
 
Exemplo - Conjecturar 
• Calculo do Fatorial 
T 𝑛 = T 𝑛 − 1 + 1 
• Para onde estamos indo? 
T 𝑛 = T 𝑛 − 𝑘 + 𝑘 
• Quando essa expansão termina? 
𝑛 = 𝑘 
T 𝑛 = T 𝑛 − 𝑛 + 𝑘 = T 0 + 𝑘 = 1 + 𝑘 
• O que isso significa? Quanto é T 𝑛 ? 
T 𝑛 = 𝑛 + 1 = Θ 𝑛 
 
 
Exemplo - Verificar 
• Como verificar se a nossa solução é a correta? 
– Caso base, mais simples 𝑛 = 0 
T 𝑛 = 𝑛 + 1 (essa é nossa suposição) 
T 0 = 0 + 1 = 1 (de acordo com a nossa 
suposição) 
– Se olharmos na Recorrência Original notaremos 
que está correto! 
T 𝑛 = 
1, se 𝑛 = 0
1 + T 𝑛 − 1 , caso contrário
 
 
Exemplo - Verificar 
• Como verificar se a nossa solução é a correta? 
– Passo Indutivo, caso genérico 𝑛 = 𝑘 
T 𝑘 = T 𝑘 − 1 + 1 
T 𝑘 = T 𝑘 − 2 + 1 + 1 = T 𝑘 − 2 + 2 
T 𝑘 = T 𝑘 − 3 + 1 + 2 = T 𝑘 − 2 + 3 
⁞ 
T 𝑘 = T 𝑘 − 𝑘 + 𝑘 = T 0 + 𝑘 = 1 + 𝑘 = 𝑘 + 1 
 
 
 
 
 
Método da Substituição 
• Como fazer um bom “chute”? 
– INFELIZMENTE, não há nenhum modo geral de 
adivinhar a solução correta para uma recorrência. 
– PRESSUPOR (1ª fase) exige experiência e, 
ocasionalmente, criatividade. 
• Se a recorrência for semelhante a uma que você já 
tenha visto antes, então é razoável supor uma solução 
semelhante. 
Método da Substituição 
• É um método eficiente, porém, só pode ser 
usado quando é fácil PRESSUPOR a solução da 
recorrência 
• As vezes é difícil apresentar uma boa 
suposição. 
Exercícios 
• Demonstre se 
– T 𝑛 = T 𝑛 − 1 + 𝑛 é O 𝑛2 
– T 𝑛 = T 𝑛 − 2 + 1 é Θ 𝑛 
– T 𝑛 = T
𝑛
2
+ 1 é O log 𝑛 
Árvore de Recursão 
• Também chamado de Método Iterativo 
• Uma árvore de recursão é uma representação 
gráfica e abstrata para o aumento do custo, de 
acordo com a redução do problema 
• Traçar uma árvore de recursão é um caminho 
direto para se criar uma boa suposição 
• Método ideal para encontrar uma 
aproximação do tempo de execução do 
algoritmo recursivo 
 
Procedimento: 
Método da Árvore de Recursão 
1. Desenhe a Árvore de Recursão, de acordo com a 
relação de recorrência T 𝑛 
a) Cada Nó representa o custo de um único subproblema 
entre as chamadas recursivas. 
2. Soma-se os custos dentro de cada nível da Árvore 
para obter um conjunto de custos por nível 
3. Soma-se os custos de todos os níveis 
a) Para isso, é necessário inferir sobre a Altura da Árvore de 
Recorrência 
b) Geralmente, essa soma resume-se em uma Progressão 
Aritmética ou Geométrica 
Árvore de Recursão 
• Relação de Recorrência para o MergeSort 
T 𝑛 = 
Θ 1 , se 𝑛 = 1
2T
𝑛
2
+ Θ 𝑛 , se 𝑛 > 1
 
• Como resolver utilizando o Método Iterativo 
(Árvore de Recursão)? 
 
 
Passo 1 
• Desenhe a Árvore de Recursão, de acordo com 
a relação de recorrência T 𝑛 
– A Árvore de Recursão representa visualmente a 
redução do problema em problemas menores 
Árvore de Recursão 
T 𝑛 
T
𝑛
2
 𝑇
𝑛
2
 
Árvore de Recursão 
𝑐𝑛 
T
𝑛
2
 𝑇
𝑛
2
 
Árvore de Recursão 
𝑐𝑛 
𝑐𝑛
2
 
T
𝑛
4
 T
𝑛
4
 
𝑐𝑛
2
 
T
𝑛
4
 T
𝑛
4
 
Árvore de Recursão 
𝑐𝑛 
𝑐𝑛
2
 
𝑐𝑛
4
 
T
𝑛
8
 T
𝑛
8
 
𝑐𝑛
4
 
T
𝑛
8
 T
𝑛
8
 
𝑐𝑛
2
 
𝑐𝑛
4
 
T
𝑛
8
 T
𝑛
8
 
𝑐𝑛
4
 
T
𝑛
8
 T
𝑛
8
 
⁞ 
Até onde essa árvore vai continuar crescendo? 
Árvore de Recursão 
𝑐𝑛
20
 
𝑐𝑛
21
 
𝑐𝑛
22
 
T
𝑛
23
 T
𝑛
23
 
𝑐𝑛
22
 
T
𝑛
23
 T
𝑛
23
 
𝑐𝑛
21
 
𝑐𝑛
22
 
T
𝑛
23
 T
𝑛
23
 
𝑐𝑛
22
 
T
𝑛
23
 T
𝑛
23
 
⁞ 
Até onde essa árvore vai continuar crescendo? 
Resposta: 
𝑛
2ℎ
 
Árvore de Recursão 
Passo 2 
• Soma-se os custos dentro de cada nível da 
Árvore para obter um conjunto de custos por 
nível 
Árvore de Recursão 
Passo 3 
• Soma-se os custos de todos os níveisÁrvore de Recursão 
Como encontrar o valor de ℎ? 
Árvore de Recursão 
• Como encontrar o valor da altura? 
–
𝑛
2ℎ
 é o caso mais simples 
𝑛
2ℎ
= 1 
 
Árvore de Recursão 
𝑛
2ℎ
= 1 
2ℎ = 𝑛 
log 2ℎ = log 𝑛 
ℎ ∗ log 2 = log 𝑛 
ℎ ∗ 1 = log 𝑛 
ℎ = log 𝑛 
Árvore de Recursão 
• Resolvendo a recorrência 
T 𝑛 = ℎ + 1 ∗ 𝑐𝑛|ℎ = log 𝑛 
T 𝑛 = log 𝑛 + 1 ∗ 𝑐𝑛 
T 𝑛 = 𝑐𝑛 ∗ log 𝑛 + 𝑐𝑛 
T 𝑛 = 𝑐 ∗ 𝑛 log 𝑛 + 𝑛 
 
Árvore de Recursão 
• Resolvendo a recorrência 
T 𝑛 = ℎ + 1 ∗ 𝑐𝑛|ℎ = log 𝑛 
T 𝑛 = log 𝑛 + 1 ∗ 𝑐𝑛 
T 𝑛 = 𝑐𝑛 ∗ log 𝑛 + 𝑐𝑛 
T 𝑛 = 𝑐 ∗ 𝑛 log 𝑛 + 𝑛 
T 𝑛 = Θ 𝑛 log 𝑛 
 
 
Exercício 
• Resolva as recorrências utilizando o método 
iterativo 
– T 𝑛 = 4T
𝑛
2
+ 𝑛 
– T 𝑛 = T
𝑛
2
+ 𝑛2 
– Desafio: T 𝑛 = 3T
𝑛
2
+ 𝑛 
 
Método Mestre 
• O método mestre fornece uma “receita de 
bolo” para resolver recorrências da forma 
T 𝑛 = 𝑎T
n
b
+ f 𝑛 
• onde 𝑎 ≥ 1 e 𝑏 ≥ 1 são constantes e f 𝑛 é 
uma função assintótica positiva 
 
Método Mestre 
• A solução é encontrada ao associar a recorrência 
com um dos três casos bases 
T 𝑛 = 𝑎T
𝑛
𝑏
+ f 𝑛 
• Caso 1: f 𝑛 < 𝑛log𝑏 𝑎 → T 𝑛 = Θ 𝑛log𝑏 𝑎 
• Caso 2: f 𝑛 = 𝑛log𝑏 𝑎 → T 𝑛 = Θ f 𝑛 log 𝑛 
• Caso 3: f 𝑛 > 𝑛log𝑏 𝑎 → T 𝑛 = Θ f 𝑛 
 
Procedimento: 
Método Mestre 
1. Identifique 𝑎, 𝑏, f 𝑛 e log𝑏 𝑎 
2. Verifique se as condições para 𝑎, 𝑏 e f 𝑛 são 
satisfeitas 
3. Compare f 𝑛 com 𝑛log𝑏 𝑎 para associar ao 
caso correto 
4. Confirme a qual caso a comparação se refere 
5. Encontre o Θ 
Exercício 
• Encontre a solução das recorrências abaixo 
utilizando o método mestre 
– T 𝑛 = 9T
𝑛
3
+ 𝑛 
– T 𝑛 = 2T
𝑛
2
+ 𝑛 log 𝑛 
– T 𝑛 = 3T
𝑛
2
+ 𝑛 
Exercício 
• É possível utilizar o método mestre com as 
recorrências a seguir? 
– T 𝑛 = 2𝑛T
𝑛
2
+ 𝑛𝑛 
– T 𝑛 =
1
2
T
𝑛
2
+
1
𝑛
 
– T 𝑛 = 64T
𝑛
8
− 𝑛2 log 𝑛 
– T 𝑛 = T
2𝑛
3
+ 1 
 
Próximas Aulas 
• Algoritmos de Busca 
• Algoritmos de Ordenação