Programacao · conceitos · algoritmos
O que e a notacao Big O?
A notacao Big O e uma forma de descrever como o tempo de execucao de um algoritmo (ou o uso de memoria) cresce a medida que a sua entrada aumenta. Responde a uma pergunta: quando a quantidade de dados duplica, ou cresce mil vezes, o seu codigo continua rapido, abranda um pouco, ou fica completamente travado? Ignora deliberadamente os segundos exatos e a velocidade da maquina, e foca-se na forma do crescimento - porque e isso que decide se o codigo que funciona com 100 itens ainda funciona com 100 milhoes.
Porque nao medir simplesmente o tempo?
Porque os segundos dependem da maquina, da linguagem, do compilador e do que mais estiver a correr. Execute o mesmo codigo num portatil e num servidor e obtera numeros diferentes. O Big O deita fora tudo isso e mede algo mais duravel: como o trabalho escala com o tamanho da entrada, geralmente chamado de n. Dois algoritmos podem ambos demorar "alguns milissegundos" com entradas pequenas, mas um mantem-se rapido em escala enquanto o outro se torna inutilizavel. O Big O e a forma de os distinguir antes de chegarmos a esse limite.
As complexidades comuns, da melhor a pior
Estes sao os ritmos de crescimento que vai encontrar com mais frequencia, do que escala melhor ao mais perigoso:
| Notacao | Nome | Ideia geral |
|---|---|---|
| O(1) | Constante | O mesmo trabalho independentemente do tamanho da entrada - por exemplo, ler array[5]. |
| O(log n) | Logaritmica | Reduz o problema a metade em cada passo - por exemplo, a pesquisa binaria. |
| O(n) | Linear | O trabalho cresce em conjunto com a entrada - por exemplo, percorrer uma lista uma vez. |
| O(n log n) | Linearitmica | O melhor que se consegue para ordenacao geral - por exemplo, o mergesort. |
| O(n²) | Quadratica | Um ciclo dentro de um ciclo - aceitavel para 100 itens, doloroso para um milhao. |
| O(2ⁿ) | Exponencial | Duplica a cada elemento adicionado - apenas utilizavel para entradas minusculas. |
| O(n!) | Fatorial | Todas as ordenacoes possiveis da entrada - pratico apenas para n muito pequeno. |
Porque as constantes e os termos pequenos sao descartados
O Big O preocupa-se com o crescimento, nao com contagens exatas, por isso simplifica. Se um algoritmo faz 2n + 3 passos, escreve-se O(n): o 2 e o 3 nao alteram a forma da curva a medida que n cresce. Da mesma forma, n² + n torna-se O(n²), porque o termo quadratico domina assim que n e grande. E por isso que o Big O se refere ao termo dominante - a parte que decide o comportamento em escala - e nao a uma leitura precisa de cronometro.
Um exemplo concreto
Suponha que quer verificar se uma lista contem um duplicado. Uma abordagem compara cada item com todos os outros - dois ciclos aninhados, aproximadamente n × n comparacoes, ou seja O(n²). Outra abordagem adiciona cada item a um hash set e verifica a pertenca a medida que avanca - uma unica passagem, ou seja O(n). Com 1.000 itens, a versao quadratica faz cerca de um milhao de comparacoes; com 100.000 itens faz dez mil milhoes, enquanto a versao linear faz 100.000. A mesma tarefa, destinos radicalmente diferentes em escala. Essa diferenca e exatamente o que o Big O foi construido para expor.
Pior caso, caso medio e melhor caso
A rigor, o Big O descreve um limite superior - geralmente o pior caso, o maximo de trabalho que o algoritmo poderia fazer. Vai tambem encontrar dois familiares: Big Omega (Ω) para o melhor caso, um limite inferior, e Big Theta (Θ) quando o melhor e o pior crescem ao mesmo ritmo, dando um limite estreito. No dia a dia, as pessoas dizem "Big O" de forma solta para significar o crescimento no pior caso, porque e em torno disso que se planeia: quer saber quao mau pode ficar, nao a sorte que ocasionalmente pode ter.
Complexidade de espaco, tambem
A mesma notacao descreve a memoria, nao apenas o tempo. Um algoritmo que copia toda a entrada para uma nova estrutura usa O(n) de espaco extra; um que reorganiza a entrada no lugar usa O(1) de espaco extra. Com grandes volumes de dados, a memoria pode ser o verdadeiro limite, por isso vale a pena perguntar tanto "como cresce o tempo?" como "como cresce a memoria?".
Como raciocinar sobre o seu proprio codigo
- Conte os ciclos sobre a entrada. Uma unica passagem e geralmente O(n); um ciclo dentro de um ciclo sobre os mesmos dados e geralmente O(n²).
- Reduzir a metade e um logaritmo. Se cada passo descarta metade dos dados restantes (como a pesquisa binaria), isso e O(log n).
- As consultas num hash map/set sao ~O(1). Substituir uma varredura aninhada por uma consulta hash e a forma classica de transformar O(n²) em O(n).
- Descarte as constantes. Tres passagens unicas separadas continuam a ser O(n), nao O(3n) - o que importa e a forma.
FAQ
Um Big O mais baixo e sempre mais rapido? Em escala, sim - mas nem sempre para entradas pequenas. As constantes e a sobrecarga que o Big O ignora podem fazer um metodo O(n²) superar um O(n log n) num punhado de itens. O Big O diz-lhe quem ganha a medida que os dados crescem, o que e geralmente o que importa.
Qual e a melhor complexidade possivel? O(1), tempo constante - o trabalho nao cresce de todo com a entrada. A seguir vem O(log n). Para problemas que tem de olhar para cada item pelo menos uma vez, O(n) e o minimo.
Porque e que O(n log n) e especial para ordenacao? E o limite inferior comprovado para a ordenacao geral baseada em comparacoes, por isso o mergesort, o heapsort e boas implementacoes de quicksort visam-no todas. Nao e possivel, em geral, ordenar dados arbitrarios mais depressa apenas por comparacoes.
Preciso de Big O para programar no dia a dia? Nao precisa da matematica formal, mas a intuicao e inestimavel: reconhecer quando um ciclo aninhado vai explodir com uma entrada grande, ou quando uma consulta hash o salva, evita classes inteiras de bugs de desempenho.