A ordenação é um problema muito importante para os desenvolvedores de software. Para implementá-la, existem vários algoritmos que já foram amplamente estudados, como o BubbleSort, o QuickSort e o MergeSort. Uma das características estudadas desses algoritmos é o tempo de execução, que, usualmente, é medido através da notação O (Big-O). Sobre esses conceitos, julgue os itens a seguir.
I. O tempo de pior caso do algoritmo QuickSort é de ordem menor que o tempo médio do algoritmo Bubblesort.
II. O tempo médio do QuickSort é O(nlog n) , pois ele usa como estrutura básica uma árvore de prioridades.
III. O tempo médio do QuickSort é de ordem igual ao tempo médio do MergeSort.
É CORRETO apenas o que se afirma em?
a) I.
b) III.
c) II e III.
d) II.
E) I e III.
A alternativa correta é a letra E) I e III. Justificativa: I. O tempo de pior caso do algoritmo QuickSort é de ordem menor que o tempo médio do algoritmo Bubblesort. - Correto. O pior caso do QuickSort é O(n^2), enquanto o pior caso do BubbleSort é O(n^2) e o tempo médio do QuickSort é O(nlogn), que é menor que o tempo médio do BubbleSort. II. O tempo médio do QuickSort é O(nlog n), pois ele usa como estrutura básica uma árvore de prioridades. - Correto. O QuickSort usa uma árvore de prioridades para dividir a lista em sub-listas menores, o que resulta em um tempo médio de O(nlogn). III. O tempo médio do QuickSort é de ordem igual ao tempo médio do MergeSort. - Incorreto. O tempo médio do QuickSort é O(nlogn), enquanto o tempo médio do MergeSort é O(nlogn) também, mas com uma constante maior.
Para escrever sua resposta aqui, entre ou crie uma conta
Análise e Desenvolvimento de Sistemas
•UVA
Análise e Desenvolvimento de Sistemas
•DOCTUM
Compartilhar