Ordenacao

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ção g(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 tempo proporcional 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 do algoritmo.

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(max f(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