SóProvas

ID
802963
Banca
CESPE / CEBRASPE
Órgão
INMETRO
Ano
2010
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Se f é uma função de complexidade para um algoritmo F, então O(f) é considerada a complexidade assintótica ou o comportamento assintótico do algoritmo F. Assinale a opção que apresenta somente algoritmos que possuem complexidade assintótica quando f(n) = O(n log n).

Alternativas
Comentários

  • Errado o Gab!!!
    O QuickSort, no pior caso, tem complexidade O(n^2).

    Mas o HeapSort e MergeSort possuem as mesmas complexidas em qlq caso: O(n log n)

    Fonte: https://pt.wikipedia.org/wiki/Quicksort

  • A questão é de 2010, provavelmente na época ninguém fez recuso com um bom embasamento, essa é a tabela padrão dos algoritmos e seus piores e melhores casos, está claríssimo que o QUICK SORT não tem em seu pior caso complexidade nlogn, mas sim n2, portanto questão DEVERIA ter sido anulada.

     

    Algoritmo             Melhor caso       Pior caso

    ----------------------------------------------------------------------
    Select Sort            n2                         n2

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

    Bubble Sort           n2                        n2

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

    Inserção Direta     n                          n2

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

    Heap Sort             nlogn                   nlogn

    ----------------------------------------------------------------------
    Merge Sort           nlogn                   nlogn
    ----------------------------------------------------------------------
    Quick Sort            nlogn                    n2
    ----------------------------------------------------------------------
     

  • e-

    algos de array com complexidade O(nlogn)

    mergesort

    timesort

    heapsort

    subesort

    quicksort

  • Assintótico é o tamanho da entrada que tende ao infinito.

    MergeSot (pior e Melhor caso),QuickSort (Médio Caso) e HeapSor tque possuem complexidade  O (n log n)

    Gabarito E