Sequências e Séries
analise-de-algoritmos avancado analise-realSequências e Séries
Sequências e séries são a linguagem em que se formaliza a ideia de comportamento no limite — o que acontece quando o tamanho da entrada cresce sem parar. É por isso que aparecem em toda análise de algoritmos: perguntar a complexidade de um algoritmo é perguntar como uma sequência se comporta quando $n \to \infty$.
Sequências
Uma sequência é uma função $a: \mathbb{N} \to \mathbb{R}$. Escrevemos $(a_n)$, onde $a_n = a(n)$.
Uma sequência é apenas uma lista infinita e ordenada de números. O que interessa quase nunca são os primeiros termos, e sim para onde a lista tende.
Limite de uma sequência
$$\lim_{n \to \infty} a_n = L \iff \forall \varepsilon > 0, \exists N \in \mathbb{N}: n > N \implies |a_n - L| < \varepsilon$$
A definição parece hostil na primeira leitura, mas descreve um jogo simples entre duas partes. Alguém escolhe uma tolerância $\varepsilon$, por menor que seja. Você precisa exibir um ponto $N$ da sequência a partir do qual todos os termos ficam a menos de $\varepsilon$ de $L$. Se você consegue responder a qualquer $\varepsilon$, a sequência converge para $L$.
O ponto essencial: $N$ pode depender de $\varepsilon$ — em geral, tolerâncias menores exigem esperar mais.
Exemplo
Mostrar que $a_n = 1/n$ converge para $0$. Dado $\varepsilon > 0$, basta tomar $N > 1/\varepsilon$. Aí, para todo $n > N$:
$$\left| \frac{1}{n} - 0 \right| = \frac{1}{n} < \frac{1}{N} < \varepsilon$$
A escolha de $N$ é a resposta ao desafio, e ela existe para qualquer $\varepsilon$.
Sequências que não convergem
Divergir não é uma coisa só. $a_n = n$ cresce sem limite; $a_n = (-1)^n$ é limitada mas oscila entre $-1$ e $1$ sem nunca se estabelecer. As duas divergem, por motivos distintos.
Vale registrar dois resultados úteis: toda sequência convergente é limitada — a recíproca é falsa, como mostra $(-1)^n$ — e toda sequência monótona e limitada converge. O segundo sustenta boa parte da análise.
Séries
Uma série é a soma dos termos de uma sequência:
$$S = \sum_{n=1}^{\infty} a_n = \lim_{N \to \infty} \sum_{n=1}^{N} a_n$$
A definição é indireta, e vale destacar por quê: não se somam infinitos termos. Forma-se a sequência das somas parciais $S_N = \sum_{n=1}^{N} a_n$ e pergunta-se se ela converge. Uma série nada mais é que uma sequência disfarçada.
Série geométrica
$$\sum_{n=0}^{\infty} r^n = \frac{1}{1-r}, \quad |r| < 1$$
É a série mais útil em computação. A soma parcial tem forma fechada:
$$S_N = \frac{1 - r^{N+1}}{1 - r}$$
Com $|r| < 1$, o termo $r^{N+1}$ vai a zero e resta $1/(1-r)$. Com $|r| \ge 1$ ele não vai, e a série diverge.
Uma consequência que aparece o tempo todo: quando o trabalho cai geometricamente a cada nível, o custo total é uma constante vezes o custo do primeiro nível. É o que faz um vetor dinâmico ter inserção amortizada $O(1)$ — a soma $1 + 2 + 4 + \cdots + n$ é menor que $2n$.
Série harmônica
$$\sum_{n=1}^{\infty} \frac{1}{n} = \infty$$
Este é o exemplo que desfaz a intuição errada mais comum: os termos irem a zero não basta para a série convergir. Aqui $1/n \to 0$ e mesmo assim a soma cresce sem limite.
A demonstração clássica agrupa os termos em blocos:
$$\underbrace{\frac{1}{2}}{\ge 1/2} + \underbrace{\frac{1}{3} + \frac{1}{4}}{\ge 1/2} + \underbrace{\frac{1}{5} + \cdots + \frac{1}{8}}_{\ge 1/2} + \cdots$$
Cada bloco soma pelo menos $1/2$, e há infinitos blocos. A divergência é apenas muito lenta: $\sum_{n=1}^{N} 1/n \approx \ln N + \gamma$, onde $\gamma \approx 0{,}5772$ é a constante de Euler-Mascheroni.
Essa aproximação é exatamente o que faz aparecer o $\log n$ na análise do quicksort, do hashing com sondagem linear e do problema do colecionador de cupons.
Série p
$$\sum_{n=1}^{\infty} \frac{1}{n^p} \quad \text{converge} \iff p > 1$$
Generaliza os dois casos anteriores e serve de régua de comparação. A harmônica é o caso limítrofe $p = 1$: para $p$ ligeiramente maior a série converge; em $p = 1$ ela já diverge.
Testes de convergência
| Teste | Quando aplicar |
|---|---|
| Termo geral | Se $a_n \not\to 0$, a série diverge. Só serve para descartar. |
| Comparação | Compare com uma série $p$ ou geométrica conhecida |
| Razão | Útil quando há fatorial ou potência de $n$ |
| Integral | Quando $a_n = f(n)$, com $f$ positiva e decrescente |
| Séries alternadas | Sinais alternados e $ |
O teste do termo geral é o primeiro a aplicar, por ser o mais barato — mas note que ele só produz conclusão negativa. A harmônica passa nesse teste e mesmo assim diverge.
Aplicações em análise de algoritmos
A ponte entre este assunto e a computação está em comparar taxas de crescimento[ref] :
$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = L$$
O valor de $L$ decide a relação assintótica: $L = 0$ significa que $f$ cresce estritamente mais devagar, ou seja, $f \in o(g)$; um $L$ finito e não nulo indica crescimento da mesma ordem, $f \in \Theta(g)$; e $L = \infty$ diz que $f$ domina $g$.
Três somas que aparecem com frequência:
Custo total de uma recursão que divide pela metade. O trabalho por nível forma uma progressão geométrica; quando ela é decrescente, o custo total é dominado pela raiz da recursão.
Análise amortizada. O crescimento de um vetor dinâmico soma $1 + 2 + 4 + \cdots + n < 2n$ — geométrica, logo linear no total, o que dá $O(1)$ amortizado por inserção.
Comparações no quicksort. O número esperado de comparações envolve $\sum_{i=1}^{n} 1/i \approx \ln n$, e é daí que sai o fator logarítmico do $O(n \log n)$ esperado.
Erros comuns
- Concluir convergência a partir de $a_n \to 0$. A harmônica é o contraexemplo definitivo.
- Manipular séries divergentes como se fossem números. Reagrupar termos de uma série que não converge absolutamente pode produzir qualquer resultado — é o conteúdo do teorema de Riemann sobre rearranjos.
- Confundir a sequência com a série. $(1/n)$ converge para zero; $\sum 1/n$ diverge. São objetos diferentes.
- Esquecer a condição $|r| < 1$ na geométrica. A fórmula fechada não vale fora dela.
Referências
- Walter Rudin (1976). Principles of Mathematical Analysis. McGraw-Hill.