- Utilize os métodos iterativo e mestre para resolver as seguintes equações abaixo:
-
-
-
Passo 1
O enunciado pede para resolver, pelos métodos iterativo e mestre, as recurrences
,
e
.
O conteúdo é análise de algoritmos e vamos precisar de:
. Método iterativo (expansão em árvore de recursão e soma de custos por nível).
. Teorema mestre (identificar
,
,
e comparar
com
).
O conteúdo é análise de algoritmos e vamos precisar de:
Passo 2
Resolver iterativamente
Cada nível da árvore tem
subproblemas de tamanho
.
O custo em cada nó é , logo o custo total no nível
é
Cada nível
O custo em cada nó é
Somando de
até
:
As folhas somam
, então
Passo 3
Aplicar o teorema mestre em
Aqui ,
, logo
. Temos
.
Como para
, é o Caso
do mestre, daí
Aqui
Como
Passo 4
Resolver iterativamente
No nível , cada nó custa
e há
nós, então o custo total do nível é
No nível
Somando de
até
dá
. As folhas são
, de ordem menor. Logo
Passo 5
Aplicar o teorema mestre em
Temos ,
,
e
. É o Caso
do mestre, então
Temos
Passo 6
Resolver iterativamente
No nível , cada nó custa
e há
nós, de modo que o custo do nível é
No nível
Somando
até
resulta em uma série geométrica convergente a
. As folhas valem
, menor ordem. Logo
Passo 7
Aplicar o teorema mestre em
Aqui ,
,
e
com
. Verifica-se a regularidade
. É o Caso
do mestre, logo
Aqui
Resposta
Para cada recorrência temos: