Seu próximo nível começa aqui
Seu desenvolvimento não pode ter limites. Garanta sua Assinatura Ilimitada e libere uma preparação completa com os melhores professores do Brasil.
Acerca do Teorema mestre, sejama21eb > 1 constantes...
Acerca do Teorema mestre, sejama21eb > 1 constantes, seja f(n) uma função 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:
I. Se f(n) = (nlogb a-) para alguma constante > 0, então T(n) =Θ(nlogb a) .
II. Se f(n) = Θ(nlogb a), então T(n) = Θ(nlogb a ig n).
III. Se f(n) = (Nlogb a+) 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)).
Nesse sentido, assinale a alternativa CORRETA.
A
No caso I, se a função nlogb a a à for a maior, então a solução é T(n) = Θ (nlogb a)
B
No caso III, se a função f(n) for a maior, então a solução é T(n) = Θ(f(n/b)).
C
No caso II, se as duas funções tiverem o mesmo tamanho, multiplicamos por um fator logarítmico e a solução é T(n) =Θ(nlog b a ig n) = Θ (nlog f(n) ig n)
D
No caso I, f(n) não só tem de ser menor que nlogb a, mas deve ser polinomialmente maior. Isto é, f(n) deve ser assintoticamente menor que nlogb a por um fator n para alguma constante > 0.
E
No caso lII, f(n) não apenas deve ser maior que nlogb,a ela tem de ser polinomialmente maior e, além disso, satisfazer à condição de “regularidade” expressa por af(n/b) ≥ cf(n).