Questão 2746369

• Banca: UFLA
• Órgão: UFLA
• Ano: 2018
• Provas: UFLA - 2018 - UFLA - Analista de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação

Analise as proposições abaixo sobre algoritmos e estrutura de dados:

I. Os métodos de ordenação por inserção e bolha possuem complexidade O(n² ) em relação ao número de comparações.

II. Embora O(n² ), o método de ordenação por inserção possui complexidade Ω(n) em relação ao número de comparações.

III. O método de ordenação por inserção, assim como o Quicksort, é estável.

IV. O método de ordenação Quicksort tem complexidade O(n² ) em seu pior caso.

Assinale a alternativa CORRETA:

• A. Somente as proposições I e III estão corretas.
• B. Somente as proposições I e IV estão corretas.
• C. Somente as proposições II e III estão corretas.
• D. Somente as proposições I, II e IV estão corretas.

Gabarito: D

Comentários

• Essa questão usa a notação de complexidade onde Big-O, Big-Ômega e Big-Theta tratam respectivamente do pior caso, melhor caso, e caso médio. 

  A (I) e a (II) me pareceram contraditórias entre si, mas vejam que a (I) traz a notação Big-O (pior caso), e a (II) traz a notação do melhor caso (Big-Ômega). 

   

• Quicksort é instável.

• Força Guerreiro!!!!!!