Ordenação de dados com métodos eficientes e uso de Python Teoria dos Grafos e Análise de Algoritmos - Exercícios

Prévia do material em texto

Ordenação de dados com métodos eficientes e uso de Python – Teoria
dos Grafos e Análise de Algoritmos
Exercícios
1. O algoritmo de ordenação rápida utiliza um pivô para recursivamente ordenar o
vetor. Em cada chamada da função de partição, os elementos menores que o pivô
são colocados na esquerda e os maiores que o pivô na direita. Essa operação é
repetida até que reste apenas um elemento.
Dado o vetor [13, 87, 63, 91, 55] e o pivô 55, qual das opções a seguir é válida após
a primeira execução da função partição?
Você acertou!
A. [13, 55, 63, 91, 87].
O   algoritmo   de   ordenação   rápida   utiliza   pivôs   para   ordenar   o   vetor.   Nesse
exercício, o objetivo é executar uma vez a função de partição utilizando o pivô 55.
O vetor original é o [13, 87, 63, 91, 55]. Da esquerda para a direita, os elementos
menores que o pivô vão sendo armazenados, enquanto na direita os maiores que
o pivô. O próprio pivô é inserido à direita dos menores elementos. No caso desse
exemplo, o 13 é o único elemento menor que o pivô. O 55, que é o pivô, é trocado
pelo 87, que é a primeira posição após o elemento menor. Nesse caso, o vetor
após a primeira execução da função partição será [13, 55, 63, 91, 87].
2. A complexidade de tempo de melhor caso da ordenação rápida ocorre quando o
elemento escolhido como pivô divide o vetor exatamente ao meio.
No exemplo [M, Q, S, I, B], qual elemento escolhido como pivô resultaria no melhor
caso de execução da ordenação rápida?
Você acertou!
E. M.
O melhor caso da ordenação rápida ocorre quando o pivô escolhido é a mediana
do vetor analisado. No exemplo do nosso vetor [M, Q, S, I, B], a mediana é o M,
que dividiria o vetor em dois subvetores: [I, B] e [Q, S].
3. A ordenação por mistura ordena, de forma recursiva, sequências a partir de
subsequências já ordenadas. Na fase de divisão, os elementos são recursivamente
divididos.
Dado o vetor [7, 4, 9, 5, 1], quantas chamadas recursivas serão feitas na fase de
divisão?
Você acertou!
E. 8.
O vetor original é o [7, 4, 9, 5, 1]. As duas primeiras chamadas recursivas serão [7,
4, 9] e [5, 1]. Após, serão feitas mais quatro chamadas: [7, 4]; [9]; [5] e [1]. Por fim,
mais duas chamadas serão feitas: [7] e [4]. O total de chamadas recursivas é 8.
4. O melhor e o pior caso da ordenação por mistura é o mesmo, O(n log2 n). Dado
um vetor totalmente desordenado [8, 7, 6, 5, 4, 3, 2, 1], qual será o estado do vetor
após duas execuções da função merge?
Você acertou!
B. [7, 8, 5, 6, 4, 3, 2, 1].
Inicialmente,   a  ordenação  por  mistura   irá  dividir   os  elementos  até   chegar  em
vetores   de   tamanho   um.   Após,   a   fase   de   conquista   começará   e   a
função merge será utilizada.  A  recursão vai   toda para a esquerda e a primeira
execução do merge irá ordenar o vetor [8, 7], resultando em [7, 8, 6, 5, 4, 3, 2, 1].
Na segunda execução do merge, o vetor [6, 5] será ordenado. Resultando no vetor
[7, 8, 5, 6, 4, 3, 2, 1].
5. A implementação dos algoritmos eficientes tem como base a técnica de divisão e
conquista. Em ambas as ordenações, por mistura e rápida, o ponto-chave é a
complexidade de tempo das funções de partição e de merge.
Qual é a complexidade de tempo dessas funções quando executadas N vezes para
um vetor de N posições?
Você acertou!
D. O(N2).
A complexidade de ambos os algoritmos é Nlog2 N, sendo que log2 N é a altura
da árvore de divisão e N é o custo de cada chamada, as funções partição e merge.
A questão pergunta a complexidade de executar essas funções N vezes. O que
resulta em N vezes O(N), ou seja, O(N2).
	Ordenação de dados com métodos eficientes e uso de Python – Teoria dos Grafos e Análise de Algoritmos
	Exercícios