Ordenacao

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (326 palavras )
  • Download(s) : 0
  • Publicado : 27 de novembro de 2011
Ler documento completo
Amostra do texto
Ordenação
Em geral, entende-se a atividade de ordenação como sendo um processo de rearranjo de um certo conjunto de objetos de acordo com um critério (ordem)específico. O objetivo da ordenação é facilitar a localização dos membros de um conjunto de dados.

Exercícios Propostos

1. O que significa dizer que uma funçãog(n) é O(f(n))?
f(n) é o limite superior para g(n). Significa que g(n) é limitada superiormente por f(n).

O que significa dizer que um algoritmo executa em tempoproporcional a n?
Significa dizer que quanto maior o n, maior é o tempo de execução.
2. Explique a diferença entre O(1) e O(2)?
Nenhuma, pois qualquer constanteé desprezível.

3. 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 doalgoritmo.

c) f(n) = O(u(n)) e g(n) = O(v(n)) => f(n)+g(n) = O(u(n)+v(n))
Falso, pois a soma de “f(n)+g(n)” corresponde ao maior valor entre esses dois. O(maxf(n), g(n))

4. Qual o comportamento assintótico das funções abaixo:
d) f (n) = n2+2n+10
f (n) = n2+2n+10
f (n) = O(2n)

e) f (n) = (n log(n) +n) / n
f (n) = (n log(n) + n) / n
f (n) = n log(n) / n
f (n) = O(log(n)) (?)

f) f (n) = n3/2 + n!/n
f (n) = n3/2 + n!/n
f (n) = n3/2 + n.(n-1)!/n
f(n) = n3/2 + n.(n-1)!/n
f (n) = n3/2 + (n-1)!
f (n) = n3 + (n-1)!
f (n) = O(n!)

g) f (n) = (n3/n2)log(n)
f (n) = (n3/n2)log(n)
f (n) = O(n log(n))
tracking img