Questão 2055416

Tecnologia da Informação · 2022

Questão

ID 2055416

Disciplina: Tecnologia da Informação

Assuntos: Complexidade de Algoritmos (Big-O, P x NP)

Ano: 2022 Banca: CEPS UFPA - Centro de Processos Seletivos da Universidade Federal do Pará Órgão: Universidade Federal do Pará

Seja V um vetor de n números inteiros distintos. Sobre a complexidade temporal de algoritmos para ordenar V em ordem crescente, é correto afirmar que

Alternativa A:
o algoritmo de ordenação bolha (ou bubblesort) entrega uma complexidade O(n) para qualquer ordenação inicial de V.
Alternativa B:
o algoritmo de ordenação por inserção tem complexidade no pior caso O(n), que ocorre quando V está inicialmente em ordem decrescente.
Alternativa C:
o melhor caso do algoritmo de ordenação rápida (ou quicksort) ocorre quando, a cada sorteio, a mediana de um vetor é escolhida como pivô.
Alternativa D:
a complexidade no pior caso do algoritmo de ordenação por intercalação (ou mergesort) é O(n log n) e a complexidade no melhor caso, que ocorre quando V está inicialmente em ordem crescente, é O(n).
Alternativa E:
o algoritmo de ordenação por monte (ou heapsort) entrega uma complexidade O(log n) no pior caso e no caso médio.