4) { while ($ads2 == $ads1) { $ads2 = rand(1, $slides); } } $ads3 = rand(1, $slides); if ($slides > 4) { while (($ads3 == $ads2) || ($ads3 == $ads1)) { $ads3 = rand(1, $slides); } } ?>
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;  
}
b) int func2(int n)  
{
int i, j, x, soma = 0;  
for (i = 0; i < n; i++)  
{
for (j = 0; j < n; j++)  
{
for (x = 0; x < n; x++)  
{
soma += n;  
}
}
}
return soma;  
}
c) void func3(int* A, int n)  
{
int i, j, aux;  
for( j = 2; j <= n; j++){  
aux = A[j];  
i = j - 1;  
while (i > 0 && A[i] > aux){  
A[i + 1] = A[i];  
i = i -1;  
}
A[i + 1] = aux;  
}
}
6) Dadas n variáveis booleanas, escreva um algoritmo que gere todas as combinações  
possíveis. Por exemplo, para três variáveis deverá ser gerado: 000 001 010 011 –  
1
00 101 110 111. Em seguida, análise a complexidade deste algoritmo.