trabalhos

1- Coloque em ordem crescente as complexidades: 2n, n!, n ^5, n(logn), log(n) e n.
2- Obtenha o valor da notação O das seguintes expressões:
a) 5 n5 + n2
b) 10 log(n) + 9n
c) n3 + n log(n)
d) 5n
3- Mostre que as igualdades estão corretas:
a) 5n² - 6n = O(n²)
b) n! = O (n^n)
c) 2n²2^n + n(log(n)) = O(n²2^n)
4- Um algoritmo processa n elementos. Se n é 4096, o tempo de execução é de 512ms. Se o tempo de execução é de 1024ms, n será 16384. Qual é a complexidade de tempo da notação O?
5- Calcule a complexidade de tempo nos pseudocódigos:
a) Algoritmo1(int n)
{
For k=1 to n do Print(k);
}
b) Algoritmo2 (int m, n, k)
{
For i=1 to n do For j=1 to m do For 1=1 to k do Print(i, j, k)
}
6- Suponha que a complexidade de um algoritmo seja:
5n(log(n)). Um passo de algoritmo leva 1ms(10^-9s). Quanto tempo esse algoritmo levará para processar um entrada de 1000 elementos?
7- Mostre que as igualdades estão incorretas:
a) 10n² + 9 = O(n)
b) N² log(n) = O(n)
c) 4n³ + n² = O(n²)

RESPOSTAS
1 – log(n), n, n(logn), n!, n^5, 2^n.
2 -
a) 5n^5 , n ^2, =>n^5 + n^2 => O(n^5)
b) 10log(n)+9n => log(n)+n => O(n)
c) n^3 + n log (n )=> O(n^3)
d) 5n=>O(n)
3 – a) correto
b) correto
c) incorreto

4 –
5 –
6 –
7 – a) 10n^2+9=O(n)=> n^2 ≠ O(n)
b) N^2.log(n) = O(n) => N^2 ≠ O(n)
c) 4n^3 + n^2 = O(n^2) => n^3 + n^2 = O(n^2) => n^3 ≠ O(n^2)