Nesta aula começamos a estudar análise de complexidade de algoritmos, uma área essencial para qualquer cientista da computação. Através dela, podemos comparar a eficiência de diferentes soluções para um mesmo problema sem precisar executá-las. Vamos aprender a notação Big O e como aplicá-la para descrever o comportamento assintótico dos algoritmos.

O que é complexidade de algoritmos?

Complexidade de algoritmos é uma medida da quantidade de recursos (tempo ou espaço) que um algoritmo consome em função do tamanho da entrada. Normalmente estamos interessados no comportamento para entradas grandes, o que chamamos de análise assintótica. Isso nos permite ignorar constantes e fatores de baixa ordem, focando no termo que domina o crescimento.

A complexidade de tempo indica quantas operações elementares o algoritmo realiza. Já a complexidade de espaço indica quanta memória adicional é necessária.

Notação Big O, Ω e Θ

A notação Big O (O) descreve o limite superior (pior caso) de um algoritmo. Dizemos que f(n) = O(g(n)) se existem constantes c e n0 tais que f(n) ≤ c·g(n) para todo n ≥ n0.

Complementarmente, a notação Ω (Omega) descreve o limite inferior (melhor caso) e a notação Θ (Theta) indica um limite justo, quando o algoritmo é tanto O(g(n)) quanto Ω(g(n)).

Na prática, usamos Big O na maioria das vezes para expressar o pior caso.

Exemplos práticos: busca linear e busca binária

Vamos analisar dois algoritmos clássicos de busca: a busca linear e a busca binária (em um array ordenado).

Busca linear: percorre o elemento por elemento até encontrar o alvo. No pior caso, visita todos os n elementos, portanto sua complexidade é O(n).

def busca_linear(arr, alvo):
    for i in range(len(arr)):
        if arr[i] == alvo:
            return i
    return -1

Busca binária: a cada passo descarta metade dos elementos restantes. No pior caso, o número de iterações é log2(n), logo a complexidade é O(log n).

def busca_binaria(arr, alvo):
    esq, dir = 0, len(arr)-1
    while esq <= dir:
        meio = (esq + dir) // 2
        if arr[meio] == alvo:
            return meio
        elif arr[meio] < alvo:
            esq = meio + 1
        else:
            dir = meio - 1
    return -1

Percebemos como a busca binária é muito mais eficiente para grandes entradas.

Complexidade de espaço

Além do tempo, devemos considerar a memória utilizada. Algoritmos que criam múltiplas cópias da entrada, como alguns tipos de ordenação, podem ter complexidade de espaço O(n) ou mais. É importante equilibrar tempo e espaço de acordo com as restrições do problema.

Principais complexidades em ordem de crescimento

  • O(1) — constante: acesso a um elemento de array por índice
  • O(log n) — logarítmica: busca binária
  • O(n) — linear: busca linear, percorrer uma lista
  • O(n log n) — linearítmica: ordenação eficiente (Merge Sort, Quick Sort no caso médio)
  • O(n²) — quadrática: algoritmos de ordenação simples (Bubble Sort, Insertion Sort no pior caso)
  • O(2ⁿ) — exponencial: algoritmos de força bruta para problemas NP-Completos

Perguntas frequentes

Por que ignoramos constantes na notação Big O?

Quando analisamos o crescimento assintótico, constantes multiplicativas não afetam a taxa de crescimento para entradas grandes. O(n) e O(2n) são ambas lineares; ignorar constantes simplifica a comparação.

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

Big O é um limite superior (pior caso), enquanto Big Θ é um limite justo que funciona como cota superior e inferior simultaneamente. Um algoritmo pode ser O(n²) mas Θ(n) se seu melhor caso for linear e o pior quadrático; Θ só se aplica quando o limite é o mesmo para o melhor e pior caso.

Como calcular a complexidade de um loop?

Para um loop simples que executa n iterações, a complexidade é O(n). Se houver um loop aninhado, a complexidade é O(n²) quando ambos rodam até n. Se o segundo loop depende de i, a análise pode resultar em O(n²) também. Sempre buscamos o termo de maior ordem.