Algoritmos e Estruturas de dados para Engenharia Elétrica - Poli - P3 2017

Prévia do material em texto

Solução
PCS3110 - Algoritmos e Estruturas de Dados para a Engenharia Elétrica Prova 3 - 08/12/2017
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
Utilize caneta azul ou preta para marcar as caixas e preencha a caixa totalmente
para correta interpretação. Exemplo: �. Não use �.
1 Marcos 2 Fábio 3 Romero 4 Anarosa
Marque as caixas ao lado para formar o seu número USP, as caixas acima para
sua turma e seu nome abaixo.
Nome (completo):
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Instruções para a prova
1 Esta prova contém 2 questões dissertativas e 8 testes. Verifique atentamente se todas elas estão presentes. Em
caso de dúvida chame o professor.
2 Preencha seu nome e número USP. Provas não identificadas não serão corrigidas. Alunos cujos NUSP possuem
7 dígitos devem iniciar o preenchimento com um ZERO, da esquerda para a direita.
3 Resolva as questões dissertativas apenas no espaço a elas reservado. Respostas fornecidas fora do local a elas
destinadas não serão corrigidas.
4 A duração total da prova é de 100 minutos.
5 É proibido o uso de calculadoras, relógios, incluindo analógicos e/ou mecânicos e qualquer outro aparelho
eletrônico.
6 É proibido retirar o grampo da prova.
7 A interpretação da questão faz parte da avaliação dos alunos. Caso considere alguma hipótese que não esteja
explicitada no enunciado, indique claramente na resposta.
8 A prova é SEM CONSULTA.
Solução
[2,0 pontos] Questão 1
Preencha a lista L com seu número USP (coloque 0 à esquerda, se necessário).
a) [0,2 ponto] Supondo que L represente uma estrutura Heap, L é:
minHeap: maxHeap: nem minHeap nem maxHeap :
Importante: se, e somente se, a resposta ao item a) for um MaxHeap copie todos os valores de L
para H com posicionamento invertido, ou seja, H passará a ter seu número USP de trás para frente. Caso
contrário, copie todo os valores de L para H sem alteração nos posicionamentos.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 .5 1 2
b) [0,4 ponto] Supondo que H represente uma estrutura Heap, desenhe abaixo a árvore representada por H.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 .5 1 2 3 4
Solução
c) [0,4 ponto] Visando construir uma estrutura MaxHeap a partir da estrutura Heap H, usando MaxHeapify, indique
o primeiro par de posições que terão seus conteúdos trocados entre si:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 .5 1 2 3 4
e Max-Heapify (A, i)
1 esquerda = Filho-Esquerda(i)
2 direita = Filho-Direita(i)
3 if esquerda <=A.heap-size and A[esquerda]>A[i]
4 maior = esquerda
5 else
6 maior = i
7 if direita<=A.heap-size and A[direita]>A[maior]
8 maior = direita
9 if maior != i
10 temp = A[i]
11 A[i] = A[maior]
12 A[maior] = temp
13 Max-Heapify(A, maior)
d) [0,6 ponto] Após transformar H em MaxHeap, pela aplicação do MaxHeapify, como ficará a estrutura H?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 .5 1 2 3 4 5 6
e) [0,4 ponto] Supondo-se que pretenda colocar em ordem crescente o conteúdo de H usando o algoritmo HeapSort,
partindo do MaxHeap H do item d), efetue a primeira troca e a primeira correção do Heap. Apresente abaixo
como ficará a estrutura H, após essa primeira troca e primeira correção.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 .5 1 2 3 4
HeapSort (A)
1 Constroi-MaxHeap(A)
2 for i = A.tamanho downto 2
3 temp = A[1]
4 A[1] = A[i]
5 A[i] = temp
6 A.heap-size = A.heap-size-1
7 Max-Heapify(A, 1)
Constroi-MaxHeap (A)
1 A.heap-size = A.tamanho
2 for i =
⌊
A.tamanho
2
⌋
downto 1
3 Max-Heapify(A, i)
Solução
[3,2 pontos] Questão 2
Cenário: Na USP, os alunos recebem nUSP distintos e sequenciais. Para acelerar a emissão de carteirinhas, deseja-se
que a atribuição dos nUSP seja feita no momento em que os alunos confirmem o interesse na vaga, antes mesmo da
matrícula. Embora útil, isso fará com que os nUSP sejam cadastrados na ordem que os alunos fazem a matrícula,
podendo não ficar em sequência na base dados. Para resolver esse empecilho, sua empresa é contratada para criar um
algoritmo que ordene a lista de nUSP no final do dia de matrículas.
Sistema: Estudando o sistema, você percebe que precisa ordenar um vetor V de tamanho fixo e conhecido. Cada
elemento V[i] desse vetor tem como atributos nUSP e nome, como ilustrado no exemplo simplificado abaixo para os
nUSP de 101 a 112 (apenas as iniciais dos nomes são mostradas):
a [0,6 pontos] Em uma primeira versão proposta, foi sugerido que os nUSP atribuídos antes da matrícula fossem
apenas temporários, ou seja, que seus valores pudessem ser substituídos no vetor V após a matrícula para garantir
a ordenação crescente. Complete o código do algoritmo abaixo para fazer isso. Lembre que os nUSP devem ser
sequenciais e distintos, e assuma que eles devem ser ordenados a partir do valor “min” (obs.: no exemplo, min = 101).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4 5 6
OrdenaNUSPSubstituicao(V, min)
1
2
3
4
5
6 return V
Solução
b [0,8 pontos] Infelizmente, a proposta do item anterior acaba sendo rejeitada porque as carteirinhas USP já
haviam sido impressas com os nomes correspondentes, de modo que os nUSP dos alunos não poderiam ser
substituídos. Por isso, decide-se usar o algoritmo QuickSort para ordenar V.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4 5 6 7 8
[0,3 pontos] Qual será o valor de pivo (linha 2 do QuickSort) retornado pela primeira chamada à função
Partition para o nosso exemplo? Nesse momento, qual será o valor do nUSP em V[1], V[pivo] e V[12]?
Quicksort(A, ini, fim)
1 if ini < fim
2 pivo = Partition(A, ini, fim)
3 Quicksort(A, ini, pivo - 1)
4 Quicksort(A, pivo + 1, fim)
Partition(A, ini, fim)
1 pivo = A[fim]
2 pmenor = ini - 1
3 for pos = ini to fim - 1
4 if A[pos].nUSP <= pivo.nUSP
5 pmenor = pmenor + 1
6 temp = A[pmenor]
7 A[pmenor] = A[pos]
8 A[pos] = temp
9 A[fim] = A[pmenor + 1]
10 A[pmenor + 1] = pivo
11 return pmenor + 1
pivo: V[1].nUSP: V[pivo].nUSP: V[12].nUSP:
[0,5 pontos] E na segunda vez que ‘Partition for chamado, já na chamada recursiva da linha 3 do Quicksort?
pivo: V[1].nUSP: V[pivo].nUSP: V[12].nUSP:
Solução
c [0,8 pontos] Como o QuickSort é mais eficiente quando o pivô corresponde ao valor que divide o vetor
aproximadamente no meio (i.e., a mediana), deseja-se alterar a linha 1 do algoritmo Partition para pivo =
Mediana(V, ini, fim). Escreva um algoritmo para calcular a mediana no cenário apresentado. Dica: aproveite
o fato dos nUSP serem distintos e sequenciais.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4 5 6 7 8
[0,6 pontos] Mediana(V, ini, fim)
1
2
3
4
5
6
7
8
9
[0,2 pontos] Qual a complexidade assintótica de Mediana (notação Θ) em função do tamanho (n) do vetor V?
Θ( )
Solução
d [1,0 ponto] A complexidade assintóticade algoritmos de ordenação como o QuickSort é Θ(n · lgn). Porém, seu
chefe diz ser possível usar um vetor auxiliar para fazer a ordenação com uma complexidade menor, novamente
aproveitando o fato dos nUSP serem distintos e sequenciais. Complete o código abaixo e informe sua complexidade
assintótica em função do tamanho (n) do vetor V, novamente assumindo que os nUSP começam no valor dado
pela variável “min”.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4 5 6 7 8 9 10
[0,8 pontos] OrdenaNUSPRapido (V, min)
1 Seja A[1 .. V.tamanho] um novo arranjo
2
3
4
5
6
7
8
9
10
11 return A
[0,2 pontos] Complexidade:
Solução
[4,8 pontos] Testes
Teste 1 A seguir é apresentado o algoritmo InsertionSort e uma implementação recursiva dele.
Insertion-Sort (A)
1 for j = 2 to A.tamanho
2 chave = A[j]
3 i = j - 1
4 while i > 0 and A[i] > chave
5 A[i+1] = A[i]
6 i = i - 1
7 A[i+1] = chave
Insertion-Sort-Rec (A, j)
1 if j > A.tamanho
2 return
3 chave = A[j]
4 i = j - 1
5 while i > 0 and A[i] > chave
6 A[i+1] = A[i]
7 i = i - 1
8 A[i+1] = chave
9 Insertion-Sort-Rec(A, j + 1)
Sobre esses algoritmos pode-se afirmar:
I Apesar de o tempo de execução em notação Θ dos algoritmos ser igual, o algoritmo recursivo consome mais
recursos devido ao custo computacional da recursão.
II A equação de recorrência do algoritmo recursivo é: T (n) =
{
Θ(1), n < 1
T (n− 1) + Θ(n), n ≥ 1
III Não há diferença de funcionamento do algoritmo recursivo se a linha 1 for if j ≥ A.tamanho.
A Nenhuma afirmação é correta.
B Apenas as afirmações I e III são corretas.
C Apenas a afirmação III é correta.
D Todas as afirmações são corretas.
E Apenas a afirmação I é correta.
F Apenas as afirmações II e III são corretas.
G Apenas as afirmações I e II são corretas.
H Apenas a afirmação II é correta.
Teste 2 O Bubblesort é outro algoritmo popular para ordenação. A ideia dele é trocar elementos adjacentes que
estão fora de ordem. Assinale o conteúdo das posições 1, 4 e 9 do arranjo A = [5, 8, 3, 2, 1, 9, 7, 6, 4] após 2
execuções completas do for da linha 1 (ou seja, imediatamente antes da terceira execução).
BubbleSort (A)
1 for i = 1 to A.tamanho - 1
2 for j = A.tamanho downto i + 1
3 if A[j] < A[j - 1]
4 temp = A[j]
5 A[j] = A[j - 1]
6 A[j - 1] = temp
Posição 1: 1 2 3 4 5 6 7 8 9
Posição 4: 1 2 3 4 5 6 7 8 9
Posição 9: 1 2 3 4 5 6 7 8 9
Solução
Teste 3 O GCC, um dos principais compiladores para C++, utiliza um algoritmo de ordenação conhecido como
IntroSort. Esse algoritmo é um híbrido entre o QuickSort, HeapSort e o InsertionSort. O QuickSort é usado até
um determinado nível da recursão ou até um determinado tamanho de arranjo. Se o nível da recursão for maior que
um limite, usa-se o HeapSort; se o número de elementos for pequeno, executa-se o InsertionSort.
A seguir é apresentada uma implementação simplificada desse algoritmo.
IntroSort (A)
1 profundidade = 2 * blg(A.tamanho)c
2 IntroSortLoop(A, 1, A.tamanho, profundidade)
IntroSortLoop (A, inicio, fim, profundidade)
1 if fim - inicio < 10
2 InsertionSort(A, inicio, fim)
3 else if profundidade == 0
4 HeapSort(A, inicio, fim)
5 else
6 pivo = Partition(A, inicio, fim)
7
8
Como devem ser preenchidas as linhas 7 e 8 do algoritmo IntroSortLoop?
A Linha 7: IntroSortLoop(A, inicio, pivo – 1, profundidade - 1)
Linha 8: IntroSortLoop(A, pivo + 1, fim, profundidade - 1)
B Linha 7: IntroSortLoop(A, inicio, pivo – 1, profundidade)
Linha 8: IntroSortLoop(A, pivo + 1, fim, profundidade)
C Linha 7: IntroSortLoop(A, inicio, pivo, profundidade - 1)
Linha 8: IntroSortLoop(A, pivo, fim, profundidade - 1)
D Linha 7: IntroSortLoop(A, inicio, pivo – 1, profundidade + 1)
Linha 8: IntroSortLoop(A, pivo + 1, fim, profundidade + 1)
E Linha 7: IntroSortLoop(A, inicio, pivo, profundidade + 1)
Linha 8: IntroSortLoop(A, pivo, fim, profundidade + 1)
F Linha 7: IntroSortLoop(A, inicio, pivo, profundidade)
Linha 8: IntroSortLoop(A, pivo, fim, profundidade)
Teste 4 Assinale a alternativa que apresenta o tempo de execução, em notação Θ do algoritmo X abaixo:
X (n)
1 soma = 0
2 for i = 1 to n
3 for j = n downto 1
4 for k = 1 to n*n
5 soma = soma + 1
6 return soma
A Θ(n4)
B Θ(n3)
C Θ(n2)
D Θ(1)
E Θ(n2lgn)
F Θ(n)
G Θ(nlgn)
Solução
Teste 5 Assinale apenas a(s) afirmação(ões) corretas:
A Algoritmos gulosos resolvem problemas de otimização fazendo escolhas localmente ótimas e sempre encontram a
solução ótima. Um exemplo de algoritmo guloso é o Código de Huffman.
B Ao afirmar que um algoritmo é Ω(n2), queremos dizer que não existe entrada de tamanho n para a qual o
algoritmo vai executar em tempo superior a n2.
C Se o algoritmo A é tal que 100n ≤ T (n) ≤ nlgn2 , podemos afirmar que A ∈ Ω(n) e A ∈ O(nlgn).
D Num projeto de algoritmo recursivo que adota a abordagem de Divisão e Conquista, o problema é quebrado em
subproblemas similares e independentes, de menor tamanho, para os quais o algoritmo chama a si mesmo para
resolver.
E Se o algoritmo A é tal que A ∈ Θ(n
√
2), podemos afirmar que A ∈ Ω(n) e A ∈ O(n
√
2).
F Num projeto de algoritmo que usa Programação Dinâmica, o problema de otimização possui substrutura ótima e
é quebrado em subproblemas similares e independentes, de menor tamanho.
Teste 6
Dada a equação de recorrência da execução da Busca
Binária, T (n) =
{
Θ(1), n ≤ 2
T (n2 ) + Θ(1), n > 2
, assinale
todas as alternativas corretas:
A T (n) ∈ Θ(lgn).
B T (n) ∈ O(n).
C T (n) ∈ Ω(1).
D T (n) ∈ Ω(nlgn).
E T (n) ∈ Θ(nlgn).
Solução
Teste 7 O algoritmo de Dijkstra pode ser implementado usando uma fila de prioridade mínima, usando um
Min-Heap, contendo os vértices do grafo e o respectivo valor do caminho mínimo da origem até o vértice. Con-
sidere o grafo da figura e as afirmações I e II sabendo-se que a configuração inicial do Min-Heap é dada por
a/0
1
b/∞
2
c/∞
3
d/∞
4
e/∞
5
f/∞
6
g/∞
7
h/∞
8
i/∞
9
.
Dijkstra (G, origem)
1 for each u ∈ G.V // inicialização
2 u.caminho = ∞
3 u.predecessor = NIL
4 origem.caminho = 0
5 Seja Q uma Fila de Prioridade
6 Q = G.V // coloca em Q todos os vértices
7 while not Queue-Empty(Q)
8 menor = Extrai-Menor(Q) // Q = Q-menor
9 for each v ∈ G.Adjacencia[menor]
10 if v.caminho > peso(G,menor,v) + menor.caminho
11 v.predecessor = menor
12 v.caminho = peso(G,menor,v) + menor.caminho
13 Altera-Prioridade(Q,v)
Extrai-menor (A)
1 if A.heapsize < 1
2 erro underflow do heap
3 menor = A[1]
4 A[1] = A[A.heapsize]
5 A.heapsize = A.heapsize - 1
6 Min-Heapify(A, 1)
7 return menor
Altera-Prioridade (A, i, prioridade)
1 antiga = A[i]
2 A[i] = prioridade
3 if antiga > prioridade
4 while i>1 and A[Pai(i)] > A[i]
5 temp = A[i]
6 A[i] = A[Pai(A[i])
7 A[Pai(A[i])] = temp
8 i = Pai(i)
9 else
10 Min-Heapify(A, i)
Min-Heapify (A, i)
1 esquerda = Filho-Esquerda(i)
2 direita = Filho-Direita(i)
3 if esquerda<=A.heap-size and A[esquerda]<A[i]
4 menor = esquerda
5 else
6 menor = i
7 if direita<=A.heap-size and A[direita]<A[menor]
8 menor = direita
9 if menor != i
10 temp = A[i]
11 A[i] = A[menor]
12 A[menor] = temp
13 Min-Heapify(A, menor)
I Após o final da primeira iteração do while a
configuração da fila de prioridade é dada por:
b/4
1
h/8
2
c/∞
3
i/∞
4
e/∞
5
f/∞
6
g/∞
7
d/∞
8
II Após o final da terceira iteração do while a con-
figuração da fila de prioridade é dada por:
g/9
1
i/15
2
c/12
3
d/∞
4
e/∞
5
f/∞
6
A Apenas a afirmação I é verdadeira.
B Todas as afirmações são falsas.
C Apenas a afirmação II é verdadeira.
D As afirmações I e II são verdadeiras.
Solução
Teste 8 O problema do corte das hastes é um problema de otimização que consiste em encontrar a estratégia de
corte de uma haste de tamanhon que maximize a receita obtida com sua venda. Assim, uma haste de tamanho 3
pode ser cortada em 3 pedaços de tamanho 1; ou 2 pedaços, sendo um de tamanho 2 e outro de tamanho 1; ou não ser
cortada. A configuração de corte que der a maior receita é a solução para o problema, cuja relação de recorrência é
dada pela expressão:
rn =
{
0, n = 0
max1≤i≤n{pi + rn−i} n > 0
onde, rn é a receita para uma haste de tamanho n e pi é o preço do i-ésimo pedaço.
Um algoritmo de Programação Dinâmica que resolve este problema usando a abordagem bottom-up é o
Bottom-Up-Cut-Rod(p,n). Assinale a alternativa que corretamente completa a linha 6 do algoritmo.
A p[i]+r[j-i]
B max{q, p[i]+r[i]}
C p[i]+Bottom-Up-Cut-Rod(p,j-i).
D p[n-i]+Bottom-Up-Cut-Rod(p,i).
E max{q, p[i]+r[j-i]}.
Bottom-Up-Cut-Rod(p,n)
1 seja r[0..n] um novo arranjo
2 r[0]=0
3 for j=1 to n
4 q = −∞
5 for i=1 to j
6 q =
7 r[j] = q
8 return r[n]
Gabarito Questão 2
Cenário: Na USP, os alunos recebem nUSP distintos e sequenciais. Para acelerar a emissão de
carteirinhas, deseja-se que a atribuição dos nUSP seja feita no momento em que os alunos
confirmem o interesse na vaga, antes mesmo da matrícula. Embora útil, isso fará com que os
nUSP sejam cadastrados na ordem que os alunos fazem a matrícula, podendo não ficar em
sequência na base dados. Para resolver esse empecilho, sua empresa é contratada para criar um
algoritmo que ordene a lista de nUSP no final do dia de matrículas. 
Sistema: Estudando o sistema, você percebe que precisa ordenar um vetor V de tamanho fixo e
conhecido. Cada elemento V[i] desse vetor tem como atributos nUSP e nome, como ilustrado no
exemplo simplificado abaixo para os nUSP de 101 a 112 (apenas as iniciais dos nomes são
mostradas): 
1) (0.6 pontos) Em uma primeira versão proposta, foi sugerido que os nUSP pré-matricula
fossem apenas temporários, ou seja, que seus valores pudessem ser substituídos no vetor V para
garantir a ordenação crescente. Isso permite a construção de um algoritmo bem simplespara
fazer isso. Complete o código desse algoritmo. Lembre que os nUSP devem ser sequenciais e
distintos, e assuma que eles devem ser ordenados a partir do valor “min” (obs.: no exemplo, min
= 101).
OrdenaNUSPSubstituicao(V, min)
1. for i = 0 to V.tamanho – 1 OU 1. for i = 1 to V.tamanho
2. V[i+1].nUSP = min + i 2. V[i].nUSP = min + i - 1
3. return V
Obs.: Algoritmo esperado na resposta é Θ(n). Usar QuickSort/MergeSort/HeapSort é solução
"sem pensar muito", então recebe no máximo 1/2 do valor da questão . Usar qualquer algoritmo
com complexidade pior do que O(n lgn) do QuickSort/MergeSort/HeapSort não faz muito
sentido, então recebe no máximo 1/3 do valor da questão (se estiver correto).
2) (0,8 pontos) Infelizmente, a proposta do item anterior acaba sendo rejeitada porque as
carteirinhas USP já haviam sido impressas com os nomes correspondentes, de modo que os
nUSP dos alunos não poderiam ser substituídos. Por isso, decide-se usar o algoritmo QuickSort
para ordenar V. 
Quicksort(V, ini, fim)
1 if ini < fim
2 pivo = Partition(V, ini, fim)
3 Quicksort(V, ini, pivo – 1)
4 Quicksort(V, pivo + 1, fim)
Partition(V, ini, fim)
1 pivo = V[fim]
2 pmenor = ini – 1 
3 for pos = ini to fim - 1
4 if V[pos].nUSP <= pivo.nUSP
5 pmenor = pmenor + 1
6 temp = V[pmenor]
7 V[pmenor] = V[pos]
8 V[pos] = temp
9 V[fim] = V[pmenor + 1]
10 V[pmenor + 1] = pivo
11 return pmenor + 1
Qual será o valor de “pivo” (linha 2 do QuickSort) retornado pela primeira chamada 
à função “Partition” para o nosso exemplo? Nesse momento, qual será o valor do 
nUSP em V[1], V[pivo] e V[12]?
pivo: 12 V[1].nUSP: 104 V[pivo].nUSP: 112 V[12].nUSP: 112
E na segunda vez que “Partition” for chamado, já na chamada recursiva da linha 3 
do Quicksort?
pivo: 6 V[1].nUSP: 104 V[pivo].nUSP: 106 V[12].nUSP: 112
3) (0,8 pontos) Como o QuickSort é mais eficiente quando o pivô corresponde ao valor que
divide o vetor aproximadamente no meio (i.e., a mediana), deseja-se alterar a linha 1 do
algoritmo “Partition” para “pivo = Mediana(V, ini, fim)”. Escreva um algoritmo para calcular a
mediana no cenário apresentado. Dica: aproveite o fato dos nUSP serem distintos e sequenciais.
Mediana(V, ini, fim)
1. mediana = 0 
2. for i = ini to fim
3. mediana = mediana + V[i].nUSP
4. mediana =  mediana/(fim – ini + 1)  // ou mediana =  mediana/(fim – ini + 1) 
5a. return mediana // Se retornar valor do pivô
5b. for i = ini to fim // Se retornar ponteiro p/ pivô
6b. if V[i].nUSP == mediana // --
7b. return V[i] // --
Obs.: O algoritmo de Partition precisa do ponteiro para o pivô, mas o enunciado dá a entender
que o valor do pivô deve ser retornado. Por isso, não há desconto nesses dois casos, mas há (de
0.1 ponto) se for retornado o índice para o pivô.
Qual a complexidade assintótica de “Mediana” (notação Θ) em função do tamanho (n) do vetor
V?
Θ(n): só é atribuída nota a este item se o algoritmo fizer algum sentido (não precisa estar
perfeito, mas tem que ao menos tentar resolver o problema...)
4) A complexidade assintótica de algoritmos de ordenação como o QuickSort é Θ(n*lgn). Porém,
seu chefe afirma ser possível usar um vetor auxiliar para fazer a ordenação com uma
complexidade menor, novamente aproveitando o fato dos nUSP serem distintos e sequenciais.
Complete o código abaixo e informe sua complexidade assintótica em função do tamanho (n) do
vetor V, novamente assumindo que os nUSP começam no valor dado pela variável “min.
(0.8 pontos) OrdenaNUSPRapido (V, min)
1. Seja A[1 .. V.tamanho] um novo arranjo
2. for i = 1 to V.tamanho OU 2. target = V[1] //solução sem usar A
3. pos = V[i].nUSP - min + 1 3. for i = 1 to V.tamanho
4. A[pos] = V[i] 4. pos = target - min + 1
5. temp = target
6. target = V[pos] 
7. V[pos] = temp
8. return
return A
Obs.: Se algoritmo obtido não é melhor do que O(n lgn ), a nota é bastante reduzida (no máximo
1/4 do valor do algoritmo).
Complexidade: Θ(n). Obs.: só é atribuída nota a este item se o algoritmo fizer algum sentido
(não precisa estar perfeito, mas tem que ao menos tentar resolver o problema...)
	GabaritoP3Testes
	P3_Q2_GABARITO