UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
Disciplina: Estrutura de Dados II
Professor: Renato E. N. de Moraes
Aluno:
Turma: 4EC/5CC
Data: 13/11/15
Semestre: 2015-2 Valor: 0,0 pts
Lista de exercícios 04
Nota:
1. O que é a eficiência assintótica de um algoritmo. Explique com suas palavras.
Efici^
encia assintótica é a efici^
encia que um algoritmo terá quando ele receber uma entrada muito grande.
2. Qual a importância prática da notação O?
A notaç~
ao O define qual será o pior caso de execuç~
ao de um algoritmo, o que possibilita saber se um algoritmo é aplicável ou n~
ao a determinado problema.
3. Explique o que significa um algoritmo de ordenação necessitar de 2n2 + 7n + 9 comparações e
como isto está relacionado a seu tempo de execução.
Isso significa que para ordenar um arquivo de por exemplo 10 registros, o algoritmo
necessitará executar 2(10)2 + 7(10) + 9 = 279 comparaç~
oes, ou seja, quanto maior a entrada, maior será o tempo de execuç~
ao do algoritmo, pois maior será o número de comparaç~
oes.
4. Qual algoritmo você julga melhor: um que executa utilizando 700n + 2000 operações ou outro que
utiliza 0, 3n2 + n operações para resolver um mesmo problema?
O que executa em 700n+2000, pois para uma entrada muito grande ele realizará um número menor de operaç~
oes e consequentemente executará em menor tempo.
Igualando as funç~
oes 700n+2000 e 0, 3n2 +n, chegamos a um resultado que mostra quando
os algoritmos ter~
ao o mesmo número de operaç~
oes para uma entrada n, e que para valores maiores que esse saberemos qual algoritmo fará menos operaç~
oes. A partir de 2333
chaves, o algoritmo 700n + 2000 passará a fazer menos operaç~
oes que 0, 3n2 + n.
5. Suponha que você dispõe de um algoritmo A, O(n2 ), e outro B, O(n log n), ambos resolvendo um
mesmo problema. Sabe-se, cotidianamente, que o algoritmo A é mais usado, pois é mais rápido
que B. Como?
O algoritmo A é mais usado, pois provavelmente o algoritmo raramente é utilizado com
uma entrada que te garante o pior caso, podendo dessa forma ser executando em um tempo
menor que o algoritmo B.
6. Qual a ordem de complexidade O(f (n)) para as funções:
(a) 40n3
(b) 0, 3n2 − 2n
(c) 45 log n + n
(d) 8 log n + 2 log4 n + log7 8n
(e) n2 + log20 n
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
(f) n2 + 2n
Respostas:
(a) O(n3 )
(b) O(n2 )
(c) O(n)
(d) O(log 7 n)
(e) O(n2 )
(f) O(n2 )
7. Qual o algoritmo mais eficiente segundo as funções da questão anterior? Qual o menos eficiente?
O mais eficiente seria o algoritmo da letra d e o menos eficiente seria o da letra a.
8. Por que, em geral, é melhor trocar um algoritmo por outro mais eficiente do que simplesmente
aumentar o poder de processamento de um computador (e.g., trocar por um processador mais
potente)?
Pois trocando o algoritmo por um mais eficiente voc^
e terá ganho de tempo independente
do hardware, ou seja seu algoritmo executará mais rápido para o mesmo tamanho n de entrada sem necessitar comprar um hardware novo.
9. O procedimento seguinte faz o preenchimento de um vetor. No algoritmo, identifique claramente
o que representa o tamanho do problema e, em função disso, faça a análise completa de complexidade de tempo. Não são necessárias provas formais.
Proc Preenche(var A: arranjo; Tam: inteiro)
A[0] = 1
Para I = 1 até Tam-1
Se I mod 2 = 0 { par }
Ent~
ao A[I] = 3 * H[I-1] + 1
Sen~
ao A[I] = 0
Para J = 0 até I-1
A[I] = A[I] + A[J]
Fim-para
Fim-se
Fim-para
Fim-proc
A complexidade será:
n−1
P
n−1
2
n−1
2
f (i) =
i=1
P
p=1
1+
P
p=1
n−1
2
2p+1 =
P
p=1
n−1
2
1+2
P
p=1
n−1
2
p+
P
p=1
n−1
2
1 = n−1+2
P
p=1
p = (1+ n−1
2 )∗(n−1)+n−1 =
O(n2 )
Onde:
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
1, i%2 = 0
f (i) =
x, i%2 =
6 0
10. Porque podemos descartar os termos de menor ordem e todos os coeficientes da expressão que
representa o custo de um algoritmo quando consideramos sua eficiência assintótica?
Pois a efici^
encia assintótica analisa o algoritmo com um valor muito grande de n, valor
esse que se sobresairá dos demais termos constantes da equaç~
ao de custo do algoritmo.
11. Qual a ordem de complexidade do algoritmo que faz pesquisa binária em uma tabela? Qual o
número mínimo de comparações com a chave de busca que pode ocorrer até achar um registro
na tabela? Qual o número máximo?
O(log(n)), o mı́nimo de comparaç~
ao é 1, quando o elemento buscado é o elemento central
da tabela e o número máximo será log(n), onde n é o tamanho da tabela.
12. Utilizando o algoritmo da Seleção Direta
(a) Mostre, passo a passo, os estágios da ordenação do vetor [3, 19, 25, 24, 1, 8, 10, 7, 9, 12, 10].
1 − [3, 19, 25, 24, 1, 8, 10, 7, 9, 12, 10]
2 − [1, 19, 25, 24, 3, 8, 10, 7, 9, 12, 10]
3 − [1, 3, 25, 24, 19, 8, 10, 7, 9, 12, 10]
4 − [1, 3, 7, 24, 19, 8, 10, 25, 9, 12, 10]
5 − [1, 3, 7, 8, 19, 24, 10, 25, 9, 12, 10]
6 − [1, 3, 7, 8, 9, 24, 10, 25, 19, 12, 10]
7 − [1, 3, 7, 8, 9, 10, 24, 25, 19, 12, 10]
8 − [1, 3, 7, 8, 9, 10, 10, 25, 19, 12, 24]
9 − [1, 3, 7, 8, 9, 10, 10, 12, 19, 25, 24]
10 − [1, 3, 7, 8, 9, 10, 10, 12, 19, 25, 24]
11 − [1, 3, 7, 8, 9, 10, 10, 12, 19, 24, 25]
(b) O que você poderia dizer sobre o pior e sobre o melhor caso para este algoritmo?
Melhor caso: O(n)
Pior caso: O(n2 )
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
13. Escreva uma versão recursiva do algoritmo de ordenação por seleção.
Resposta:
void selection(int list[], int i, int j, int size, int flag){
int temp;
if (i < size - 1){
if (flag)
{
j = i + 1;
}
if (j < size){
if (list[i] > list[j]){
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
selection(list, i, j + 1, size, 0);
}
selection(list, i + 1, 0, size, 1);
}
}
14. Considere a implementação do algoritmo SelectionSort dada por:
void selecao (int n, int v[]) {
int i, j, min, x;
for (i = 0; i < n-1; ++i) {
min = i;
for (j = i+1; j < n; ++j)
if (v[j] < v[min]) min = j;
x = v[i]; v[i] = v[min]; v[min] = x;
}
}
(a) Na função seleção, que acontece se trocarmos for ( i = 0 por for (i = 1)? Que acontece se trocarmos for (i = 0; i < n-1 por for ( i = 0; i < n?
O vetor será ordena apenas da posiç~
ao 1 para frente.
irá acessar área inválida de memória.
No segundo caso o algoritmo
(b) Na função seleção, troque a comparação v[j] < v[min] por v[j] <= v[min]. A nova função continua produzindo uma ordenando crescente de v[0..n-1]?
sim, porem realizará mais trocas da variável "min".
15. Escreva uma função que permute os elementos de um vetor inteiro v[0..n-1] de modo que eles
fiquem em ordem decrescente.
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
void selecao_decrescente (int n, int v[]) {
int i, j, max, x;
for (i = 0; i < n-1; ++i) {
max = i;
for (j = i+1; j < n; ++j)
if (v[j] > v[max]) max = j;
x = v[i]; v[i] = v[max]; v[max] = x;
}
}
16. Faça uma análise da complexidade do algoritmo Selection Sort. Evidencie os custos relacionados
a (1) Comparações e (2) Permutações, mostrando qual tem mais influência sobre o tempo de
execução.
comparaç~
oes = O(n2 )
trocas = O(n)
Assim, as comparaç~
oes tem maior influ^
encia sobre o tempo de execuç~
ao, pois é realizado
muito mais vezes do que a troca, mesmo a troca sendo uma operaç~
ao mais custosa de se
realizar se comparada a apenas uma comparaç~
ao.
17. Utilizando o algoritmo Heapsort
(a) Mostre, passo a passo, os estágios da ordenação do vetor [3, 19, 25, 24, 1, 8, 10, 7, 9, 12, 10].
1 - [3, 19, 25, 24, 1, 8, 10, 7, 9, 12, 10]
2 - [25, 24, 10, 19, 12, 8, 3, 7, 9, 1, 10]
3 - [24, 19, 10, 10, 12, 8, 3, 7, 9, 1, 25]
4 - [19, 12, 10, 10, 1, 8, 3, 7, 9, 24, 25]
5 - [12, 10, 10, 9, 1, 8, 3, 7, 19, 24, 25]
6 - [10, 9, 10, 7, 1, 8, 3, 12, 19, 24, 25]
7 - [10, 9, 8, 7, 1, 3, 10, 12, 19, 24, 25]
8 - [9, 7, 8, 3, 1, 10, 10, 12, 19, 24, 25]
9 - [8, 7, 1, 3, 9, 10, 10, 12, 19, 24, 25]
10 - [7, 3, 1, 8, 9, 10, 10, 12, 19, 24, 25]
11 - [3, 1, 7, 8, 9, 10, 10, 12, 19, 24, 25]
12 - [1, 3, 7, 8, 9, 10, 10, 12, 19, 24, 25]
(b) O que é um “heap”?
Heap é uma estrutura de dados organizada como árvore binária balanceada, seguindo
algumas regras.
(c) Quais são as operações básicas realizadas sobre um heap e qual o tempo para realização
destas operações?
Build_heap → O(n)
Heapify → O(lg(n))
LEFT → O(1)
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
RIGHT → O(1)
PARENT → O(1)
(d) Modifique o algoritmo Heapsort para realizar a ordenação de dados em ordem decrescente,
mas continue fazendo ordenação local.
Basta alterar a funç~
ao "Heapify"de forma a manter o menor elemento na raiz, ou
seja, construir um "min-Heap"
18. Discuta a seguinte implementação do algoritmo Heapsort:
void bottom_up_heapsort (int n, int v[])
{
int m, f, max, t;
constroi_heap (n, v);
for (m = n; m > 1; --m) {
max = v[1];
f = 2;
while (f <= m) {
if (f < m && v[f] < v[f+1]) ++f;
v[f/2] = v[f];
f *= 2;
}
f = f/2;
if (f < m) {
t = v[f], v[f] = v[m], v[m] = t;
while (f > 1 && v[f/2] < v[f]) {
t = v[f], v[f] = v[f/2], v[f/2] = t;
f = f/2;
}
}
v[m] = max;
}
}
void constroi_heap (int n, int v[])
{
int m, f, t;
for (m = 1; m < n; ++m) {
f = m+1;
while (f > 1 && v[f/2] < v[f]) {
t = v[f/2], v[f/2] = v[f], v[f] = t;
f = f/2;
}
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
}
}
19. Utilizando o algoritmo Merge Sort
(a) Mostre, passo a passo, os estágios da ordernação do vetor [3, 19, 25, 24, 1, 8, 10, 7, 9, 12, 10].
1
2
3
4
5
6
7
-
[3, 19, 25, 24, 1, 8, 10, 7, 9, 12, 10]
[3, 19, 1, 24, 25, 8, 10, 7, 9, 12, 10]
[1, 3, 19, 24, 25, 8, 10, 7, 9, 12, 10]
[1, 3, 19, 24, 25, 7, 8, 10, 9, 12, 10]
[1, 3, 19, 24, 25, 7, 8, 10, 9, 10, 12]
[1, 3, 19, 24, 25, 7, 8, 9, 10, 10, 12]
[1, 3, 7, 8, 9, 10, 10, 12, 19, 24, 25]
(b) Qual o desempenho assintótico do algoritmo?
O(nlog(n))
20. Considere a função abaixo:
void intercala1 (int p, int q, int r, int v[])
{
int i, j, k, *w;
w = malloc ((r-p) * sizeof (int));
i = p; j = q;
k = 0;
while (i < q && j < r) {
if (v[i] <= v[j]) w[k++] = v[i++];
else w[k++] = v[j++];
}
while (i < q) w[k++] = v[i++];
while (j < r) w[k++] = v[j++];
for (i = p; i < r; ++i) v[i] = w[i-p];
free (w);
}
(a) Analise e discuta a seguinte alternativa para a função intercala1 (detalhes de alocação e
liberação de memória foram omitidas):
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
i = p; j = q; k = 0;
while (i < q && j < r) {
if (v[i] <= v[j]) w[k++] = v[i++];
if (v[i] > v[j]) w[k++] = v[j++];
}
while (i < q) w[k++] = v[i++];
while (j < r) w[k++] = v[j++];
for (i = p; i < r; ++i) v[i] = w[i-p];
Esse algoritmo aumentará o número de operaç~
oes realizadas no laço while, pois ao
invés de se usar if, else, foram usado dois if’s o que implica em realizar uma
comparaç~
ao a mais por cada laço do while.
(b) Analise e discuta a seguinte alternativa para a função intercala1 (detalhes de alocação e
liberação de memória foram omitidas):
i = p; j = q; k = 0;
while (i < q && j < r) {
if (v[i] <= v[j]) w[k++] = v[i++];
else w[k++] = v[j++];
}
while (i < q) w[k++] = v[i++];
for (i = p; i < j; ++i) v[i] = w[i-p];
Esse algoritmo funcionará corretamente, pois caso o primeiro while seja terminado
pela condiç~
ao i < q, a parte direita do vetor a ser intercalado n~
ao será copiada
para o vetor auxiliar w, porém o for subsequente irá copiar para o vetor de resposta
os elementos do vetor w até a posiç~
ao j, pois o resto dos elementos já est~
ao no
vetor resposta, que é o vetor original. Com isso algumas operaç~
oes s~
ao economizadas
o que torna o algoritmo um pouco mais eficiente que o primeiro.
21. Critique a função de intercalação abaixo. (Observe que a função faz a intercalação “inloco”, ou
seja, não usa um vetor auxiliar). Ela está está correta? Quais as invariantes do while? Qual o
consumo de tempo?
int i, k, t;
i = p;
while (i < q && q < r) {
if (v[i] >= v[q]) {
t = v[q];
for (k = q - 1; k >= i; k--)
v[k+1] = v[k];
v[i] = t;
q++;
}
i++;
}
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
O algoritmo está correto. A invariante do while é que todo elemento com posiç~
ao menor
que i estará no seu local certo do vetor final. O consumo de tempo será O(n2 )
22. Discuta a seguinte implementação do algoritmo Mergesort:
void mergesort (int p, int r, int v[]) {
if (p < r) {
int q = (p + r) / 2;
mergesort (p, q, v);
mergesort (q, r, v);
intercala (p, q, r, v);
}
}
A implementaç~
ao está errada, por um leve detalhe, a segunda chamada recursiva deveria
ser mergesort(q + 1, r, v);
23. Qual a diferença entre a propriedade de uma árvore binária de pesquisa e a propriedade de um
heap?
Na árvore binária de busca a propriedade respeitada é que os filhos a esquerda sejam
menores que o pai e os filhos a direita sejam maiores que o pai. No Heap a única propriedade
requerida é que o pai seja maior que os filhos.
24. Considere o seguinte algoritmo de ordenação: dado um conjunto de valores a serem ordenados,
construa uma árvore binária de pesquisa e imprima os valores dos nodos durante um percorrimento da árvore em pré-ordem. Discuta o custo deste algoritmo para o pior e melhor caso? Como
ele se compara com os custos do Quicksort e do Merge Sort?
- No pior caso, a árvore binária de busca será uma lista encadeada, ou seja, os elementos
foram inseridos de forma ordenada e portanto o custo de inserç~
ao de cada elemento será
O(n), assim para construir a árvore no pior caso terá complexidade O(n2 ). Já no melhor
caso a árvore estará balanceada e para inserir um elemento o custo será de O(lg(n)),
assim para construir toda a árvore a complexidade será O(n ∗ lg(n)). Para percorrer
a árvore eu sempre vou precisar visitar os n nós da árvore ou seja, complexidade O(n),
dessa forma somando as complexidades temos:
- pior caso: O(n2 ) + O(n) = O(n2 )
- melhor caso: O(n ∗ lg(n)) + O(n) = O(n ∗ lg(n))
comparado com Merge Sort ele é menos efici^
ente, pois o merge Sort tem complexidade no
melhor e pior caso O(n∗lg(n)). Porém terá a mesma complexidade do Quick Sort, no pior
e no melhor caso.
25. Escreva uma função que imprima as chaves de uma árvore-B em ordem crescente.
void emOrdem (tpaginaB raiz) {
if(raiz==NULL)
return;
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
for(int i=0;i<raiz.n,i++){
emOrdem(raiz->pont[i]);
printf("%i",raiz->chv[i]);
}
emOrdem(raiz->pont[raiz.n]);
}
26. Escreva uma função que imprima as chaves de uma árvore-B em ordem decrescente.
void emOrdemDecrescente (tpaginaB raiz) {
if(raiz==NULL)
return;
for(int i=raiz.n; i>0 ,i--){
emOrdemDecrescente(raiz->pont[i]);
printf("%d",raiz->chv[i]);
}
emOrdemDecrescente (raiz->pont[0]);
}
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/