Questão de TI - Desenvolvimento de Sistemas — Outros Tópicos de Desenvolvimento de Sistemas — Legalle 2023
TI - Desenvolvimento de SistemasOutros Tópicos de Desenvolvimento de Sistemas
- Código
- qa541837
- Banca
- Legalle
- Órgão
- DPE PA
- Ano
- 2023
- Cargo
- AnaDP ( )
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) = \Theta(nlogb a-) para alguma constante > 0, então T(n) =\Theta(nlogb a) :
II. Se f(n) = \Theta(nlogg a), então T(n) = \Theta(miogb ig n).
III. Se f(n) = (Nlogb a+) para alguma constante > 0, e se af(n/b) \le cf(n) para alguma constante c < 1 e todos os n suficientemente grandes, então T(n) = \Theta(f(n))
Nesse sentido, assinale a alternativa CORRETA.
- ANo caso I, se a função nlogb a a à for a maior, então a solução é T(n) = \Theta (nlogb a)
- BNo caso III, se a função f(n) for a maior, então a solução é T(n) = \Theta(f(n/b)).
- CNo caso II, se as duas funções tiverem o mesmo tamanho, multiplicamos por um fator logarítmico e a solução é T(n) =\Theta nlog b a ig n) = \Theta (nlog f(n) ig n)
- DNo 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 Nog? 3 POr um fator n para alguma constante > 0.
- ENo caso II, 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) \ge cf(n).