Questão 3546319

• Banca: SUGEP - UFRPE
• Órgão: UFRPE
• Ano: 2019
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação; Complexidade de Algoritmos

Os algoritmos de ordenação são utilizados para os mais diversos cenários de dados. Apesar de terem o mesmo objetivo (ordenação), possuem diferentes complexidades em relação ao número (n) de elementos a serem ordenados. O “quiksort” se destaca como um dos algoritmos mais rápidos para ordenação. No pior caso, a complexidade “quicksort” será:

• A. O(logn)
• B. O(n logn)
• C. O(n)
• D. O(n²)
• E. O(n )

Gabarito: D

Comentários

• Quicksort

  Possui complexidade O(n²) no pior caso e O(n log n) no caso médio;

  Alternativa: D

• A maioria dos algoritmos de ordenação tem a pior complexidade O(n²)

• Algoritmo            Melhor caso   Pior caso

  ----------------------------------------------------------------------

  Select Sort           n2                n2

  ----------------------------------------------------------------------

  Bubble Sort           n2                n2

  ----------------------------------------------------------------------

  Inserção Direta     n2                 n2

  ----------------------------------------------------------------------

  Heap Sort            nlogn            nlogn

  ----------------------------------------------------------------------

  Merge Sort          nlogn             nlogn

  ----------------------------------------------------------------------

  Quick Sort           nlogn              n2

  ----------------------------------------------------------------------

• Força Guerreiro!!!!!!