// Complexidade assintotica

Big-O, seus tipos e como as curvas crescem

Uma leitura curta sobre a origem da notacao, a diferenca entre limites assintoticos e o comportamento pratico das classes de crescimento mais comuns em algoritmos.

Historia

De Landau para analise de algoritmos

A familia de simbolos O, Ω, Θ, o e ω vem da notacao de Landau, criada no contexto da analise matematica para comparar taxas de crescimento.

Na computacao, a notacao ganhou papel central quando passou a ser usada para descrever custo de tempo e espaco em funcao do tamanho da entrada, isolando a forma de crescimento em vez de detalhes de maquina.

Donald Knuth ajudou a consolidar e padronizar esse vocabulário na analise de algoritmos, especialmente ao discutir as diferencas entre limite superior, inferior e limite apertado.

Leitura correta

O que a notacao quer capturar

O objetivo principal nao e prever o tempo exato de execucao, e sim descrever como o custo cresce quando n aumenta.

Isso permite comparar algoritmos de forma mais estavel, mesmo quando linguagem, processador ou detalhes de implementacao mudam.

Em termos práticos: uma curva melhor costuma escalar melhor. Mas constantes, localidade de memoria e layout dos dados ainda importam muito em entradas reais.

Tipos

Os simbolos mais usados

Big-O O(f(n))

Limite superior assintotico. Diz que o algoritmo nao cresce mais rapido do que certa funcao, ignorando constantes.

Leitura prática: pior crescimento esperado dentro de uma ordem de grandeza.

Big-Omega Ω(f(n))

Limite inferior assintotico. Indica que a funcao cresce pelo menos naquela ordem.

Leitura prática: o algoritmo nao consegue crescer menos do que essa classe.

Big-Theta Θ(f(n))

Limite apertado. A funcao cresce na mesma ordem superior e inferior ao mesmo tempo.

Leitura prática: descreve a classe de crescimento mais precisa entre as tres grandes.

little-o o(f(n))

Limite superior estrito. Cresce estritamente mais devagar do que f(n).

Leitura prática: e mais forte que Big-O, porque exclui crescimento na mesma ordem.

little-omega ω(f(n))

Limite inferior estrito. Cresce estritamente mais rapido do que f(n).

Leitura prática: e mais forte que Big-Omega, porque exclui a mesma ordem.

Curvas

Grafico de crescimento assintotico

O grafico abaixo usa uma escala normalizada para comparar o formato das curvas mais comuns. Ele nao representa tempo absoluto, e sim a tendencia de crescimento conforme n aumenta.

O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ) O(n!)

Para manter o grafico legivel, curvas explosivas como O(2ⁿ) e O(n!) sao comprimidas verticalmente na normalizacao.

Classes comuns

Como cada classe costuma se comportar

O(1)

Crescimento constante. A operacao praticamente nao se altera quando a entrada aumenta.

O(log n)

Cresce devagar. Estruturas balanceadas e busca binaria costumam cair aqui.

O(n)

Crescimento linear. Dobrar a entrada tende a dobrar o trabalho.

O(n log n)

Quase linear. Costuma aparecer em algoritmos eficientes de ordenacao geral.

O(n²)

Quadratico. Comparacoes par a par e loops aninhados fazem essa classe crescer rapido.

O(2ⁿ)

Exponencial. Fica inviavel cedo quando o tamanho de entrada aumenta.

O(n!)

Fatorial. Explosao combinatoria severa; aparece em busca exaustiva de permutacoes.

Fontes

Referencias tecnicas

Wolfram MathWorld — Landau Symbols Wolfram MathWorld — Big-O Notation Wolfram MathWorld — Little-O Notation DBLP / DOI — Knuth, Big Omicron and Big Omega and Big Theta (1976) Stanford Profile — Donald Knuth