Assinale a opção que apresenta a técnica que tem a maior co...

Próximas questões
Com base no mesmo assunto
Q1686344 Algoritmos e Estrutura de Dados
Assinale a opção que apresenta a técnica que tem a maior complexidade de tempo de execução.
Alternativas

Gabarito comentado

Confira o gabarito comentado por um dos nossos professores

A alternativa correta é a alternativa D - Selection Sort.

Vamos discorrer sobre o tema da questão, que aborda a complexidade de tempo de execução de diversos algoritmos de ordenação. Para responder corretamente, é necessário compreender os conceitos de complexidade de tempo, frequentemente expressos na notação Big O (O(N)), que determina o desempenho de um algoritmo em termos de tempo de execução conforme o tamanho da entrada cresce.

Agora, justificaremos a resposta correta e as razões pelas quais as outras alternativas estão incorretas:

Alternativa D - Selection Sort:

O Selection Sort possui uma complexidade de tempo de execução de O(N²) tanto no pior caso quanto no caso médio. Isso ocorre porque, para cada elemento no array, ele percorre o restante do array para encontrar o menor elemento, resultando em um comportamento quadrático. Dessa forma, entre as alternativas, o Selection Sort é o algoritmo que tem a maior complexidade de tempo de execução.

Alternativa A - Quick Sort:

O Quick Sort, na média, apresenta uma complexidade de tempo de O(N log N). No pior caso, sua complexidade é O(N²), mas esse caso é raro e pode ser evitado com técnicas de escolha de pivô. De qualquer forma, na maioria das implementações e casos práticos, ele é mais eficiente do que o Selection Sort.

Alternativa B - Insertion Sort:

O Insertion Sort possui uma complexidade de O(N²) no pior e no caso médio. Porém, ele é eficiente para conjuntos de dados pequenos ou quase ordenados, onde sua complexidade pode se aproximar de O(N) no melhor caso. Apesar de ser quadrático no pior caso, ele é geralmente mais rápido que o Selection Sort em muitos cenários práticos.

Alternativa C - Bubble Sort:

O Bubble Sort também tem uma complexidade de tempo de O(N²) no pior caso e no caso médio. Contudo, similar ao Insertion Sort, ele é menos eficiente em comparação com outros algoritmos quadráticos devido ao seu maior número de trocas.

Alternativa E - Heap Sort:

O Heap Sort opera com uma complexidade de O(N log N) no pior caso. Ele é mais eficiente do que os algoritmos quadráticos e é usado em aplicações que requerem eficiência garantida no pior cenário.

Portanto, a resposta correta é a alternativa D, pois o Selection Sort tem a maior complexidade de tempo de execução.

Clique para visualizar este gabarito

Visualize o gabarito desta questão clicando no botão abaixo

Comentários

Veja os comentários dos nossos alunos

A ordenação por seleção é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição, depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os n-1 elementos restantes, até os últimos dois elementos. Portanto tem a maior complexidade de tempo de execução. Fonte: 

Complexidade O(n²) > O(n log n) > O(n)

ALGORITMO MELHOR CASO CASO MÉDIO PIOR CASO

BubbleSort O(n) O(n²) O(n²)

InsertionSort O(n) O(n²) O(n²)

SelectionSort O(n²) O(n²) O(n²)

QuickSort O(n log n) O(n log n) O(n²)

ShellSort O(n log n) Depende do gap O(n²)

MergeSort O(n log n) O(n log n) O(n log n)

HeapSort O(n log n) O(n log n) O(n log n)

GABARITO: D

https://s3.ap-south-1.amazonaws.com/afteracademy-server-uploads/comparison-of-sorting-algorithms-compare1-18082c14f960abf3.png

Boa Sorte

Selection Sort complexidade O(n²)

Clique para visualizar este comentário

Visualize os comentários desta questão clicando no botão abaixo