Análise Assintótica¶

Objetivos de aprendizado¶

Interpretar O, Ω e Θ como conjuntos de funções.
Analisar laços sequenciais, aninhados e de divisão.
Distinguir análises de pior caso, de caso médio, esperada e amortizada.

Definições¶

Para funções eventualmente não negativas f e g:

f(n) ∈ O(g(n)) se existem constantes c > 0 e n₀ tais que f(n) ≤ c g(n) para todo n ≥ n₀.
f(n) ∈ Ω(g(n)) se f é eventualmente limitada inferiormente por uma constante positiva múltipla de g.
f(n) ∈ Θ(g(n)) se ambos os limites valem.

O(g(n)) é um limite assintótico superior, não necessariamente uma descrição exata ou justa. Dizer que a busca binária é O(n) é verdadeiro, mas pouco informativo; seu tempo de execução no pior caso é mais precisamente Θ(log n).

Taxas de crescimento¶

Classe	Exemplo típico
`Θ(1)`	Acesso a array por índice válido
`Θ(log n)`	Busca binária
`Θ(n)`	Varredura de um array
`Θ(n log n)`	Merge sort
`Θ(n²)`	Comparar todos os pares
`Θ(2ⁿ)`	Enumerar todos os subconjuntos
`Θ(n!)`	Enumerar todas as permutações

Bases de logaritmo diferem apenas por um fator constante, portanto a notação assintótica normalmente omite a base.

Contando operações¶

for i = 0 to n - 1
    for j = i + 1 to n - 1
        visit(i, j)

O número de visitas é (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2, que é Θ(n²).

Um laço que repetidamente divide o problema restante pela metade executa ⌊log₂ n⌋ + O(1) iterações, que é Θ(log n).

Casos e probabilidade¶

Pior caso: custo máximo entre entradas de tamanho n.
Melhor caso: custo mínimo entre entradas de tamanho n.
Caso médio: custo esperado sob uma distribuição de entrada explicitamente declarada.
Custo esperado: expectativa sobre aleatoriedade da entrada, aleatoriedade do algoritmo ou ambas; o espaço de probabilidade deve ser declarado.
Custo amortizado: média por operação sobre toda sequência de operações válidas; não requer distribuição de probabilidade.

Adicionar ao final de um array dinâmico é uma operação clássica com custo amortizado O(1), embora uma inserção individual que exija redimensionamento custe Θ(n).

Espaço¶

Este site relata o pico de espaço auxiliar. A recursão acrescenta quadros de pilha. Um algoritmo in-place normalmente usa O(1) armazenamento auxiliar, embora definições possam permitir O(log n) de espaço na pilha de chamadas; cada página declara sua convenção.

Exercícios¶

Analisar um laço cujo índice dobra após cada iteração.
Mostrar que 3n² + 7n + 4 ∈ Θ(n²) a partir da definição.
Explicar por que caso médio e análise amortizada são diferentes.