Teorema Mestre: resolver recorrências de divisão e conquista T(n) = aT(n/b) + f(n)
Informe a, b e f(n) = c · nᵈ · (log n)ᵏ para ver log_b a, o caso do Teorema Mestre e o Θ de T(n), com a forma estendida para k = −1 e k < −1.
- Roda no seu navegador
Resultado
O resultado aparece aqui.
Os três casos do teorema
T(n) = a·T(n/b) + c·nᵈ·(log n)ᵏ, com a ≥ 1 e b maior que 1; L = log_b a
| Comparação de d com L | Resultado Θ(T(n)) |
|---|---|
| d menor que L (caso 1) | Θ(nᴸ) |
| d igual a L, k maior que −1 (caso 2) | Θ(nᵈ · (log n)ᵏ⁺¹) |
| d igual a L, k igual a −1 | Θ(nᵈ · log log n) |
| d igual a L, k menor que −1 | Θ(nᵈ) |
| d maior que L (caso 3) | Θ(nᵈ · (log n)ᵏ) |
L é o expoente do trabalho nas folhas da árvore de recursão; d, o do trabalho em cada nível. O caso 1 vale para qualquer k; no caso 3, f(n) = nᵈ(log n)ᵏ cumpre a condição de regularidade quando d é maior que L. As linhas de k menor ou igual a −1 com d = L são a forma estendida de Akra e Bazzi (1998); o enunciado clássico cobre k ≥ 0.
Exemplos conhecidos
Merge sort, T(n) = 2T(n/2) + n: L = 1 = d, caso 2 com k = 0, Θ(n^1 (log n)^1).
Karatsuba, a = 3, b = 2, d = 1: L = 1,584963 é maior que d, caso 1: Θ(n^1,584963).
Busca binária, a = 1, b = 2, d = 0: L = 0 = d, caso 2: Θ(n^0 (log n)^1), isto é, Θ(log n). Com a = 2, b = 2, d = 2, L = 1 é menor que d: caso 3, Θ(n^2).
Quando o teorema não se aplica
- Divisão em partes desiguais (n/3 e 2n/3, por exemplo) e recorrências sem a forma a·T(n/b): use o método de Akra–Bazzi ou a árvore de recursão.
- Precisa de a ≥ 1 e b maior que 1; a constante c não altera o Θ e só documenta a recorrência.
- f(n) com outras formas, como n·log log n no lugar de uma potência, exige outra análise.
Perguntas frequentes
Como resolver uma recorrência de divisão e conquista pelo Teorema Mestre?
Calcule L = log base b de a e compare com o expoente d de f(n). Se d for menor que L, T(n) = Θ(n^L); se d = L, multiplica-se por log n; se d for maior que L, T(n) = Θ(f(n)). Merge sort tem L = 1 = d.
Quais são os casos do Teorema Mestre?
Caso 1: f(n) cresce mais devagar que n^L e T(n) = Θ(n^L). Caso 2: mesma ordem, e entra um fator de log n. Caso 3: f(n) cresce mais rápido, e T(n) = Θ(f(n)) se a regularidade valer.
Qual a complexidade de T(n)=2T(n/2)+n?
Com a = 2, b = 2 e f(n) = n, L = log base 2 de 2 = 1 = d, caso 2 com k = 0. Logo T(n) = Θ(n log n), a complexidade do merge sort.