TeoremaMestre_GeovanioJose

Prévia do material em texto

Universidade Federal do Agreste de Pernambuco
Bacharelado em Ciência da Computação
Projeto e Análise de Algoritmos
Prof° Álvaro Alvares
Geovânio José da Silva
Teorema Mestre
O teorema mestre é um dos métodos mais utilizados para resolver equações de recorrências de algoritmos que usam a estratégia de divisão e conquista. Comparado com outros métodos, ele é simples e intuitivo. Além disso, ele resolve boa parte das equações de recorrência.
O Teorema utiliza as notações assintóticas O, Θ e Ω. De forma genérica, o teorema mestre resolve recorrências que possuem a seguinte forma:
T(n)=aT(n/b)+f(n)
Onde n é o tamanho do problema. Os valores de a e de b são constantes. O valor de a é igual ao número de subproblemas no qual o problema original foi dividido. O valor n/b é o tamanho de cada um desses subproblemas. A função f(n) representa o custo no tempo de cada chamada recursiva do algoritmo analisado.
Segundo CORMEN (2012), temos que sejam a≥1 e b>1 constantes, seja f(n) uma função assintoticamente positiva e seja T(n) definida no domínio dos números inteiros não negativos pela recorrência
T(n)=aT(n/b)+f(n)
onde interpretamos que n/b significa ⌊n/b⌋ou ⌈n/b⌉. Então, T(n) tem os seguintes limites assintóticos:
· Se f(n)=O(nlogba−ϵ)para alguma constante ϵ>0, então T(n)=Θ(nlogba).
· Se f(n)=Θ(nlogba), então T(n)=Θ(nlogba lg n).
· Se f(n)=Ω(nlogba+ϵ) para alguma constante ϵ>0, e se af(n/b)≤cf(n) para alguma constante c<1 e todos os n suficientemente grandes, então T(n)=Θ(f(n)).
A primeira coisa a ser feita para aplicar o teorema mestre é identificar as constantes a e b e a função f(n).
Certo cuidado deve ser tomado na hora de identificar a constante b, ela é o divisor na divisão n/b. Quando temos T(2n/3), por exemplo, o valor de b é igual a 3/2, pois 2n/3 = n/(3/2).
Também deve ser analisado os valor das constantes. O valor de a deve ser maior ou igual a 1, afinal o algoritmo deve gerar pelo menos um subproblema (com exceção quando é caso base). Já a constante b deve ser maior do que 1, senão ao invés de dividir o problema, estaríamos gerando subproblemas maiores que o problema original.
Em todos os três casos, deve ser calculado o valor de logba e comparar as funções f(n) e nlogba.
O valor de ϵ nos casos 1 e 3 pode ser qualquer valor real maior do que zero que satisfaça a notação assintótica do caso analisado.