Gabarito disponível
A notação “O” que determina ordem de complexidade e eficiência de um algoritmo pode ser formalizada como se segue:
T(n) = O(f(n))
Se existirem inteiro m e constante c tais que
T(n) ≤ cf(n) para n > m.
Para uma entrada n e um tempo T, melhorias substanciais podem ser obtidas ao utilizarmos diferentes algoritmos. Assinale a alternativa correta com relação ao tempo de execução, para uma mesma entrada (n), porém utilizando algoritmos diferentes.
Considere as seguintes ordens de complexidade no tempo:
T1(n) = n, T2(n) = nlogn, T3(n) = n², T4(n) = 2ⁿ
T(n) = O(f(n))
Se existirem inteiro m e constante c tais que
T(n) ≤ cf(n) para n > m.
Para uma entrada n e um tempo T, melhorias substanciais podem ser obtidas ao utilizarmos diferentes algoritmos. Assinale a alternativa correta com relação ao tempo de execução, para uma mesma entrada (n), porém utilizando algoritmos diferentes.
Considere as seguintes ordens de complexidade no tempo:
T1(n) = n, T2(n) = nlogn, T3(n) = n², T4(n) = 2ⁿ
Resolução comentada
Para n grande, n log n cresce menos que n², logo T2 < T3.
Comparando as ordens: n < n log n < n² < 2ⁿ. Assim, o algoritmo T2 (n log n) é mais eficiente que o T3 (n²) para entradas grandes.
Análise das alternativas
B) T3 n. C) T4 T4 é falso, pois n T2 é falso, pois n < n log n para n grande.
Referência: Cormen et al.; Ziviani – Análise assintótica.
Resolução comentada do VaiConcursos.