Questão 3136057

• Banca: Exército
• Órgão: EsFCEx
• Ano: 2019
• Provas: Exército - 2019 - EsFCEx - Oficial - Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

A notação “O” que determina ordem de complexidade e eficiência de um algoritmo pode ser formalizada como se segue:  

                                        T(n) = O (ƒ(n))

                        Se existirem inteiro m e constante c tais que 

                                 T(n) ≤ cƒ(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ⁿ 

• A. T2 < T3
• B. T3 < T1
• C. T4 < T3
• D. T1 > T4
• E. T1 > T2

Gabarito: A

Comentários

• Em relação ao tempo de execução, quanto mais complexo a função, maior o tempo de execução.

  O(n!) > O(2^n) > O(n^2) > O(nlogn) > O(n) > O(logn) > O(1).

  Logo, T4(n) > T3(n) > T2(n) > T1(n).

  T2 < T3.

  Fonte: <https://medium.com/nagoya-foundation/introdu%C3%A7%C3%A3o-%C3%A0-complexidade-de-algoritmos-4a9c237e4ecc>.

• O problema da alterantica C é que no enunciado não coloca T4(n)=2^n e aí fica com a A e C corretas. Acho que foi erro de digitação do Qconcursos

• der o valor de n= 10 calcule e veja o gabarito