IPRJ – PROJETO E ANÁLISE DE ALGORITMOS
LISTA DE EXERCÍCIOS 01
1) Supondo que estamos comparando duas implementações de um algoritmo em um
mesmo computador. Para entradas de tamanho n, a implementação A é executada em
2
8
n etapas, enquanto a implementação B é executada em 64n Iog n etapas. Para que
valores de n a implementação A supera a implementação B?
2
2
3
) As funções log n e log n possuem a mesma ordem de complexidade? Justifique sua
resposta.
3
) Dada a função T(n) = 64n + n log n + 128n, responda verdadeiro ou falso para às
afirmações abaixo.
a) T(n) = O(n log n)
b) T(n) = Ω(log n)
3
c) T(n) = Θ(n )
3
d) T(n) = O(n )
e) T(n) ≠ Ω(n)
f) T(n) = O(1)
g) T(n) = Ω(1)
h) T(n) ≠ O(n!)
i) T(n) = Θ(n log n)
n
j) T(n) = O(2 )
4
5
) Escreva um algoritmo que, dado um conjunto S de n inteiros e outro inteiro x,
determina se existe ou não dois elementos de S cuja soma é exatamente x. Em
seguida, análise a complexidade deste algoritmo.
) Análise a complexidade dos algoritmos abaixo:
a) float func1(int n, float A[], float x)
{
int k;
float y = 0.0;
for (k = n; k >= 0; k--)
{
y = A[k] + y * x;
}
return y;
}
