analise de algoritmos

Exercícios Cormen

3.1.1 – max(f(n) . g(n)) = θ(f(n) + g(n)) h(n) = max(f(n) , g(n)) h(n) =
Enquanto f(n) e g(n) não forem negativos f(n) 0 e g(n) 0 para todo h h0.
Para h h0, f(n) + g(n), temos que f(n) + g(n) h(n) 0 o que mostra que h(n) = max ( f(n), g(n) ) c2 (f(n) + g(n)) para todos 0s h h0 (com c2 = 1 na definição de θ)
Do mesmo jeito, para qualquer n, h(n) é maior que f(n) e g(n), que tem para todo n n0, 0 f(n) h(n) e 0 g(n) h(n)adicionando as duas desigualdades 0 f(n) + g(n) 2h(n), ou 0 h(n), o que mostra que h(n) = max(f(n), g(n)) c1(f(n) + g(n)) para todos os n n0 (com c1 = 112 na definição de θ).
3.1.2 - = θ, quero achar -> c1, c2, n0 > 0, sendo que 0 c1 c2 para todo n n0.

E |a|
Assim, quando n 2|a|
0
Quando b>0, a desigualdade continua quanto tem potência de b.
0
0
Assim, c1 = , c2 = e n0 = 2|a|
3.1.3 –
Quando o tempo de execução é t(n). t(n) O(n²) significa que t(n) f(n) para alguma função f(n) no conjunto O(n²).
Esta declaração é válida para qualquer tempo de execução t(n), uma vez que a função g(n) = 0 para todo n é O(n²) e o tempo de execução continua.
3.1.4 –
Para mostrar que temos que encontrar constantes c, n0 >0 tal que 0 para todo n n0. Uma vez que para todo n, que pode satisfazer c = 2 e n0 =1.
Para mostrar que 0 para todo n n0, então . Mas não é constante quando maior que , portanto ocorre uma contradição.
3.1.5 –
Para duas funções quaisquer f(n) e g(n), temos f(n) = θ(g(n)) se e somente se f(n) = Og(n) e f(n) = Ω(g(n))

Esse teorema é verdadeiro.
3.1.8 –
Ω(g(n,m))= { f (n,m) : constantes positivas c, n0 e m0 de tal forma que 0 c g(n,m) f (n,m) para todos n n0 e m m0} θ(g(n,m))= { f (n,m) : constantes positicas c1,c2,n0 e m0 de tal forma que 0 c1 g(n,m) f (n,m) c2 g(n,m) para todos n n0 e m m0}
• Prove: se f(n) = θ(g(n)),