bc1435 – Recorrências e soluções assintóticas

Em muitos casos, como em algoritmos recursivos e divisão-e-conquista,  a complexidade de um algoritmo é dada por uma equação de recorrência, para a qual devemos determinar a sua ordem de grandeza. Veremos algumas estratégias para fazer comparações assintóticas quando uma das funções é dada por uma equação de recorrência.

— Definição recursiva de funções —

Sejam {n_0\in{\mathbb N}} e {A = \{n\in{\mathbb N}\colon n \geq n_0\}}. Podemos definir uma função com domínio {A} usando o princípio da indução finita da seguinte maneira:

  • (base) especificamos o valor de {f(n_0)},
  • (passo) especificamos para todo {n \geq n_0} como determinar {f(n+1)} a partir de todos ou alguns elementos de {\{f(n_0), f(n_0+1),\dots, f(n-1),f(n)\}.}

Se {X\subseteq A} é o conjunto dos pontos para os quais {f} está definida então pelo Princípio da Indução ( 3ª versão), {X=A.}


Exemplos

  • (1) {f(0)=3} e {\mathrm{para~todo~} n\geq 0,~f(n+1)=2f(n)+3}.
  • (2) {\mathrm{fat}(0)=1} e {\mathrm{para~todo~} n\geq 0,~\mathrm{fat}(n+1)=(n+1)\cdot\mathrm{fat}(n)}.
  • (3) {S(0)=0} e {\mathrm{para~todo~} n\geq 0,~S(n+1)=S(n)+g(n+1)}, em que {g} é a função, para a,r\in\mathbb{R} fixos

    \displaystyle \begin{array}{rcl} g(0) &=& a \\ g(n) &=& g(n-1) + r \qquad(n>0)\end{array}

  • (4) {p(0)=1} e {\mathrm{para~todo~} n\geq 0, ~ p(n+1)=ap(n)}, em que {a\in {\mathbb R}\setminus\{0\}}.
  • (5) {b(1)=1} e {\mathrm{para~todo~} n\geq 1, ~ b(n+1)=b\left( \left\lfloor \frac{n+1}2 \right\rfloor \right) +1}.
  • (6) {H(1)=1} e {\mathrm{para~todo~} n\geq 1, ~ H(n+1) = H (n) + \frac 1{n+1}}.

Notemos que nos exemplos acima a função {\mathrm{fat}} é {\mathrm{fat}(n)=n!}, a função {p} é a função {p(n)= a^n}. O que podemos dizer a respeito das outras funções?

A função {S} é {S(n) = \sum_{i=1}^n g(i)} e a função g é uma progressão aritmética de termo inicial a e razão r, temos g(n) = a+nr e S(n) é a soma dos n primeiros termos da P.A., ou seja S(n) = (a+rn/2)(n+1).

Vamos provar que {f(n) = 3(2^{n+1}-1)} e que {b(n) = \lfloor \log_2 (n) \rfloor + 1}.

Seja {g\colon {\mathbb N} \rightarrow {\mathbb N}} definida por {g(n) = 3(2^{n+1}-1)}. Vamos provar por indução que para {f} definida indutivamente no exemplo (1) acima vale {\mathrm{para~todo~} n, ~f(n)=g(n)}.

Se {n = 0} então {f(0)=3} e {g(0) = 3(2-1) =3}, portanto {f(0) = g(0)}.

Agora, vamos provar que para todo {n\in {\mathbb N}}, se {f(n)=g(n)} então {f(n+1) = g(n+1)}. Seja {n} um natural e assuma que {f(n) = g(n)}. Então

\displaystyle \begin{array}{rcl} f(n+1) &=& 2f(n) +3 \\ &=& 2g(n) +3 \\ &=& 2(3(2^{n+1}-1)) +3 \\ &=& 3(2^{n+2}-1)\\ &=& g(n+1). \end{array}
a primeira igualdade é a definição de {f}, na segunda foi usada a hipótese da indução, nas terceira e na última a definição de {g}. Portanto,  {\mathrm{para~todo~} n, ~f(n)=g(n)}.

No caso do exemplo (5) acima, seja {\ell\colon {\mathbb N} \rightarrow {\mathbb N}} definida por {\ell(n) = \lfloor \log_2(n)\rfloor +1 }. Vamos provar por indução que para {b} definida indutivamente no exemplo acima vale {b(n)=\ell(n)} para todo n\geq 1.

Se {n = 1} então {b(1)=1} e {\ell(1) = \lfloor \log_2(1) \rfloor +1 = 1}, portanto {b(1) = \ell(1)}.
Agora, vamos provar que para todo {n\in {\mathbb N}}, se {\mathrm{para~todo~} k\in \{1,\dots,n\}, ~ b(k) = \ell(k)} então {b(n+1) = \ell(n+1)}. Seja {n} um natural e assuma que {\mathrm{para~todo~} k\in \{1,\dots,n\}, ~b(k) = \ell(k)}. Então
\displaystyle \begin{array}{rcl} b(n+1) &=& \displaystyle b \left( \left\lfloor \frac{n+1}2 \right\rfloor \right) +1 \\ &=&\;\;\displaystyle \ell\left(\left\lfloor \frac{n+1}2 \right\rfloor \right) +1\\ &=& \displaystyle \left\lfloor \log_2\left(\left\lfloor \frac{n+1}2 \right\rfloor\right)\right\rfloor +2 \\ &=& \;\;\displaystyle \left\lfloor \log_2\left( \frac{n+1}2 \right)\right\rfloor +2 \\ &=& \displaystyle \lfloor \log_2( {n+1} ) - 1\rfloor +2 \\ &=& \displaystyle \lfloor \log_2( {n+1} )\rfloor -1+2 \\ &=& \displaystyle \lfloor \log_2(n+1)\rfloor +1\\ &=& \ell(n+1). \end{array}
a primeira igualdade é a definição de {b}, a segunda hipótese de indução, a terceira definição de {\ell}, a quarta igualdade decorre do item 12 das Propriedades da função chão, a sexta igualdade segue do item 11 das Propriedades da função chão, e na última a definição de {\ell}.

Portanto, pelo Princípio da Indução Finita  {\mathrm{para~todo~} n\geq 1, ~b(n)=\ell(n)}.


Agora, o que podemos dizer da função {H} do exemplo (6)? Podemos dizer muita coisa, menos uma fórmula aritmética simples para computar {H(n)}, que é conhecido como o {n}-ésimo número harmônico.

— Soluções assintóticas —

Vimos que {f} dada por {f(0)=3} e {f(n+1)=2f(n)+3}, se {n\geq 0}, é dada por {f(n) = 3(2^{n+1}-1)}. Isso pode ser descoberto iterando (desenrolando) a definição indutiva. Assuma que {n} é grande

\displaystyle \begin{array}{rcl} f(n) &=& 2f(n-1)+3 \\ &=& 2\big(2f(n-2)+3 \big)+3 \\ &=& 2^2f(n-2) + 2\cdot 3 +3\\ &=& 2^2\big( 2f(n-3)+3\big) + 2\cdot 3 +3 \\ &=& 2^3 f(n-3) + 2^2 \cdot 3 + 2\cdot 3 +3 \\ &=& 2^3\big( 2f(n-4)+3\big) + 2^2 \cdot 3 + 2\cdot 3 +3 2^4f(n-4) + 2^3\cdot 3 + 2^2 \cdot 3 + 2\cdot 3 +3 \\ &\vdots& \cdots \\ &=& 2^if(n-i) +2^{i-1}\cdot 3+\cdots + 2^3\cdot 3 + 2^2 \cdot 3 + 2\cdot 3 +3 \\ \end{array}

a iteração termina quando {i=n} e temos {f(n) = 2^nf(0)+ 2^{n-1} \cdot 3 + \cdots + + 2^3\cdot 3 + 2^2 \cdot 3 + 2\cdot 3 +3}, ou seja

\displaystyle f(n) = \sum_{i=0}^n 2^i\cdot 3 = 3(2^{n+1}-1).

Resta provar por indução que {f(n) =3(2^{n+1}-1)}, o que já fizemos acima.

Da mesma forma, iterando {b(1)=1}, {b(n)= b(\lfloor (n)/2 \rfloor ) +1}, usando o item 12 das Propriedades de teto e chão temos

\displaystyle \begin{array}{rcl} b(n) &=& b\left(\left\lfloor \frac n2 \right\rfloor\right) + 1\\ &=& \left( b\left( \left\lfloor \frac{\left\lfloor \frac n2 \right\rfloor}{2} \right\rfloor \right) + 1 \right)+1 \\ &=& b\left( \left\lfloor \frac{n}{2^2} \right\rfloor \right) + 2 \\ &=& \left( b\left( \left\lfloor \frac{\left\lfloor \frac n{2^2} \right\rfloor}{2} \right\rfloor \right) + 1 \right)+2 \\ &=& b\left( \left\lfloor \frac{n}{2^3} \right\rfloor \right) + 3 \\ &=& \left( b\left( \left\lfloor \frac{\left\lfloor \frac n{2^3} \right\rfloor}{2} \right\rfloor \right) + 1 \right)+3 \\ &=& b\left( \left\lfloor \frac{n}{2^4} \right\rfloor \right) + 4 \\ &\vdots& \cdots \\ &=& b\left( \left\lfloor \frac{n}{2^i} \right\rfloor \right) + i \end{array}

e, novamente, usando as Propriedades da função chão determinamos i

\displaystyle \begin{array}{rcl} \left\lfloor \frac n{2^i} \right\rfloor = 1 \Leftrightarrow 1 \leq \frac n{2^i} < 2 \Leftrightarrow i \leq \log_2 n < i+1 \Leftrightarrow i = \lfloor \log_2 n \rfloor \end{array}

portanto, após {\lfloor \log_2 n \rfloor} iterações {b(n) = b(1) + \lfloor \log_2 n \rfloor = 1+ \lfloor \log_2 n \rfloor}. Resta provar por indução que {b(n) = 1+ \lfloor \log_2 n \rfloor}, o que já fizemos acima.

1ª estratégia pra resolver uma recorrência: desenrolar a recorrência pra ter um “chute” para uma solução; provar que o chute está correto usando indução.

Essa estratégia nem sempre funciona, ou as vezes é muito difícil chegar em algum lugar, por exemplo, tente o mesmo com a seguinte função T definida por

\displaystyle \begin{array}{rcl} T(1) &=& 1,\\ T(n) &=& T \left(\left\lceil \frac n2 \right\rceil \right) + T \left(\left\lfloor \frac n2 \right\rfloor \right) + n ~\textrm{ se } ~n>1. \end{array} \ \ \ \ \ \ (1)

Ao invés de procurarmos por uma solução da equação de recorrência podemos tentar determinar a ordem de grandeza da função.

Para provar que T(n) = O(g(n)) usando indução devemos determinar  as constantes c,~n_0 > 0 tais que para n\geq n_0

\displaystyle T(n) \leq c f(n)

para alguma função f tal que f(n)=O(g(n)).

Por exemplo, vamos provar que para a função definida em (1) acima, vale {T(n) = O(n^2)}. Para tal, vamos provar por indução em {n} que, para algum par de constantes {c,n_0>0}, vale que

\displaystyle T(n) \leq c n^2 ~\mathrm{para~todo~} n\geq n_0.

Tomemos {c=1} e {n_0=4}.

Para a base da indução, deixamos a cargo do leitor verificar que vale T(j)\leq cj^2 para todo 4\leq j\leq 8. Seja {n>8} um inteiro e assuma que para todo {k\in \{8,...,n-1\}}, {T(k) \leq c k^2}. Vamos provar que {T(n) \leq c n^2}. Por definição {T(n) = T \left(\left\lceil \frac n2 \right\rceil \right) + T \left(\left\lfloor \frac n2 \right\rfloor \right) + n } e usando a hipótese da indução

\displaystyle \begin{array}{rcl} T(n) & \leq & \displaystyle c \left\lceil \frac n2 \right\rceil^2 + c \left\lfloor \frac n2 \right\rfloor^2 + n \\ & \leq &\displaystyle c \left( \frac n2 +1 \right)^2 + c \left( \frac n2 \right)^2 + n \\ & =&\displaystyle \frac c2 n^2 + (c+1)n +c\end{array}

portanto, {T(n) \leq cn^2} para todo {n\geq 4}.

Essa solução está superestimada, de fato é possível provar uma solução justa ou seja, uma solução que limita assintoticamente superiormente e inferiormente a função {T(n)}. Abaixo vamos provar que {T(n) = \Theta(n\log_2 n)}.

Primeiro, para tentar acertar a função que limita justamente T(n) vamos desenrolar a recorrência para n potência de 2. Nesse domínio a recorrência fica

\displaystyle T(n) = 2T\left(\frac n2\right) +n

portanto, fazendo n=2^k ficamos com

\displaystyle \begin{array}{rcl} T(2^k) &=& \displaystyle 2T\left(2^{k-1}\right) +2^k \\ & =&\displaystyle 2^2T\left(2^{k-2}\right) +2^k+2^k \\ &=&\displaystyle 2^3T\left(2^{k-3}\right) +2^k+2^k+2^k \\ &\dots &\\ & =&\displaystyle 2^iT\left(2^{k-i}\right) +i2^k \end{array}

e quando i=k ficamos com T(2^k)=2^{k}T\left(1\right) +k2^k e como n=2^k, resolvendo para k, k=\log_2 n, portanto

\displaystyle T(n) = n\log_2n + n \text{, para }n\text{ pot\^encia de } 2.

Agora, vamos provar que {T(n) \leq c ( n \lceil \log_2 n\rceil +n)} para algum c e todo n suficientemente grande.

Como n \lceil \log_2 n\rceil +n = O(\max\{n\log_2n,n\}) = O(n\log_2 n), feito isso teremos T(n) = O(n\log_2 n).

Para tal, tomemos {c=1} e {n_0=1}.

Para {n=1} temos {T(1)=1} e {c 1 \lceil \log_2(1)\rceil +1=1} e para {n=2} temos {T(2)=3} e {c 2 \lceil \log_2(2)\rceil +2=4}, portanto, {T(n) \leq c n \lceil \log_2(n)\rceil+cn} nesses casos.

Seja {n>2} inteiro e assumamos que

\displaystyle T(k) \leq c (k \lceil \log_2(k)\rceil +k)~\mathrm{para~todo~natural~} k\leq n-1.

Por definição

\displaystyle T(n) = T \left(\left\lceil \frac n2 \right\rceil \right) + T \left(\left\lfloor \frac n2 \right\rfloor \right) + n

e por hipótese

\displaystyle T(n) \leq c \left\lceil \frac n2 \right\rceil \left\lceil \log_2 \left\lceil \frac n2 \right\rceil \right\rceil + c \left\lfloor \frac n2 \right\rfloor \left\lceil \log_2 \left\lfloor \frac n2 \right\rfloor \right\rceil + cn +n

ainda, pelo item 6 de  Propriedades da função teto 

\displaystyle \left\lceil \log_2 \left\lceil \frac n2 \right\rceil \right\rceil = \left\lceil \log_2 \frac n2 \right\rceil

e como {\lfloor x \rfloor \leq x} e {\log_2} é crescente

\displaystyle \left\lceil \log_2 \left\lfloor \frac n2 \right\rfloor\right\rceil \leq \left\lceil \log_2 \frac n2 \right\rceil

portanto

\displaystyle \begin{array}{rcl} T(n) &\leq& c \left\lceil \frac n2 \right\rceil \left\lceil \log_2 \left( \frac n2 \right)\right\rceil + c \left\lfloor \frac n2 \right\rfloor \left\lceil \log_2 \left( \frac n2 \right)\right\rceil +cn +n\\ & = & c \left( \left\lceil \frac n2 \right\rceil + \left\lfloor \frac n2 \right\rfloor \right) \left\lceil \log_2 \left( \frac n2 \right)\right\rceil +cn +n\\ & = & c n \left\lceil \log_2 \left( (n) -1 \right)\right\rceil +cn +n\\ & = & \displaystyle c n \left\lceil \log_2 n \right\rceil +n\\ & = & c (n \left\lceil \log_2 n\right\rceil+n) . \end{array}

Com isso provamos que {T(n) = O ( n \lceil \log_2(n) \rceil) =O ( n \log_2(n) ) }.

Agora, de modo análogo, podemos provar que {T(n) \geq a( n \lfloor\log_2(n)\rfloor +n)} para alguma constante a>0 e todo n suficientemente grande. Com isso teremos que {T(n) = \Theta(n\log_2 n)}.

Notemos que de {T(n) = \Omega ( n \log_2(n))} deduzimos que não vale que {T(n) = O(n)}, entretanto podemos “provar” essa última comparação assintótica.

Exercício 1 Onde está o erro da seguinte prova?

Vamos provar que existem {c,n_0>0} tais que {T(n) \leq cn} para todo {n\geq n_0}. Tomemos {c=1/2} e {n_0=1}.

Para {n=1,2} a desigualdade vale (verifique). Seja {n>2} inteiro e assumamos que para todo {k\in [n_0..n-1]}, {T(k) \leq c k}. Vamos mostrar que {T(n) \leq cn}.

\displaystyle \begin{array}{rcl} T(n) &=& T \left(\left\lceil \frac n2 \right\rceil \right) + T \left(\left\lfloor \frac n2 \right\rfloor \right) + n \\ & \leq & c \left\lceil \frac n2 \right\rceil + c \left\lfloor \frac n2 \right\rfloor + n\\ &=& (c+1) n \end{array}

e como {c} é constante, também {c+2} é constante, portanto {T(n) = O(n)}.

Exercício 2 Para o número harmônico, mostre que H_n = \Theta (\log n).

2ª estratégia pra resolver uma recorrência: desenrolar a recorrência para um domínio num subconjunto (infinito) de \mathbb N pra ter um “chute” para uma solução; provar que o chute está correto usando indução.

Vamos usar a mesma técnica para mostrar que {b(1)=1}, {b(n)= b(\lfloor n/2 \rfloor ) +1} tem solução assintótica {b(n) = \Theta (\log_2 n)} (claramente, essa prova é desnecessária pois sabemos que {b(n) = \lfloor \log_2 n \rfloor +1} e é fácil provar que {\lfloor \log_2 n \rfloor +1 = \Theta (\log_2 n)}, a idéia é dar mais um exemplo de demonstração de solução assintótica).

Exercício 3 Desenrole a recorrência para n potência de 2. Mostre que nesse caso b(n) = \log_2 n + 1 para n potência de 2.

Primeiro, vamos mostrar que {b(n) = O(\lfloor \log_2 n \rfloor)}.

Vamos mostrar que para {c=3} e {n_0 = 2}, {b(n) \leq c \lfloor \log_2 n \rfloor} para todo {n \geq n_0}.

Para {n=2,3} temos {b(2) = b(3) = 2} e { c \lfloor \log_2 2 \rfloor = c \lfloor \log_2 3 \rfloor = c}, portanto, {b(n) \leq c \lfloor \log_2 n \rfloor} nesses casos. Seja {n>3} e assuma que para todo {k\in \{n_0,\dots,n-1\}}, {b(k) \leq c \lfloor \log_2 k \rfloor}. Então

\displaystyle \begin{array}{rcl} b(n) &=& b(\lfloor n/2 \rfloor) +1 \\ & \leq & c \lfloor \log_2 \lfloor n/2 \rfloor \rfloor +1\\ & = & c \lfloor \log_2 ( n/2) \rfloor +1\\ & = & c \lfloor \log_2(n) -\log_2(2) \rfloor +1\\ & = & c \lfloor \log_2(n) \rfloor -1 +1\\ & = & c \lfloor \log_2(n) \rfloor \end{array}

portanto {b(n) \leq c \lfloor \log_2 n \rfloor} para todo {n \geq n_0}, logo, por definição {b(n) = O(\lfloor \log_2 n \rfloor)}. Como {\lfloor \log_2 n \rfloor = O(\log_2 n )}, temos {b(n) = O(\log_2 n )}.

Agora, vamos mostrar que {b(n) = \Omega (\lfloor \log_2 n \rfloor)}.

Vamos mostrar que para {c=1} e {n_0 = 2}, {b(n) \geq c \lfloor \log_2 n \rfloor} para todo {n \geq n_0}.

Para {n=2,3} temos {b(2) = b(3) = 2} e { c \lfloor \log_2 2 \rfloor = c \lfloor \log_2 3 \rfloor = c}, portanto, {b(n) \geq c \lfloor \log_2 n \rfloor} nesses casos. Seja {n>3} e assuma que para todo {k\in \{n_0,\dots,n-1\}}, {b(k) \geq c \lfloor \log_2 k \rfloor}. Então

\displaystyle \begin{array}{rcl} b(n) &=& b(\lfloor n/2 \rfloor) +1 \\ & \geq & c \lfloor \log_2 \lfloor n/2 \rfloor \rfloor +1\\ & = & c \lfloor \log_2 ( n/2) \rfloor +1\\ & = & c \lfloor \log_2(n) -\log_2(2) \rfloor +1\\ & = & c \lfloor \log_2(n) \rfloor -1 +1\\ & = & c \lfloor \log_2(n) \rfloor \end{array}

portanto {b(n) \geq c \lfloor \log_2 n \rfloor} para todo {n \geq n_0}, logo, por definição {b(n) = \Omega (\lfloor \log_2 n \rfloor)}. Como {\lfloor \log_2 n \rfloor = \Omega (\log_2 n )}, concluímos que {b(n) = \Omega (\log_2 n )}.

Exercício 4 Troque as condições iniciais das recorrências acima por T(1)=a e b(1)=a onde a>0 é uma constante qualquer. Determine soluções assintóticas para essas novas recorrências. O valor inicial de um recorrência afeta sua ordem de grandeza?

Exercício 5 Verifique que I(n) =n\log_2 n+n satisfaz a recorrência I(1)=1 e I(n) = 2I(\lfloor n/2 \rfloor) +n, para n>1, quando n é potência de 2.

Assumamos que I\colon \mathbb N^*\to\mathbb R acima é uma função (assintoticamente) crescente e consideremos n qualquer (suficientemente grande) que não seja potência de 2 e tomemos k\in\mathbb N^* tal que

\displaystyle 2^{k-1} < n < 2^k

que significa que k -1 < \log_2 n < k e como a função I é crescente

\displaystyle I(2^{k-1}) < I(n) < I(2^k)

portanto

\displaystyle I(n) < I(2^k) = 2^k k+2^k < 2n (\log_2(n)+1) +2n = 2n \log_2(n) + 4n

donde concluímos que I(n) \leq 6n\log_2(n) se n\geq 2 e, também,

\displaystyle I(n) > I(2^{k-1}) = 2^{k-1} (k-1) + 2^{k-1} > \frac n2 (\log_2(n)-1) +\frac n2 = \frac 12 n \log_2(n)

e como as duas desigualdades deduzidas também vale para n potência de 2 temos

\displaystyle \frac 12 n \log_2(n) < I(n) < 6n\log_2(n) \text{ para todo }n\geq 2

ou seja I(n) = \Theta (n\log_2 n).

3ª estratégia pra resolver uma recorrência: desenrolar a recorrência para um domínio num subconjunto (infinito) de \mathbb N pra ter um “chute” para uma solução; use indução para provar que a função dada pela recorrência é crescente. Provar que o chute está correto em todo o domínio.

Vamos mostrar, usando indução em n, que a função I do exercício acima é crescente, isto é, I(n) < I(n+1). No caso n=1 temos I(1)= 1 que é menor que I(2) = 2I(1)+2=4. Assumos, para a hipótese da indução, que I(k) < I(k+1) para k<n e vamos provar para {n \geq 2} que {I(n) < I(n+1)}.

A prova considera dois casos. Quando n é ímpar

\displaystyle \begin{array}{rcl} \displaystyle I(n) & = & 2I( \frac{n-1}2 ) + n \\ \displaystyle & < & 2I( \frac{n-1}2 +1 ) + n \\ \displaystyle & = & 2I( \frac{n+1}2 ) + n \\ \displaystyle & < & 2I( \frac{n+1}2 ) + n+1 \\ \displaystyle & = & I(n+1)\end{array}

e quando n é par

\displaystyle \begin{array}{rcl} \displaystyle I(n) & = & 2I( \frac{n}2 ) + n \\ \displaystyle & < & 2I( \frac{n}2 ) + n +1 \\ \displaystyle & = & I(n+1).\end{array}

Portanto, pelo Princípio da Indução, I(n) < I(n+1) para todo n \geq 1.

Seja C\colon \mathbb N^*\to\mathbb R dada recursivamente por C(1)=2 e C(n) = C(\lfloor n/2\rfloor)+2 para n>1.

Desenrolando a recorrência n potência de 2 chegamos a C(n) = 2\log_2 n+2 para todo n potência de 2.

Vamos provar que C(n) \leq C(n+1) para todo n \geq 1. Como C(1)=1 e C(2)= 4 a desigualdade vale para n=1. Vamos assumir que C(k) \leq C(k+1) para todo k<n. Dado {n>1}, se n é par

\displaystyle C(n) = C\left(\frac n2\right)+2 = C\left(\left\lfloor \frac{n+1}2 \right\rfloor\right)+2=C(n+1)

e se n é ímpar

\displaystyle C(n) = C\left(\frac {n-1}2\right)+2 \leq C\left( \frac{n-1}2 +1 \right)+2= C\left(\frac {n+1}2\right)+2 =C(n+1)

portanto C(n) \leq C(n+1) para todo n \geq 1.

Notemos que o caso n par garante que não conseguimos a hipótese de C crescente. Mesmo assim, nesse caso, podemos usar essa técnica, pois \log n é suave (o que explicaremos em seguida). Sempre que f é uma função suave para n suficientemente grande e g e não-decrescente para n suficientemente grande e g(n) =\Theta (f(n)) para n potência de b (b\geq 2) então g(n) =\Theta (f(n)) para todo n. Dizemos que f é suave se é não-decrescente e f(bn) \leq cf(n) para alguma constante positiva c e todo n suficientemente grande. Nesse caso, para n qualquer tomamos k\in\mathbb N^* tal que

\displaystyle b^{k} \leq n < b^{k+1}

se g(n) =\Theta(f(n)) nas potências de b, isto é,

\displaystyle af(n) \leq g(n) \leq Af(n) \text{ para constantes positivas }a,~A\text{ para }n\text{ pot\^encia de b}

e para n suficientemente grande, então

\displaystyle g(n) \leq g(b^{k+1}) \leq Af(b^{k+1}) = Af(b\cdot b^k) \leq Acf(b^k)\leq Acf(n)

em que, na primeira desigualdade usamos que g é não-decrescente, na segunda usamos a comparação assintótica conhecida para potência de b, na terceira na última usamos que f é suave. Com isso provamos que g(n)=O(f(n)). De modo análogo, provamos que g(n) = \Omega(f(n)).

Exercício 6 Prove que g(n) = \Omega(f(n)).

Agora, de volta a função C, sabemos que C(n)=\Theta(\log_2 n) para n potência de 2 e que \log_2 é crescente e, além disso, \log_2(2n) = \log_2(n) +1 \leq 3\log_2 n para todo n. dado n>1 qualquer, tomemos k tal que

\displaystyle 2^{k} \leq n < 2^{k+1}

de modo que

\displaystyle C(n) \leq C(2^{k+1}) \leq A\log_2( 2^{k+1} ) \leq A 3 \log_2( 2^{k} )\leq A 3 \log_2( n )

e

\displaystyle C(n) \geq C(2^{k}) \geq a \log_2( 2^{k} ) \geq a \log_2(\frac 12 2^{k+1} ) \geq a \frac 13 \log_2( n )

ou seja

\displaystyle \frac a3 \log_2( n ) \leq C(n) \leq 3A \log_2( n )

para todo n, onde a e A são as constantes da comparação C(n)=\Theta(\log_2 n) para n potência de 2, portanto,

\displaystyle C(n) =\Theta (\log_2 n).

Observação  Muitas das funções usadas como limitantes em Análise de Algoritmos  são suaves, não são suaves as que crescem muito rapidamente como, por exemplo, 2^n e n!.

Exercício 7 Determine uma solução assintótica para T(n) usando a 3ª estratégia.

Último exemplo: Considere a recorrência {K(1)=K(2)=1} e {K(n) = 3K \left( \left\lfloor \frac n3 \right\rfloor \right) + n} se {n>1}.

Iterando a recorrência e usando o item 12 das propriedades de chão e teto para {f(x) = x/3}, donde {\left\lfloor \lfloor n/3^k \rfloor /3 \right\rfloor = \lfloor n/3^{k+1} \rfloor} temos

\displaystyle \begin{array}{rcl} K(n) & = & K(n) = 3K \left( \left\lfloor \frac n3 \right\rfloor \right) + n\\ &=& 3^2 K \left( \left\lfloor \frac n{3^2} \right\rfloor \right) + 3\left\lfloor \frac n3\right\rfloor + n \\ &=& 3^3 K \left(\left\lfloor \frac n{3^3} \right\rfloor \right) +3^2 \left\lfloor\frac n{3^2}\right\rfloor +3\left\lfloor{\frac n3}\right\rfloor + n \\ &\vdots& \\&=& 3^k K \left(\left\lfloor \frac n{3^k} \right\rfloor \right) + 3^{k-1}\left\lfloor{\frac n{3^{k-1}}}\right\rfloor +\cdots+3\left\lfloor{\frac n3}\right\rfloor+ n \end{array}

tomando {k=\lfloor{\log_3 n}\rfloor} temos

\displaystyle K(n) = 3^{\lfloor{\log_3 n}\rfloor} K(1) + \sum_{i=0}^{\lfloor{\log_3 n}\rfloor-1} 3^i\left\lfloor{\frac n{3^i}}\right\rfloor.

Sabemos que \log_3 (n) - 1\leq \lfloor \log_3 n \rfloor \leq \log_3 n, como exponencial é função crescente {3^{\log_3 n - 1}\leq 3^{\lfloor{\log_3 n}\rfloor} \leq 3^{\log_3 n}}, portanto,

\displaystyle \frac 13 n\leq 3^{\lfloor{\log_3 n}\rfloor} \leq n

logo {3^{\lfloor{\log_3 n}\rfloor}= \Theta(n)}.

Para todo {i\in \{0,...,\lfloor{\log_3 n}\rfloor-1\}} vale que {3^i\lfloor{\frac n{3^i}}\rfloor \leq n}, portanto

\displaystyle \sum_{i=0}^{\lfloor{\log_3 n}\rfloor-1} 3^i\lfloor{\frac n{3^i}}\rfloor \leq \sum_{i=0}^{\lfloor{\log_3 n}\rfloor-1} n = n \lfloor{\log_3 n}\rfloor = O(n\log n).

Por outro lado, para todo {i\in \{0,...\lfloor{\log_3 n}\rfloor-1\}} vale que {3^i\lfloor{\frac n{3^i}}\rfloor \> n-3^i}, portanto

\displaystyle \sum_{i=0}^{\lfloor{\log_3 n}\rfloor -1} 3^i\lfloor{\frac n{3^i}}\rfloor \> \sum_{i=0}^{\lfloor{\log_3 n}\rfloor-1} n-3^i = n\lfloor{\log_3 n}\rfloor - \frac{1-(1/3)^{\lfloor{\log_3 n}\rfloor}}{1 - (1/3)} =

\displaystyle n\lfloor{\log_3 n}\rfloor - \frac{1-(1/n)}{2/3}= n\lfloor{\log_3 n}\rfloor - \frac 23 + \frac 2{3n} =\Omega (n\log n)

Portanto o somatório é {\Theta(n\log n)} e com isso temos a hipótese de que

\displaystyle K(n) = \Theta (n\log n).

Vamos provar que {K(n) = \Theta (n\log n)}.

Primeiro, vamos provar que existem cosntantes {c,n_0} tais que {K(n) \leq cn {\log_3 n}} para todo {n\geq n_0}.

Tome {c=2} e {n_0=3}. Usando indução

Base:

\displaystyle \begin{array}{rcl} K(3)= 6 &\leq & c\cdot 3 \cdot {\log_3 3} \\ K(4)= 7 &\leq & c\cdot 4 \cdot {\log_3 4} \\ K(5)= 8 &\leq & c\cdot 5 \cdot {\log_3 5} \\ K(6)= 9 &\leq & c\cdot 6 \cdot {\log_3 6} \\ K(7)= 10&\leq & c\cdot 7 \cdot {\log_3 7} \\ K(8)= 11&\leq & c\cdot 8 \cdot {\log_3 8} \\ \end{array}

Passo:

Seja {n\geq 9} inteiro e assuma que para todo {k\in[n_0..n-1]}, {K(k) \leq ck {\log_3 k}}.

\displaystyle \begin{array}{rcl} K(n) & = & 3K \left( \left\lfloor \frac n3 \right\rfloor \right) + n\\ &\leq & 3c\left\lceil n/3 \right\rceil \log_3 \left\lceil n/3 \right\rceil + n\\ & \leq & 3c(n/3)\log_3 (n/3) + n\\ & =& cn{\log_3 n} -cn + n\\ & < & cn{\log_3 n}. \end{array}

Logo {K(n) = O(n\log n)}.

Agora, vamos provar que existem constantes {c,n_0} tais que {K(n) \geq cn \lfloor{\log_3 n}\rfloor} para todo {n\geq n_0}.

Tome {c=1} e {n_0=3}. Usando indução

Base:

\displaystyle \begin{array}{rcl} K(3)= 6 &\geq & c\cdot 3 \cdot \left\lfloor\log_3 3\right\rfloor \\ K(4)= 7 &\geq & c\cdot 4 \cdot \left\lfloor\log_3 4\right\rfloor \\ K(5)= 8 &\geq & c\cdot 5 \cdot \left\lfloor\log_3 5\right\rfloor \\ K(6)= 9 &\geq & c\cdot 6 \cdot \left\lfloor\log_3 6\right\rfloor \\ K(7)= 10&\geq & c\cdot 7 \cdot \left\lfloor\log_3 7\right\rfloor \\ K(8)= 11&\geq & c\cdot 8 \cdot \left\lfloor\log_3 8\right\rfloor \\ \end{array}

Passo:

Seja {n\geq 9} inteiro e assuma que para todo {k\in[n_0..n-1]}, {K(k) \geq ck \left\lfloor\log_3 k\right\rfloor}.

\displaystyle \begin{array}{rcl} K(n) & = & 3K \left(\left\lfloor \frac n3 \right\rfloor \right) + n\\ & \geq & 3c \left\lfloor n/3 \right\rfloor \left\lfloor \log_3 \left\lfloor n/3 \right\rfloor \right\rfloor + n\\ & > & 3c(n/3 + 1)\left\lfloor\log_3 ( n/3 )\right\rfloor + n\\ & =& cn\left\lfloor\log_3 (n/3)\right\rfloor + 3c\left\lfloor\log_3 (n/3)\right\rfloor + n\\ & =& cn\left\lfloor\log_3 n\right\rfloor -cn + 3c\left\lfloor\log_3 n\right\rfloor -3c + n\\ & > & cn\left\lfloor\log_3 n\right\rfloor. \end{array}

Logo {K(n) = \Omega(n\log n)}.

Obeservação Quando procuramos por soluções assintóticas não há motivo para especificar exatamente as condições iniciais, no caso

\displaystyle T(n)= \begin{cases} \Theta (1),~\textrm{ se }&n\leq n_0\\ T \left( \left\lceil \frac n2 \right\rceil \right) + T\left( \left\lfloor \frac n2 \right\rfloor \right) + \Theta (n), ~\textrm{ se } & n > n_0 \end{cases} \ \ \ \ \ (62)

por exemplo, basta escrever {T(n) = T \left( \left\lceil \frac n2 \right\rceil \right) + T \left( \left\lfloor \frac n2 \right\rfloor \right) + \Theta (n)}

Exercício 8 — sequência de Fibonacci No caso da função {F\colon \mathbb{N}\to\mathbb{R}} definida por

\displaystyle F(0)=0,~F(1)=1 {~\mathrm{ e }~} F(n+1) = F(n) + F(n-1),~\mathrm{se}~ n+1>1.

prove usando indução que {F(n) = \Theta ( \varphi^n)}, onde {\varphi = \frac{1+\sqrt{5}}2}.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s