Análise Assintótica

Análise assintótica descreve como o custo de um algoritmo cresce quando a entrada cresce, ignorando constantes e termos de menor ordem. É a linguagem padrão para comparar algoritmos — e também a fonte de várias conclusões erradas quando aplicada sem cuidado.

As cinco notações

Notação	Significado	Analogia
$f = O(g)$	$f$ cresce no máximo como $g$	$\le$
$f = \Omega(g)$	$f$ cresce pelo menos como $g$	$\ge$
$f = \Theta(g)$	Mesma ordem	$=$
$f = o(g)$	Estritamente menor	$<$
$f = \omega(g)$	Estritamente maior	$>$

Formalmente, $f = O(g)$ quando existem $c > 0$ e $n_0$ tais que $0 \le f(n) \le c,g(n)$ para todo $n \ge n_0$.

Pela via dos limites, quando o limite existe:

$$\lim_{n\to\infty}\frac{f(n)}{g(n)} = \begin{cases} 0 & \Rightarrow f = o(g) \ c \in (0,\infty) & \Rightarrow f = \Theta(g) \ \infty & \Rightarrow f = \omega(g) \end{cases}$$

Um esclarecimento importante: $O$ é um limite superior, não uma descrição exata. Dizer que a busca binária é $O(n^3)$ é tecnicamente verdadeiro e praticamente inútil. Quando se quer precisão, a notação correta é $\Theta$.

Hierarquia de crescimento

$$1 \prec \log\log n \prec \log n \prec \sqrt n \prec n \prec n\log n \prec n^2 \prec n^3 \prec 2^n \prec n! \prec n^n$$

Vale ter uma noção concreta das escalas. Supondo $10^9$ operações por segundo:

$n$	$n\log n$	$n^2$	$2^n$
$10^3$	$10,\mu$s	$1$ ms	inviável
$10^6$	$20$ ms	$17$ min	inviável
$10^9$	$30$ s	$30$ anos	inviável

A fronteira prática costuma estar entre $n^2$ e $n^3$: $n = 10^4$ ainda é tratável em $O(n^2)$, mas $n = 10^6$ não é.

Regras de manipulação

$$O(f) + O(g) = O(\max(f,g))$$ $$O(f)\cdot O(g) = O(fg)$$ $$O(cf) = O(f)$$ $$\log_a n = \Theta(\log_b n)$$

A última justifica escrever $O(\log n)$ sem base: mudar de base multiplica por constante. Já em $2^n$ versus $3^n$ a base importa — não são da mesma ordem.

Algumas simplificações frequentes:

$$3n^2 + 5n + 100 = \Theta(n^2), \qquad \log(n!) = \Theta(n\log n)$$

A segunda vem da aproximação de Stirling e é o que dá o limite inferior $\Omega(n\log n)$ para ordenação por comparação.

Melhor, médio e pior caso

São dimensões independentes da notação assintótica, e confundi-las é o erro conceitual mais comum da área.

Algoritmo	Melhor	Médio	Pior
Busca linear	$\Theta(1)$	$\Theta(n)$	$\Theta(n)$
Quicksort	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n^2)$
Merge sort	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n\log n)$
Busca em hash	$\Theta(1)$	$\Theta(1)$	$\Theta(n)$

É perfeitamente correto dizer "o pior caso do quicksort é $\Theta(n^2)$" e "o caso médio é $\Theta(n\log n)$" — são afirmações sobre funções diferentes.

Análise amortizada

Mede o custo médio por operação numa sequência, o que é diferente do caso médio probabilístico: a amortização é uma garantia determinística sobre a sequência inteira.

O exemplo canônico é o vetor dinâmico. Uma inserção individual pode custar $O(n)$ (quando realoca), mas $n$ inserções custam $O(n)$ no total, porque as realocações formam progressão geométrica $1 + 2 + 4 + \cdots + n < 2n$. Logo o custo amortizado é $O(1)$.

O método do potencial formaliza: define-se uma função de potencial sobre o estado da estrutura, e o custo amortizado é o custo real mais a variação de potencial.

Os limites da análise assintótica

Esta seção é a mais importante da página, porque é o que separa quem usa a ferramenta de quem a idolatra.

Constantes importam. Um algoritmo $O(n\log n)$ com constante 1000 perde para um $O(n^2)$ com constante 1 em toda entrada com $n < 10^4$. É por isso que implementações reais de ordenação trocam para inserção em subvetores pequenos.

A hierarquia de memória não aparece. Dois algoritmos $\Theta(n)$ podem diferir em uma ordem de grandeza conforme o padrão de acesso. Percorrer um vetor sequencialmente é muito mais rápido que percorrer uma lista ligada de mesmo tamanho, apesar de ambos serem lineares.

$n$ é finito. Se a entrada real nunca passa de mil elementos, o comportamento assintótico é irrelevante — meça.

O modelo pode não valer. O modelo de custo uniforme supõe operações aritméticas de custo constante, o que deixa de valer com inteiros de precisão arbitrária.

A conclusão prática: use análise assintótica para descartar algoritmos claramente inadequados e para entender escalabilidade; use medição para escolher entre candidatos plausíveis.

Exemplo trabalhado

Analisar:

def f(n):
    total = 0
    for i in range(n):          # n iterações
        for j in range(i, n):   # n - i iterações
            total += 1
    return total

O total de iterações é $\sum_{i=0}^{n-1}(n-i) = n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2}$.

Logo $\Theta(n^2)$. Note que o laço interno não roda $n$ vezes sempre — mas a soma continua sendo quadrática, e o fator $\frac12$ desaparece na notação.

Erros comuns

• Usar $O$ quando se quer dizer $\Theta$.
• Confundir pior caso com caso médio.
• Somar complexidades de laços aninhados em vez de multiplicar.
• Ignorar o custo de operações "simples" — concatenar cadeias imutáveis num laço é o clássico $O(n^2)$ acidental.
• Otimizar assintoticamente sem medir, trocando um algoritmo simples e rápido por um sofisticado e lento na faixa de uso real.
• Esquecer a complexidade de espaço, que às vezes é o gargalo real.

Leituras recomendadas

• Cormen et al., capítulo 3 — as definições formais das cinco notações com exercícios.
• Graham, Knuth e Patashnik, capítulo 9 — assintótica em profundidade, incluindo expansões e a notação $O$ com rigor.
• Knuth, TAOCP volume 1, seção 1.2.11 — a origem do uso rigoroso dessas notações em computação.
• Bentley, Programming Pearls — o contraponto empírico: quando a medição contradiz a análise.

Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein (2009). Introduction to Algorithms. MIT Press. ISBN 9780262533058. Ronald L. Graham and Donald E. Knuth and Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley. ISBN 9780134389967. Donald E. Knuth (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley. Página oficial.

Referências

1. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms. MIT Press.
2. Ronald L. Graham; Donald E. Knuth; Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley.
3. Donald E. Knuth (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.