Algoritmos

Algoritmos - Exercícios
1) O que significa dizer que uma função g(n) é O(f(n))? f(n) é o limite superior para g(n). Significa que g(n) é limitada superiormente por f(n). Uma função f (n) domina assintoticamente outra função g(n) se existem duas constantes positivas c e m tais que, para n ≥ m, temos |g(n)| ≤ c x |f(n)|.
2) O que significa dizer que um algoritmo executa em tempo proporcional a n?
Significa dizer que quanto maior o n, maior é o tempo de execução.
3) Explique a diferença entre O(1) e O(2).
Não existe diferença pois qualquer constante é desprezível em relação à O(1) e O(2).
4) Qual algoritmo é melhor: um algoritmo que requer n5 passos ou um que requer 2n passos?
5) Indique se as afirmativas a seguir são verdadeiras ou falsas e justifique sua resposta:
a) 2n+1=O(2n)
Verdadeiro, pois o valor de “1” na função é desprezível para o resultado geral.
b) 22n=O(2n)
Falso, pois o valor de “n” está dobrando, o que afeta diretamente o desempenho do algoritmo.
6) Suponha um algoritmo A e um algoritmo B com funções de complexidade tempo a(n)=n2-n+549 e b(n)=49n+49, respectivamente. Determine quais são os valores de n pertencentes ao conjunto dos números naturais para os quais A leva menos tempo para executar do que B.
Não existem valores de “n” pertencentes ao conjunto que satisfaça essa condição.
7) Qual é a ordem de complexidade das seguintes funções (utilize a notação O).
a) f(n) = n2 + 2
b) g(n) = 503
c) g(n) = 2 log n + n
d) g(n) = 10. 2n
e) f(n) = n log n + log n
8) Qual dessas funções possui a maior ordem de complexidade?
9) Arranje as seguintes expressões de acordo com a taxa de crescimento (da menor para a maior): 4n2, n!, log3n, 3n, 20n, 2, log2n.
10) Analise a complexidade dos seguintes trechos de códigos:
For