Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Qual a complexidade computacional dessas relações de recorrência de acordo com o Teorema Mestre (master theorem)?

0 votos
90 visitas
perguntada Abr 8, 2016 em Ciência da Computação por danielcajueiro (5,666 pontos)  

As relações de recorrência que estou interessado são:

1) \(T(n)=4T(n/2)+n\)

2) \(T(n)=4T(n/2)+n^2\)

3) \(T(n)=4T(n/2)+n^3\)

Compartilhe

1 Resposta

0 votos
respondida Abr 8, 2016 por danielcajueiro (5,666 pontos)  

Considere essa versão do Teorema Mestre:

Seja \(a\ge 1\) e \(b>1\) constantes, \(f(n)\) uma função e \(T(n)\) definida usando a recorrência \[T(n)=a T(n/b) + f(n)\]

onde \(n/b\) significa \(floor {(n/b)}\) ou \(ceil {(n/b)}\).

Então \(T(n)\) tem os seguintes limitantes:

Se \(f(n)=O(n^{\log_{b} a-\epsilon})\) para algum \(\epsilon>0\), então \(T(n)=\Theta(n^{\log_{b} a})\).

Se \(f(n)=\Theta(n^{\log_{b} a})\) para algum \(\epsilon>0\), então \(T(n)=\Theta(n^{\log_{b} a}log_b n)\).

Se \(f(n)=\Omega(n^{\log_{b} a+\epsilon})\) para algum \(\epsilon>0\) e se \(af(n/b)\le c
f(n)\) para algum \(c<1\), então \(T(n)=\Theta(f(n))\).</p>

Note que esses problemas são uma aplicação direta do Teorema Mestre:

1) A primeira relação de recorrência cai no caso 1. Logo, \(T(n)=\Theta(n^2)\).

2) A segunda relação de recorrência cai no caso 2. Logo, \(T(n)=\Theta(n^2 \log n)\).

3) A terceira relação de recorrência cai no caso 3. Logo, \(T(n)=\Theta(n^3)\).

...