Bacharelao em Ciência da Computação – UFU
Disciplina – Análise de Algoritmos
Profa. Sandra de Amo
Exercício – AULA 3
Temas: Prova por indução, provas rigorosas de análise assintótica, Notações O, Ω, θ
Exercicio 1
Seja T(n) = número de passos do algoritmo recursivo Fib1(n) que calcula o n-ésimo
número de Fibonacci Fn
Fib1(n) =
1. If n = 0 retorna 0 e pára;
2. If n = 1 retorna 1 e pára;
3. retorna Fib1(n-1) + Fib1(n-2)
Deduzimos em sala de aula que: T(0) = 1; T(1) = 2 e T(n) = T(n-1) + T(n-2) + 3 se n ≥2
Mostre por indução em n que T(n) ≥ Fn para todo n ≥ 0
Solução:
Base da indução: n=0 e n=1
Para n=0
Por um lado: T(0) = 1
Por outro lado: F_0 = 0.
Logo: como 1 > 0 temos que T(0) > F_0
Para n=1
Por um lado: T(1) = 2
Por outro lado: F_1 = 1.
Logo: como 2 > 1 temos que T(1) > F_1
Hipótese de Indução: Suponha que a proposição T(i) ≥ F_i para todo i ≤ k. Mostremos que T(k+1) ≥
F_k+1, para k ≥ 1 (isto é, k+1 ≥ 2)
Para k+1 ≥ 2 temos: T(k+1) = T(k) + T(k-1) +3
Por hipótese de indução, podemos afirmar que : T(k) ≥ F_k e T(k-1) ≥ F_k-1
Por outro lado, temos que: F_k+1 = F_k + F_k-1.
Logo: T(k+1) = T(k) + T(k-1) + 3 ≥ F_k + F_k-1 + 3 = F_k+1 + 3 > F_k+1
Exercicio 3: Algoritmo de complexidade constante para calcular chão(n/2)
Input: Número n = array de n bits = A[1,...,n]
Output: chão(n/2) = array de n-1 bits
1. Elimina o último bit do array A.
Exercício 5:
Se x é par então x = 2k, para algum inteiro natural k
Logo chão(x/2) = chão (k) = k
Logo 2. chão(x/2) = 2.k = x
Se x é impar então x = 2k + 1 para algum inteiro natural k
Logo: chão(x/2) = chão ((2k + 1)/2) = chão(k + ½ ) = k.
Logo: 2chão(x/2) = 2k = x - 1
Exercício 7: Seja p(n) polinômio de grau k. Mostre que p(n) = O(nk).
Solução:
Por indução sobre k
Base da indução: k = 1
p(n) = a1n + a0 ≤ a1n + a0 n = (a1+ a0)n , para todo n ≥ 1
Logo, para n ≥ 1: p(n) ≤ cn, onde c = a1+ a0 , o que prova que p(n) = O(n)
Suponha a proposição válida para polinômios de grau k-1 e mostremos que é válida para polinômios de
grau k, onde k > 1
Seja p(n) um polinômio de grau k:
p(n) = aknk + ak-1 nk-1 + … + a1n + a0 ≤ aknk + ak-1 nk-1 + … + a1n + a0n (se n ≥ 1)
= aknk + ak-1 nk-1 + … + n(a1 + a0)
Colocando n em evidência temos:
p(n) ≤ n (aknk-1 + ak-1 nk-2 + … + (a1 + a0)) = n. q(n), onde q(n) = aknk-1 + ak-1 nk-2 + … + (a1 + a0) é um
polinômio de grau k-1.
Por hipótese de indução temos que q(n) = O(nk-1). Logo, pela definição, existe no e uma constante c tais que
para todo n ≥ n0, temos que q(n) ≤ c. nk-1.
Ora: p(n) ≤ nq(n) ≤ n c nk-1 = cnk, para todo n ≥ max(1, n0).
Portanto: p(n) = O(nk)
Exercicio 12: Mostre que an = O(n!), para todo número real positivo a.
Solução:
Vimos a idéia geral deste exercicio em sala de aula, para o caso de a=2, a=3, a=4,… Para a=2, mostramos
que 2n ≤ 2 n! para n ≥ 2. Para a=3, vimos que 3n ≤ (32/2) n!, para n ≥ 3. Para a = 4, mostramos que 4n ≤
(43/(3.2)) n!, para n ≥ 4
Podemos generalizar esta idéia para qualquer inteiro a:
an ≤ (a(a-1)/(a-1)!) n!, para n ≥ a
Para n ≥ a, temos:
n! (a(a-1)/(a-1)!) = (n n-1 n-2 … a+1 . a a-1 … 2 . 1) (a/(a-1). (a/a-2). (a/a-3) … (a/2) a ) =
(n n-1 n-2 … a+1 a a … a) >= a a …a a a … a = an
Para mostrar que an = O(n!), para qualquer real positivo a:
Seja a um real positivo e seja b um inteiro > a
Pelo que foi demonstrado anteriormente, temos que bn = O(n!). Logo existe c > 0 e n0 tal que para todo n ≥
n0
bn ≤ cn!
Logo an ≤ bn ≤ cn!
Portanto an = O(n!)