Resumêra

Questão 1 (Nível Médio) Sobre a notação assintótica Θ (Theta), qual alternativa apresenta corretamente sua definição formal?

A) F(x) ⊆ Θ(G(x)) implica F(x) ≤ C·G(x) para grande x B) F(x) ∈ O(G(x)) e F(x) ∈ Ω(G(x)) não implica necessariamente F(x) ∈ Θ(G(x)) C) Existe C1, C2 > 0 e N0 ≥ 0 tais que C1·G(x) ≤ F(x) ≤ C2·G(x) para x ≥ N0 D) F(x) ∈ Θ(G(x)) significa que F e G são iguais para todo x E) F(x) cresce mais rápido que G(x) para grande x

Resposta correta: C) Existe C1, C2 > 0 e N0 ≥ 0 tais que C1·G(x) ≤ F(x) ≤ C2·G(x) para x ≥ N0

Essa é a definição formal de F(x) ∈ Θ(G(x)).

Questão 2 (Difícil) Considere a recorrência de divisão e conquista: T(n)=4T(n/5)+n³ Utilizando o Teorema Mestre, qual é a complexidade assintótica dessa recorrência?

A) Θ(n^2) B) Θ(n^3) para T(n) = 4 T(n/5) + n^3 C) Θ(n^{log_5 4}) D) Θ(log n) E) Θ(n^3 log n)

Resposta correta: B) Θ(n^3) para T(n) = 4 T(n/5) + n^3

Caso 1 do Teorema Mestre: se a < n^log_b(a) é menor que f(n) = n^c, etc.

Questão 3 (Difícil) Sobre as notações assintóticas utilizadas na análise de algoritmos, assinale a alternativa correta:

A) O é estritamente mais rápido que Θ B) Θ representa crescimento assintótico exato, combinando limites superior e inferior C) pequeno o é sempre maior que O D) Θ é apenas limite superior E) O e Θ são funções idênticas

Resposta correta: B) Θ representa crescimento assintótico que é limitado superior e inferiormente

Θ significa que F e G crescem na mesma taxa, até constantes multiplicativas, para large enough x.

Questão 4 (Extremamente Difícil) Considere um algoritmo que realiza dois loops aninhados, onde o laço externo executa n vezes e o laço interno executa nlogn operações no total. Qual é a complexidade assintótica total do algoritmo?

A) Θ(n^2) B) Θ(n^2 log n) C) Θ(n^3) D) Θ(n log n) E) Θ(log n)

Resposta correta: B) Θ(n^2 log n)

Para T(n) = 4 T(n/2) + n^2, caíríamos no Caso 2 com f(n) ≈ n^{log_b(a)} = n^2, resultando Θ(n^2 log n).

Questões sobre o tema