Trabalho Prático 01 - Praticando a Análise de Algoritmos

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Trabalho Prático 01
Praticando a Análise de Algoritmos
Objetivo: Exercitar a análise analítica de algoritmos e estruturas de dados simples.
Modalidade de desenvolvimento: equipe (até 2 componentes)
Modalidade da apresentação: envio de arquivo .odt1 para flaviacoelho@ufersa.edu.br
Data de entrega: até Domingo, 14/08/2016
Artefatos de entrega: soluções das questões, a seguir.
1. Considere dois computadores que executam 107 (C1) e 109 (C2) operações por segundo e um
algoritmo de ordenação cujo tempo de execução é 50nlog10n. Qual é o computador mais
indicado (com menor tempo de execução) para ordenar 106 elementos? Justifique
(apresentando os cálculos).
2. Prove que g(n) = (n + 1)2 é O(n2).
3. Há diferença entre O(1) e O(2)? Justifique. 
4. É verdade que 2nn + 2nnlgn é O(2n)? Justifique.
5. Caracterize o melhor, pior e caso médio para o algoritmo a seguir, utilizando a notação
assintótica (apresente todos os cálculos efetuados).
algoritmo somaPrefixos
Entrada: Um arranjo A que armazena n  1 elementos.
Saída: Soma dos prefixos de A.
s   0←
para i   0 ← até n­1 faça
s   s + A[0]←
para j   1 ← até i faça
s   s + A[j]←
retorna s
1 Requerida para viabilizar o registro de alterações e comentários via LibreOffice Writer – vide modelo. 
1
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
6. É verdadeira a seguinte afirmação? Justifique.
7. Calcule a complexidade de melhor e pior casos para o seguinte trecho de programa.
if (x == y){
for(i = 0; i < n; i++){
for(j = 0; j <= n; j++){
//instruções
}
}
for(i = 0; i < n; i++){
//instruções
}
}
else{
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
for(k = 0; k < n; k++)
//instruções
}
8. Calcule a T(n) e determine a complexidade assintótica para o seguinte código.
9. Joãozinho tem n reais. Todo dia, ele compra exatamente 1 chocolate (2 reais) ou 1 brigadeiro
(1 real) ou 1 sorvete (2 reais). Determine a relação de recorrência que fornece o número de
possíveis modos de gastar n reais, sendo n ≥ 3.
10. Determine a ordem de complexidade das relações a seguir.
a. T(n) = T(n/2) + 1, T(1) = 1
b. T(n) = 2T(n/2) + (n – 1), T(1) = 1
2
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
c. T(n) = 2T(n – 1) + 1, T(1) = 1
d. T(n) = T(n – 1) + (n – 1), T(1) = 0
3
	Trabalho Prático 01