Questão 754561

• Banca: Marinha
• Órgão: Quadro Complementar
• Ano: 2011
• Provas: Marinha - 2011 - Quadro Complementar - Segundo-Tenente - Engenharia de Computação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Analise as informações a seguir

Algoritmo: Rearranja o vetor A[ p..r] em ordem crescente, supondo p≤r QuickSort(A, p, r)

1- se p< r

2- então q < - Particione (A,p, r)

3- QuickSort (A,p, q-1)

4- QuickSort (A, q+ 1, r)
Em uma análise do consumo máximo de tempo do algoritmo QuickSort, considerando a função Particione com desempenho EN, qual é o consumo de tempo no pior caso? Considere n igual ao número máximo de elementos.

• A. Ω( log n)
• B. o (√n)
• C. O(n log n)
• D. O (n²)
• E. O (n) 

Gabarito: D

Comentários

• O gabarito é a letra D.

   

  Complexidade no Pior Caso: O(n^2)

  Complexidade no Caso Médio: O(n log n)

  Complexidade no Melhor Caso: O(n log n)