Questão 1510872 de Tecnologia da Informação - Legalle Concursos 2023

Questão

ID 1510872

Disciplina: Tecnologia da Informação

Assuntos: Complexidade de Algoritmos (Big-O, P x NP)

Ano: 2023 Banca: Legalle Concursos Órgão: Defensoria Pública do Estado do Pará

Acerca do Teorema mestre, sejam a ≥ 1 e b > 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) = O(n_{logb a}-) para alguma constante > 0, então T(n) = Θ(n_{log b a}).

II. Se f(n) = Θ(n_{logb a}), então T(n) = Θ(n_{logb a} lg n).

III. Se f(n) = (n_{logb 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.

Alternativa A:
No caso I, se a função \(n_{\log^{ba}}\) a for a maior, então a solução é T(n) = Θ( \(n_{\log^{ba}}\) ).
Alternativa B:
No caso III, se a função f(n) for a maior, então a solução é T(n) = Θ(f(n/b)).
Alternativa 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) = Θ ( \(n_{\log^{ba}}\) lg n) = Θ( \(n_{\log^{f\left(n\right)}}\) lg n).
Alternativa D:
No caso I, f(n) não só tem de ser menor que \(n_{\log^{ba}}\) , mas deve ser polinomialmente maior. Isto é, f(n) deve ser assintoticamente menor que \(n_{\log^{ba}}\) por um fator n para alguma constante >0.
Alternativa E:
No caso III, f(n) não apenas deve ser maior que \(n_{\log^{ba}}\) , ela tem de ser polinomialmente maior e, além disso, satisfazer à condição de "regularidade" expressa por af (n/b) ≥ cf (n).

Estatísticas Cadernos

Questão 1510872

Continue estudando na plataforma