Neste tutorial, você aprenderá o que é o teorema mestre e como ele é usado para resolver relações de recorrência.
O método mestre é uma fórmula para resolver relações de recorrência da forma:
T (n) = aT (n / b) + f (n), onde, n = tamanho da entrada a = número de subproblemas na recursão n / b = tamanho de cada subproblema. Todos os subproblemas são considerados como tendo o mesmo tamanho. f (n) = custo do trabalho realizado fora da chamada recursiva, que inclui o custo de dividir o problema e o custo de mesclar as soluções. Aqui, a ≧ 1 e b> 1 são constantes e f (n) é um positivo assintoticamente função.
Uma função assintoticamente positiva significa que para um valor suficientemente grande de n, temos f(n)> 0.
O teorema mestre é usado no cálculo da complexidade do tempo das relações de recorrência (algoritmos de divisão e conquista) de forma simples e rápida.
Teorema Mestre
Se a ≧ 1e b> 1são constantes e f(n)são uma função assintoticamente positiva, então a complexidade de tempo de uma relação recursiva é dada por
T (n) = aT (n / b) + f (n) onde, T (n) tem os seguintes limites assintóticos: 1. Se f (n) = O (n log b a-ϵ ), então T (n ) = Θ (n log b a ). 2. Se f (n) = Θ (n log b a ), então T (n) = Θ (n log b a * log n). 3. Se f (n) = Ω (n log b a + ϵ ), então T (n) = Θ (f (n)). ϵ> 0 é uma constante.
Cada uma das condições acima pode ser interpretada como:
- Se o custo de resolver os subproblemas em cada nível aumentar em um determinado fator, o valor de
f(n)se tornará polinomialmente menor que . Assim, a complexidade do tempo é oprimida pelo custo do último nível, ou seja.nlogb anlogb a - Se o custo de resolver o subproblema em cada nível for quase igual, o valor de
f(n)será . Assim, a complexidade do tempo será vezes o número total de níveis, ou seja.nlogb af(n)nlogb a * log n - Se o custo de resolver os subproblemas em cada nível diminui por um determinado fator, o valor de
f(n)se tornará polinomialmente maior do que . Assim, a complexidade do tempo é oprimida pelo custo de .nlogb af(n)
Exemplo Resolvido do Teorema Mestre
T (n) = 3T (n / 2) + n2 Aqui, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 ie. f (n) <n log b a + ϵ , onde, ϵ é uma constante. O caso 3 implica aqui. Assim, T (n) = f (n) = Θ (n 2 )
Limitações do Teorema Mestre
O teorema mestre não pode ser usado se:
- T (n) não é monótono. por exemplo.
T(n) = sin n f(n)não é um polinômio. por exemplo.f(n) = 2n- a não é uma constante. por exemplo.
a = 2n a < 1
