Questão 880248

Tecnologia da Informação · 2021

Questão

ID 880248

Disciplina: Tecnologia da Informação

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

Ano: 2021 Banca: FAPEC - Fundação de Apoio à Pesquisa ao Ensino e à Cultura Órgão: Polícia Civil do Mato Grosso do Sul

Algoritmos de ordenação por comparação são aqueles em que a ordem dos elementos na solução é determinada exclusivamente por meio da comparação entre elementos da entrada. Tais algoritmos são necessários quando não se sabe nenhuma outra informação sobre a entrada (como por exemplo, o maior elemento ou a quantidade de bits de cada elemento), além da ordem relativa entre os elementos. Para uma entrada, nessas condições com n elementos, assinale a alternativa correta.

Alternativa A:
Existe apenas um algoritmo conhecido que pode ordenar esses elementos em tempo \(O\ \left(n\ \log_2\ n\right)\) no pior caso.
Alternativa B:
A implementação padrão do algoritmo Ordenação por Separação, ou Quick Sort, ordenará este conjunto em tempo no \(O\ \left(n\ \log_2\ n\right)\) pior caso.
Alternativa C:
No melhor caso, o algoritmo Ordenação por Inserção, ou Insertion Sort, termina em tempo \(Θ\left(n^2\right)\) .
Alternativa D:
Qualquer algoritmo de ordenação por comparação deverá realizar \(Ω\ \left(n\ \log_2\ n\right)\) comparações no pior caso.
Alternativa E:
Algoritmos de ordenação por comparação podem ordenar os n elementos apenas se eles forem números inteiros ou reais.

Estatísticas Cadernos

Questão 880248

Continue estudando na plataforma