Analise e complexidade de algoritmos

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (337 palavras )
  • Download(s) : 0
  • Publicado : 29 de outubro de 2012
Ler documento completo
Amostra do texto
Analise e complexidade de algoritmos

5) O que significa dizer que uma função g(n) é O(f(n))?
Uma função f (n) domina assintoticamente outra função g(n) se existem duasconstantes positivas c e m tais que, para n ≥ m, temos |g(n)| ≤ c x |f(n)|.

6) Indique se as afirmativas a seguir são verdadeiras ou falsas e justifique a sua resposta:a. 2n+1 = O(2n).
b. 22n = O(2n).
c. É melhor um algoritmo que requer 2n passos do que um que requer 10n5 passos.
d. f(n) = O(u(n)) e g(n) = O(v(n)) => f(n) + g(n) =O(u(n) + v(n))
e. f(n) = O(u(n)) e g(n) = O(v(n)) => f(n) - g(n) = O(u(n) - v(n))

A=Verdadeira
B=Verdadeira
C=Verdadeiro, o melhor é o 2n; porque quanto maior o numeroque multiplica o “n” maior o tempo de execução do programa.
D= Verdadeira
E=Falsa. se f(n) – g(n) = O(u(n)) – O(v(n)) = O(u(n))+(-1)O(v(n)); como -1 é uma constante, elapode ser desconsiderada, de acordo com as propriedades da notação O.

7) Suponha um algoritmo A e um algoritmo B com funções de complexidade de tempo a(n) = n2 – n +549 eb(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 queB.

Não existem valores de “n” que satisfaça essa condição.

8) Considere que você tenha um problema para resolver e duas opções de algoritmos. O primeiro algoritmo équadrático tanto no pior caso quanto no melhor caso. Já o segundo algoritmo, é linear no melhor caso e cúbico no pior caso. Considerando que o melhor caso ocorre 90% dasvezes que você executa o programa enquanto o pior caso ocorre apenas 10% das vezes, qual algoritmo você escolheria? Justifique a sua resposta em função do tamanho da entrada.
tracking img