Analise e complexidade de algoritmos

Páginas: 2 (337 palavras) Publicado: 29 de outubro de 2012
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.
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Análise e complexidade de algoritmos
  • analise e complexidade de algoritmos
  • Analise e complexidade de algoritmos
  • Analise e complexidade de algoritmos
  • ANALISE E COMPLEXIDADE DE ALGORITMOS
  • Análise de Complexidade de Algoritmos
  • ATPS Analise e Complexidade de Algoritmos
  • Atps análise e complexidade de algoritmos

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!