bc1435 – Comparação assintótica de funções

Em análise de algoritmos a complexidade (quantidade de recurso usado) de um algoritmo é, normalmente, expressa por uma função f\colon {\mathbb N}^{\geq n_0} \to {\mathbb R}^{\geq 0} em que {f(n)} é a quantidade (máxima/média/mínima) de recurso consumido para instâncias de tamanho n. Comparar duas dessas funções permite-nos dizer qual algoritmo é mais eficiente com respeito ao consumo daquele recurso.

Abaixo veremos técnicas para compração assintótica de funções, isto é, como as funções se comparam quando {n} é suficientemente grande. Por suficientemente grande entendemos para todo {n \geq n_0} para alguma constante {n_0} que depende do contexto.

Relembrando dois conceitos do cálculo: seja {f\colon {\mathbb N} \rightarrow {\mathbb R}}

{\lim_{n \rightarrow\infty} f(n)=L} se e somente se

\displaystyle \mathrm{para~todo~} \varepsilon > 0,~\mathrm{existe~natural~} n_0, ~\mathrm{tal~que~} n\geq n_0 \Rightarrow |f(n)-L| < \varepsilon

{\lim_{n \rightarrow\infty} f(n)=\infty} se e somente se

\displaystyle \mathrm{para~todo~natural~} m,~\mathrm{existe~natural~} n_0, ~\mathrm{tal~que~} n\geq n_0 \Rightarrow |f(n)| > m

Exercício 1 Suponha {f(n) > 0 } para todo {n\in {\mathbb N}} suficientemente grande. Prove que se {\lim_{n\rightarrow\infty} f(n) = 0} então {\lim_{n\rightarrow\infty} \frac 1{f(n)} = \infty }.

Abaixo {f},~{g},~{h},~{\ell} são funções de {{\mathbb N}} em {{\mathbb R}}, ou seja, sequências de números reais. Ademais, assumiremos que tais sequências são assintoticamente não-negativas, ou seja {f(n)},~{g(n)},~{h(n)},~{\ell(n) \geq 0} para todo {n} suficientemente grande.

— Notação assintótica —

Notação o: Dizemos que {f} é assintoticamente muito menor que {g} se

\displaystyle \lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} = 0.

Denotamos esse fato por { f(n) = o( g(n))}.

Exemplos.

(1) {1 = o( \log(\log (n)))}.

(2) {\log(\log(n)) = o( \log (n))}.

(3) {\log(n) =o( n^{\varepsilon})} para todo {\varepsilon >0}.

(4) {n^{\varepsilon} =o( n^c)} para quaisquer {0< \varepsilon < 1 \leq c}.

(5) {n^c = o( n^{\log n})} para todo {1 \leq c}.

(6) {n^{\log n} = o( \exp(n))}.

(7) {\exp(n) = o( n^{n})}.

(8) {n^{n} =o( \exp(\exp(n)))}.

Notação O: Dizemos que f é assintoticamente menor que {g} e escrevemos

\displaystyle f(n) = O(g(n))

se existe {n_0 > 0} e existe {c>0} tais que

\displaystyle n\geq n_0 \Rightarrow f(n) \leq c g(n)

e nesse caso dizemos que {g} é um limitante superior assintótico para {f}.

Exemplos

(9) {n^2+2n+1 = O(n^2)}.

(10) {5\sin(n) = O(1)}

Atenção o símbolo de {=} na definição não é a igualdade no sentido usual. Notemos que

\displaystyle \begin{array}{rcl} n &=& O(n^2) \\ n^2+2n+1 &=& O(n^2) \end{array}

entretanto {n \neq n^2+2n+1}.

A rigor, {O(g(n))} é um conjunto de funções, a saber, aquelas que são limitdas superiormente e assintoticamente por  {g(n)}.

Teorema 0 {a\cdot f(n) = O( f(n))} para qualquer constante a positiva.

A prova do teorema é imediata da definição de {O( \,)}.

Teorema 1 {f(n) =o( g(n)) \Rightarrow f(n)= O(g(n))}.

A prova é imediata da definição de limite.

Observação. A recíproca do Teorema 1 não vale, como pode ser visto tomando-se f(n)=g(n)=n^2.

Teorema 2 Se {\lim_{n\rightarrow\infty} \frac {f(n)}{g(n)} = L,} em que {L > 0}, então {f(n)= O(g(n))}.

A prova também é imediata da definição de limite.

Teorema 3 Se {f_1(n) = O(g_1(n)) {~\mathrm{ e }~} f_2 = O(g_2(n))} então {f_1(n) + g_2(n) = O(\max\{g_1(n), g_2(n)\})} .

Demonstração: Digamos que f_1(n) \leq c_1 g_1(n) para todo n\geq n_1 e que f_2(n) \leq c_2 g_2(n) para todo n\geq n_2, onde n_1,~n_2,c_1,~c_2 são as constantes dadas pela definição de notação O. Então

\displaystyle \begin{array}{rcl} f_1(n) + f_2 (n) &\leq & c (g_1(n)+g_2(n))\quad \text{ com } c= \max\{c_1,c_2\} \\ &\leq& 2c (\max\{g_1(n), g_2(n)\})\end{array}

para todo n\geq \max\{n_1,n_2\}, o que prova a afirmação.\Box

Cuidados com o teorema acima:

  1. {O(n) = O(n+n^2-n^2) = O(\mathrm{max} \{ n, n^2, -n^2\}) = O(n^2)}.  O problema aqui é que uma das funções não é assintoticamente não-negativa, como assumimos no começo do texto.
  2. {O(1^k +2^k+\cdots+(n-1)^k+n^k) = O(\mathrm{max} \{ 1^k , 2^k , \dots , (n-1)^k , n^k\} ) = O(n^k).}  O problema aqui é que o máximo só pode ser tomado sobre um número de termos que não dependa de {n}. De fato, {O(1^k +\cdots+n^k) = O(n^{k+1})} mas {O(1^k +\cdots+n^k) \neq O(n^k)} (veja o exemplo 16 abaixo).

Fica como exercício verificar os seguintes resultados.

Teorema 4 Se {f(n) = O(g(n)) {~\mathrm{ e }~} g(n) = O(h(n))} então {f(n) = O(h(n))}.

Teorema 5 Se {f(n) = O(g(n)) {~\mathrm{ e }~} h(n) = O(\ell(n))} então {f(n)h(n) = O(g(n)\ell (n))}.

Exemplos.

(11) {a n^2 + bn + c = O(n^2)} para todo {a>0} fixo.

Primeiro, como coeficientes podem ser negativos, observamos que

{an^2 + bn + c \leq an^2 +|b|n + |c|}

Agora usamos o Teorema 0 e 0  Teorema 3 em cada operando das somas, de {an^2 = O(n^2)}{|b|n =O(n)}{|c| = O(1)} temos {an^2 + |b|n + |c| = O( \mathrm{max} \{n^2 ,n, 1\}) = O(n^2)}.

(12) para {k\in{\mathbb N}, a_k>0} constantes, {\sum_{i=0}^k a_in^i = O(n^k)}.

(13) {n\log(n!) = O(n^2 \log n)}.

Primeiro, temos {n=O(n)}. Depois, {n! = \prod_{i=1}^n i < \prod_{i=1}^n n =n^n}. Como log é crescente {\log(n!) < \log(n^n) = n\log (n)}, portanto {\log(n!) = O( n\log (n))}. Pelo Teorema 5, {n\log(n!) = O(n^2 \log n)}.

(14) para todo {a>1}, {\log_a (n) = O(\log_2 (n))}.

De fato, \displaystyle \log_a (n) = \frac 1{\log_2 a} \log_2 n porém { \frac 1{\log_2 a} =O(1)} e {\log_2 n = O(\log_2 n)} e pelo Teorema 5, {\log_a (n) = O(\log_2 (n))}.

Exercício 2 {n=O(\log n) }?


Convenções de notação

  • desconsiderar os coeficientes, por exemplo, usar {O(n^2)} ao invés de {O(a n^2)}, {O(1)} ao invés de {O(1024)}. Notemos que, como classes de funções {O(n^2)=O(a n^2)}{O(1)=O(1024)} pelo Teorema 0.
  • escrever no argumento de {O(\cdot)} somente o termo mais significativo, por exemplo, usar {O(n^2)} ao invés de {O(2n^2 + 5n\log n + 4)}. Notemos que do Teorema 0 e Teorema 3 (conforme observado no item acima) 2n^2+5n\log n+4 = O(\max\{n^2,n\log n,1\}) = O(n^2).

 

Não são verdade as afirmações abaixo [ou o “bestiário da notação assintótica”, caso você escreva uma besteira muito besta na prova, vai aparecer aqui :)]

  • se {f_1(n)= O(g(n))} e {f_2(n)=O(g(n))}, então {f_1(n)=f_2(n)};
  • se {f(n)= O(g(n))} então {g(n)= O^{-1}(f(n))};
  • se {f_1(n)= O(g_1(n))} e {f_2(n)=O(g_2(n))} e para todo {n}, {g_1(n) < g_2(n)}, então para todo {n}, {f_1(n) < f_2(n)};
  • para quaisquer {f} e {g}, {f(n) = O(g(n))} ou {g(n) = O(f(n))}.

— Exercícios —

Verifique se valem

(a) n^{1,5} = O(n^2)

(b) \frac{n^2}{10} = O(n)

(c) se f(n)=O(h(n)) e g(n) = O(h(n)) então f(n)+g(n)=O(h(n))

(d) n^2-100n = O(n^2)

(e) n\log(n) = O(n^2)

(f) n=O(n\log n)

(g) 2^n=O(n)

(h) 2^n=O(2^{n-1})

(i) Teorema 4

(j) Teorema 5

 

Notação  { \Omega}: {f(n) = \Omega(g(n))} se e somente se

\displaystyle \mathrm{existe~} n_0 > 0, ~\mathrm{existe~} C>0, ~f(n) \geq C g(n).

Equivalentemente

\displaystyle f(n)= \Omega(g(n)) \Leftrightarrow g(n) = O(f(n)).

Notação {\Theta}:

\displaystyle f(n) = \Theta ( g(n) ) \Leftrightarrow f(n) = O(g(n)) {~\mathrm{ e }~} g(n) = O(f(n)).

ou, equivalentemente,

\displaystyle f(n) = \Theta ( g(n) ) \Leftrightarrow f(n) = O(g(n)) {~\mathrm{ e }~} f(n) = \Omega (g(n))

ou, equivalentemente,

\displaystyle \mathrm{existem~} n_0>0, ~c>0, ~C>0, ~\mathrm{tais~que~} c g(n) \leq f(n) \leq C g(n).

Estendendo o Teorema 2 podemos concluir da definição de limite o seguinte resultado

Teorema 6 Se {\lim_{n\rightarrow\infty} \frac {f(n)}{g(n)} = L,} então

  • no caso {L > 0}, temos {f(n)= \Theta(g(n))}.
  • no caso {L = 0}, temos {f(n)=O(g(n))} mas {f(n)\neq \Theta(g(n))}.
  • no caso {L = \infty}, temos {f(n)=\Omega(g(n))} mas {f(n)\neq \Theta(g(n))}.

Exemplo

(15) se {a_k \neq 0} então {\sum_{i=0}^k a_in^i = \Theta(n^k)}.

— As funções chão e teto —

Função teto {\lceil \; \rceil \colon {\mathbb R} \rightarrow {\mathbb Z}} dada por

\displaystyle \lceil x \rceil = \min \{ z\in {\mathbb Z} \colon z\geq x \}.

Função chão {\lfloor \; \rfloor \colon {\mathbb R} \rightarrow {\mathbb Z}} dada por

\displaystyle \lfloor x \rfloor = \max \{ z\in {\mathbb Z} \colon z\leq x \}.

Teorema (Propriedades dessas funções) Sejam {x \in {\mathbb R}} e {t\in {\mathbb Z}}.

  1. {\lceil x \rceil = x \Leftrightarrow x\in {\mathbb Z}}.
  2. {\lceil x \rceil = t \Leftrightarrow t-1 < x \leq t},
  3. {\lceil x \rceil = t \Leftrightarrow x \leq t < x+1},
  4. {\lceil \; \rceil} é não-decrescente em {{\mathbb R}},
  5. {\lceil x+t \rceil = \lceil x \rceil + t}.
  6. Se {f:{\mathbb R} \rightarrow {\mathbb R}} é contínua, crescente e tal que f(x) \in {\mathbb Z} \Rightarrow x \in {\mathbb Z} então \displaystyle \big\lceil f ( \lceil x \rceil ) \big\rceil = \lceil f ( x ) \rceil .
  7. {\lfloor x \rfloor = x \Leftrightarrow x\in {\mathbb Z}}.
  8. {\lfloor x \rfloor = t \Leftrightarrow t \leq x < t+1},
  9. {\lfloor x \rfloor = t \Leftrightarrow x - 1 < t \leq x},
  10. {\lfloor \; \rfloor} é não-decrescente em {{\mathbb R}},
  11. {\lfloor x+t \rfloor = \lfloor x \rfloor + t}.
  12. Se {f: {\mathbb R} \rightarrow {\mathbb R}} é contínua, crescente e tal que f(x) \in {\mathbb Z} \Rightarrow x \in {\mathbb Z} então \displaystyle \big\lfloor f ( \lfloor x \rfloor ) \big\rfloor = \lfloor f ( x ) \rfloor .

As demonstrações dessas propriedades são encontradas no final deste texto.

Exercício 3 Mostre que para todo natural n valem que

\displaystyle ~(1)~\left\lfloor \frac{n+1}2 \right\rfloor = \left\lceil \frac n2 \right\rceil  e \displaystyle ~(2)~\left\lceil \frac{n+1}2 \right\rceil = \left\lfloor \frac n2 \right\rfloor +1.

Exercício 4 Prove que

\displaystyle \left\lceil \frac{\lceil x\rceil+m}{n} \right\rceil = \left\lceil \frac{x +m}{n} \right\rceil.

Prove que a mesma igualdade vale se trocamos as ocorrências de \lceil \;\; \rceil por \lfloor \;\;\rfloor.

Exercício 5 Prove: Se {x \in {\mathbb R}} então
\lfloor -x \rfloor = - \lceil x \rceil e  \lceil - x \rceil = - \lfloor x \rfloor.

Exemplos.

(16) \displaystyle \sum_{i=1}^n i^k =\Omega(n^{k+1}) para qualquer inteiro fixo k\geq 0.
De fato,
{\displaystyle \sum_{i=1}^n i^k \geq \sum_{i=\lceil \frac n2\rceil}^n i^k \geq \sum_{i=\lceil \frac n2\rceil}^n \left( \frac n2\right)^k \geq \lfloor \frac n2 \rfloor \left( \frac n2\right)^k \geq \Omega(n^{k+1})}.
Ademais, a soma é limitada por n\cdot n^k, portanto \displaystyle \sum_{i=1}^n i^k =\Theta(n^{k+1}).

(17) {\left\lceil \log_2\left( \frac n2 \right) \right\rceil=\Theta (\log n)}.

Usamos o item 3 das propriedades acima:
Por um lado {\left\lceil \log_2\left( \frac n2\right)\right\rceil \geq \log_2\left( \frac n2 \right) = \log_2(n) - 1 \geq \frac 12\log_2(n) } para n\geq 4. Portanto {\left\lceil \log_2\left( \frac n2\right)\right\rceil =\Omega (\log_2 n)}.

Pelo outro lado {\left\lceil \log_2\left( \frac n2\right)\right\rceil \leq \log_2\left( \frac n2 \right) +1= \log_2(n)} para todo n.Portanto, {\left\lceil \log_2\left( \frac n2\right)\right\rceil =O (\log_2 n)}.

(18) Do item 3 das propriedades acima \lceil f(n) \rceil =\Theta (f(n)) se f(n) \geq 1 para todo n suficientemente grande.
Do item 9, \lfloor f(n) \rfloor = \Theta (f(n)) se f(n) \geq 1 para todo n suficientemente grande.

(19) {\log_2 \left\lceil \frac n2 \right\rceil = \Theta (\log_2 (n))}.

\displaystyle \log_2 \left\lceil \frac n2 \right\rceil \leq \left\lceil \log_2 \left\lceil \frac n2 \right\rceil \right\rceil = \left\lceil \log_2 \frac n2 \right\rceil < \log_2 \left(\frac n2\right) +1 = \log_2 n

A primeira desigualdade vem da Propriedade 2, a igualdade segue da Propriedade 6 e a última desigualdade da Propriedade 3. Logo {\log_2 \lceil n/2 \rceil = O(\log_2 n)}.

Por outro lado, como log é crescente

\displaystyle \left\lceil \frac n2 \right\rceil \geq \frac n2 \Rightarrow \log_2 \left\lceil \frac n2 \right\rceil \geq \log_2 \left( \frac n2 \right)

e

\displaystyle \log_2 \left( \frac n2 \right) = \log_2 (n) - 1 \geq \frac 12 \log_2 (n)

para todo {n\geq 4}, portanto {\log_2 \lceil n/2 \rceil = \Omega(\log_2 n)}. Pela definição {\log_2 \lceil n/2 \rceil = \Theta (\log_2 (n))}.

(20) Seguindo a dedução acima é fácil provar que se f é crescente pra n\geq n_0 (algum n_0) então \displaystyle f \left( \lceil n/2 \rceil \right) = \Theta (f(n)).

Exercício 6 Determine o valor inteiro i pro qual vale que \displaystyle \left\lfloor \frac{n}{2^i} \right\rfloor = 1.

— Notação assintótica em equações —

expressão 1 = expressão 2

onde “expressão” são expressões algébricas que envolvem notação assintótica.

Nesses casos, os termos assintóticos em expressão 1 são quantificados universalmente, enquanto que os termos assintóticos em expressão 2 são quantificados existencialmente.

Exemplos.

(21) {n^3 + O(n^2) = O(n^3) + n^2+ n} entende-se como

\displaystyle \mathrm{para~todo~} f(n)= O(n^2) , ~\mathrm{existe~} g(n) = O(n^3), ~\text{tal que}~ n^3 + f(n) = g(n) + n^2 + n

para todo {n}.

Dado {f(n)= O(n^2)}, tome {g(n)= n^3 +f(n) -n^2- n}, então {g(n)=O(n^3)} e {n^3 + f(n) = g(n) + n^2 + n}.

(22) O número de comparações do Merge-Sort pode ser escrito como

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

que significa que existe {f(n) = \Theta (n)} tal que {T(n) = T \left( \left\lceil \frac n2 \right\rceil \right) + T \left( \left\lfloor \frac n2 \right\rfloor \right) + f(n)}, para todo {n}. É sabido que {T(n) = \Theta( n\log n)}.

Demonstração das propriedades das função teto:

  1. Vamos provar 1. Primeiro suponhamos que {\lceil x \rceil = x}. Então {\lceil x \rceil \in {\mathbb Z}} por definição de {\lceil \; \rceil}. Agora, suponhamos que {x \in {\mathbb Z}}. Então {x \in \{ z\in {\mathbb Z} \colon z\geq x \}} e como {\lceil x \rceil = \min \{ z\in {\mathbb Z} \colon z\geq x \}} temos \displaystyle x \geq \lceil x \rceil. Por outro lado, {\lceil x \rceil \in \{ z\in {\mathbb Z} \colon z\geq x \}}, portanto

    \displaystyle x \leq \lceil x \rceil \ \ \ \ \ (1)

    donde concluímos que {\lceil x \rceil = x}.

  2. Vamos provar 2. Supohamos que {\lceil x \rceil = t}. Se {\lceil x \rceil = t} então {t-1 < x} pois, caso contrário, isto é se {t-1 \geq x} então {t -1 \in \{ z\in {\mathbb Z} \colon z\geq x \}} e {t -1 <t } em que {t = \min \{ z\in {\mathbb Z} \colon z\geq x \}}, uma contradição. Por (1) {x \leq t}. Logo \displaystyle t-1 < x {~\mathrm{ e }~} x \leq t .  Por outro lado, suponhamos {t-1 < x {~\mathrm{ e }~} x \leq t .}  Então, { x \leq t} e {\lceil x \rceil = \min \{ z\in {\mathbb Z} \colon z\geq x \}} implica em {\lceil x \rceil \leq t}, e de {t-1 < x} e (1) temos {t-1 \leq \lceil x \rceil }, ou seja, {t \leq \lceil x \rceil } pois { t,\lceil x \rceil \in {\mathbb Z}}.
  3. Vamos provar 3. Supohamos que {\lceil x \rceil = t}. Se {\lceil x \rceil = t} então {t \geq x}. Do item 2 temos {t-1 < x}, ou seja, {t < x +1}. Portanto, \displaystyle x \leq t {~\mathrm{ e }~} t < x+1. Agora, suponhamos que {x \leq t {~\mathrm{ e }~} t < x+1.} De {t < x+1} e {x+1 \leq \lceil x \rceil +1} temos {t\leq \lceil x \rceil}. Por outro lado, se {x \leq t} então {t\in \{ z\in {\mathbb Z} \colon z\geq x \}}, portanto {t\geq \lceil x \rceil}, logo {t =\lceil x \rceil }.
  4. Vamos  provar que para {x,y \in {\mathbb R}}, \displaystyle x < y \Rightarrow \lceil x \rceil \leq \lceil y \rceil.Se {x < y} e { y \leq \lceil y \rceil} então { x \leq \lceil y \rceil}, portanto {\lceil y \rceil \in \{ z\in {\mathbb Z} \colon z\geq x \}}, portanto, {\lceil x \rceil \leq \lceil y \rceil}.
  5. Usando o item 3 temos \displaystyle x \leq \lceil x \rceil < x+1, portanto \displaystyle x + t \leq \lceil x \rceil + t < x+t+1 e pelo item 3,  novamente, \displaystyle \lceil x \rceil + t = \lceil x + t \rceil.
  6. Seja {f\colon {\mathbb R} \rightarrow {\mathbb R}} contínua, crescente e tal que {f(x) \in {\mathbb Z} \Rightarrow x \in {\mathbb Z}}, vamos provar que {\big\lceil f ( \lceil x \rceil ) \big\rceil = \lceil f ( x ) \rceil} em dois casos. Sabemos por (1) que {x \leq \lceil x \rceil}. Se {x = \lceil x \rceil} então {\big\lceil f ( \lceil x \rceil ) \big\rceil = \lceil f ( x ) \rceil}. Resta provar o caso {x < \lceil x \rceil}. Seja {x} um real tal que {x < \lceil x \rceil}. Se {f} é crescente, então {f(x) < f \big(\lceil x \rceil\big)}. Se {f(x) < f \big(\lceil x \rceil\big)} então {\lceil f(x) \rceil \leq \lceil f \big(\lceil x \rceil\big)\rceil} pelo item 4 do teorema anterior. Suponhamos que {\lceil f(x) \rceil < \lceil f \big( \lceil x \rceil \big) \rceil}. Se {\lceil f(x) \rceil > f \big( \lceil x \rceil \big)} então {\lceil f(x) \rceil} é um inteiro entre {f( \lceil x \rceil )} e { \lceil f( \lceil x \rceil )\rceil}, o que não é possível, portanto

    {f(x) < \lceil f(x) \rceil < f \big( \lceil x \rceil \big)}

    Como {f} é contínua e crescente  existe {a \in (x, \lceil x \rceil)} tal que {f(a)= \lceil f(x) \rceil}. Logo {f(a)\in {\mathbb Z}} e, por hipótese, {a\in {\mathbb Z}}, uma contradição. \Box.

    Com isso, vale {\lceil f(x) \rceil \leq \lceil f \big(\lceil x \rceil\big)\rceil} mas não vale  {\lceil f(x) \rceil < \lceil f \big(\lceil x \rceil\big)\rceil}, ou seja, {\lceil f(x) \rceil = \lceil f \big(\lceil x \rceil\big)\rceil}. \Box

Exercício 7 Prove as propriedaDes da função chão.

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