Nesta aula, vamos mergulhar no conceito de complexidade de algoritmos, uma ferramenta fundamental para qualquer pessoa que deseje escrever código eficiente e escalável. Entender como um algoritmo se comporta à medida que a entrada cresce é essencial para tomar decisões informadas na escolha da melhor estratégia computacional. Vamos explorar a notação assintótica — Big‑O, Ω e Θ — e ver exemplos práticos de análise que nos ajudarão a comparar algoritmos de forma clara e objetiva.

O que é complexidade de algoritmos?

Complexidade de algoritmos é uma medida da quantidade de recursos (tempo de execução ou espaço na memória) que um algoritmo consome em função do tamanho da sua entrada. Normalmente expressamos essa relação usando funções que descrevem o crescimento do custo computacional quando n (o tamanho da entrada) se torna muito grande. O objetivo é classificar algoritmos em categorias de eficiência, por exemplo: O(1), O(log n), O(n), O(n log n), O(n²), etc.

Essa análise nos permite prever, mesmo antes de implementar, qual algoritmo será mais adequado para um determinado volume de dados. Ignoramos constantes multiplicativas e termos de menor ordem, focando apenas no termo dominante — é a chamada análise assintótica.

Notação Assintótica

A notação assintótica é a linguagem que usamos para descrever a complexidade de um algoritmo. As três principais variantes são:

Big‑O (O)

Define um limite superior para o crescimento. Dizemos que um algoritmo é O(f(n)) se, para valores suficientemente grandes de n, o tempo de execução não ultrapassa c · f(n) para alguma constante c > 0. Big‑O é a notação mais comum e usamos para expressar o pior caso de um algoritmo.

Big‑Ω (Ω)

Define um limite inferior: o algoritmo leva pelo menos c · f(n) passos no melhor caso. Útil para estabelecer que nenhum algoritmo pode resolver um problema em tempo inferior a uma certa função.

Big‑Θ (Θ)

Define um limite justo (apertado): o algoritmo é simultaneamente O(f(n)) e Ω(f(n)). Quando temos essa garantia, sabemos que a complexidade cresce exatamente como f(n) (a menos de constantes).

Na prática, a maioria das análises se concentra no Big‑O do pior caso, pois nos dá uma garantia de que o algoritmo nunca será mais lento do que aquele limite.

Exemplos Práticos

Vamos analisar dois clássicos: busca linear e busca binária.

Busca linear: percorre um vetor desordenado até encontrar o elemento desejado. No pior caso, visita todos os n elementos, portanto é O(n).

// Pseudocódigo — Busca Linear
funcao buscaLinear(vetor, alvo)
    para i de 0 ate comprimento(vetor)-1
        se vetor[i] == alvo
            retorna i
    retorna -1

Busca binária: exige que o vetor esteja ordenado e reduz o espaço de busca pela metade a cada iteração. O número de passos é O(log n).

// Pseudocódigo — Busca Binária (iterativa)
funcao buscaBinaria(vetor, alvo)
    esq = 0; dir = comprimento(vetor)-1
    enquanto esq <= dir
        meio = (esq + dir) // 2
        se vetor[meio] == alvo
            retorna meio
        se vetor[meio] < alvo
            esq = meio + 1
        senao
            dir = meio - 1
    retorna -1

A diferença prática é enorme: para um vetor com 1 milhão de elementos, a busca linear pode exigir 1 milhão de comparações, enquanto a binária requer apenas cerca de 20 (log₂ 1.000.000 ≈ 20). Isso ilustra por que a análise assintótica é indispensável.

Por que isso importa?

Escolher o algoritmo errado pode tornar um sistema inviável para conjuntos de dados reais. Em aplicações que processam milhões de registros, a diferença entre um algoritmo O(n²) e outro O(n log n) pode ser a diferença entre segundos e horas de processamento. A análise assintótica também nos ajuda a projetar soluções escaláveis desde o início, evitando retrabalho caro depois que o sistema está em produção.

Além disso, entender complexidade é fundamental para entrevistas técnicas e para ler a literatura da área. É um pilar da Ciência da Computação que atravessa disciplinas como estrutura de dados, inteligência artificial, sistemas operacionais e redes.

Pontos Principais

  • A complexidade de algoritmos mede o crescimento do tempo/espaço em função do tamanho da entrada.
  • A análise assintótica ignora constantes e termos de menor ordem, focando no comportamento para n grande.
  • Big‑O (O) define um limite superior (pior caso); Big‑Ω (Ω) define um limite inferior; Big‑Θ (Θ) é um limite justo.
  • Busca linear é O(n); busca binária é O(log n) — a diferença é drástica para entradas grandes.
  • Algoritmos de ordenação como Merge Sort e Heap Sort são O(n log n), enquanto Bubble Sort é O(n²).
  • Conhecer complexidade ajuda a escolher a melhor implementação para cada cenário.
  • A análise é independente da linguagem de programação e do hardware (a menos de constantes).
  • Recursos como memória (complexidade espacial) também podem ser analisados com a mesma notação.

Perguntas Frequentes

O que significa O(n log n)?

Significa que o tempo de execução cresce proporcionalmente a n vezes o logaritmo de n. É uma complexidade encontrada em algoritmos eficientes de ordenação (Merge Sort, Heap Sort) e em várias operações de divisão e conquista.

Qual a diferença entre Big‑O e Big‑Θ?

Big‑O é apenas um limite superior, ou seja, o algoritmo nunca será pior que aquela função. Big‑Θ é um limite justo: o algoritmo é exatamente daquela ordem, tanto para cima quanto para baixo. Quando dizemos que um algoritmo é Θ(n²), sabemos que ele leva tempo proporcional a n² no melhor e pior caso (desconsiderando constantes).

Por que a análise assintótica ignora constantes?

Porque as constantes dependem de detalhes de implementação, linguagem e hardware. A análise assintótica revela o comportamento intrínseco do algoritmo, que independe desses fatores. Para entradas suficientemente grandes, o termo dominante prevalece independentemente da constante multiplicativa.