Notação Big O para iniciantes: O(1), O(n), O(n ao quadrado) e O(log n) explicadas

Crescimento, não tempo de cronómetro

O Big O não trata de quantos segundos algo demora no seu portátil. Trata de como o trabalho escala quando a entrada cresce. Dois algoritmos podem ser ambos O(n), e ainda assim um corre o dobro da rapidez em hardware real por um fator constante menor. O Big O descarta de propósito essa constante, porque com n suficientemente grande a forma da curva de crescimento domina qualquer multiplicador fixo.

A notação também mantém apenas o termo que cresce mais depressa. Um algoritmo que faz 3n ao quadrado mais 5n mais 200 operações é simplesmente O(n ao quadrado), porque assim que n é grande o termo ao quadrado empequenece o resto. É por isso que o Big O é uma lupa grosseira mas poderosa: dá-lhe a classe de comportamento, exatamente o que precisa ao decidir se uma solução sobreviverá a cem vezes mais dados.

As quatro classes comuns

O(1) é tempo constante: ler um elemento de array por índice ou verificar uma chave de mapa hash custa o mesmo esforço tenha a coleção dez elementos ou dez milhões. O(log n) é logarítmico: a pesquisa binária reduz para metade os dados restantes em cada passo, por isso procurar numa lista ordenada de mil milhões de elementos leva apenas cerca de trinta comparações. Reduzir para metade é a imagem espelhada da duplicação que se vê ao converter números entre bases.

O(n) é linear: somar cada elemento ou percorrer uma lista uma vez toca cada elemento exatamente uma vez, por isso o trabalho sobe em linha reta com n. O(n ao quadrado) é quadrático e costuma vir de ciclos aninhados, como comparar cada par de elementos. Com n de 1000 são um milhão de operações; com n de 1 000 000 são um bilião, e é aí que o código quadrático ingénuo se torna inutilizável sem barulho.

Porque a classe que escolhe importa

A complexidade é o que separa um protótipo que funciona no seu ficheiro de teste de um software que sobrevive aos dados de produção. Ordenar com um algoritmo O(n ao quadrado) parece instantâneo em cem linhas e congela num milhão. Trocar por uma ordenação O(n log n) mantém a mesma tarefa abaixo de um segundo. O algoritmo que escolhe, e não a velocidade da máquina, fixa o teto de quantos dados consegue tratar.

Dito isto, o Big O é assintótico: descreve o comportamento quando n tende para o infinito. Para entradas pequenas, uma rotina mais simples O(n ao quadrado) pode vencer uma sofisticada O(n log n) com muita sobrecarga. A regra prática é conhecer a classe de cada operação central e depois otimizar as partes que verão mesmo um n grande, em vez de perseguir constantes em código que só trata entradas minúsculas.

Perguntas frequentes

Um Big O menor é sempre mais rápido?

Não para entradas pequenas. O Big O ignora os fatores constantes, por isso um método O(n log n) com muita preparação pode perder para um simples ciclo O(n ao quadrado) quando n é minúsculo. A classe menor ganha assim que a entrada é grande o suficiente.

Qual é a diferença entre O(log n) e O(n log n)?

O(log n) faz uma única passagem logarítmica, como uma única pesquisa binária. O(n log n) faz uma quantidade logarítmica de trabalho para cada um dos n elementos, que é o custo de algoritmos de ordenação eficientes como o merge sort.

O Big O cobre também a memória?

Sim. A mesma notação descreve a complexidade de espaço, quanta memória extra um algoritmo precisa à medida que n cresce. Uma ordenação no local pode usar O(1) de espaço extra, enquanto uma que copia os dados usa O(n).

Porque ignoramos as constantes e os termos menores?

Porque com n grande o termo que cresce mais depressa domina tudo o resto, e as constantes dependem de hardware que não controla. Descartá-los dá uma comparação portável de como os algoritmos escalam, independente de qualquer máquina.