Método Mestre §

---

O Método Mestre é uma técnica usada para estimar a complexidade assintótica de algoritmos recursivos que seguem o paradigma de divisão e conquista. Em geral, algoritmos que dividem o problema em subproblemas menores de tamanho fracionado e resolvem esses subproblemas recursivamente podem ser analisados usando essa técnica.

Definição Geral §

Dada uma relação de recorrência no formato:

Onde:

• indica o número de subproblemas gerados em cada passo da recursão;
• representa o fator de redução do tamanho do problema em cada passo;
• é o custo não recursivo (por exemplo, o tempo gasto em dividir o problema ou combinar soluções).

A função é geralmente descrita como:

O Método Mestre classifica o comportamento da função com base na comparação entre o termo recursivo e o fator , onde e são expoentes característicos do termo .

Casos do Método Mestre §

Existem três cenários principais:

1. Quando O termo recursivo domina o custo total. Neste caso, a solução é dada por:

2. Quando Ambos os termos (recursivo e o custo não recursivo) têm contribuição semelhante para o custo total. A solução é:

3. Quando O custo não recursivo domina o custo total, e a solução é:

Exemplo: Merge Sort §

Uma aplicação clássica do método mestre. A relação de recorrência para o Merge Sort é:

Aqui, , , e , então e . Isso se encaixa no caso 2 do Método Mestre, e a complexidade é:

Referências §

---

Aula de Projeto e Análise de Algoritmo II do dia 04/09/2024.

Flashcards §

---

O que é o Método Mestre?
~~
O Método Mestre é uma técnica para determinar a complexidade assintótica de algoritmos recursivos que seguem o paradigma de divisão e conquista, a partir de uma relação de recorrência.

Qual é a forma geral da relação de recorrência no Método Mestre?
~~
A relação de recorrência geral é:

Onde (a) é o número de subproblemas, (b) é o fator de divisão do problema, e (f(n)) é o custo fora da recursão.

Quais são as condições para aplicar o Método Mestre?
~~
As condições são:

• (a \geq 1)

• (b > 1)

• (f(n) = O(n^k \log^p{n}))

Quando a relação (a > b^k), qual é a complexidade da função?
~~
Quando (a > b^k), o termo recursivo domina, e a complexidade é:

O que acontece no caso (a = b^k)?
~~
Quando (a = b^k), os termos recursivo e não recursivo contribuem igualmente, e a complexidade é:

No Método Mestre, o que ocorre quando (a < b^k)?
~~ Quando (a < b^k), o custo não recursivo domina, e a complexidade é: