Quando desenvolvemos soluções para problemas computacionais, frequentemente nos deparamos com múltiplas abordagens possíveis. Como decidir qual é a melhor? A análise de algoritmos nos fornece as ferramentas necessárias para responder a essa pergunta de forma objetiva. Nesta aula, vamos estudar os conceitos fundamentais de complexidade de tempo e espaço, aprender a utilizar a notação Big O e aplicar esses conceitos na comparação de algoritmos clássicos.

O que é Análise de Algoritmos?

A análise de algoritmos é uma área central da ciência da computação que estuda a eficiência dos algoritmos. Diferentemente da medição empírica — que depende do hardware, da linguagem de programação e das condições de execução — a análise teórica nos permite comparar algoritmos de forma abstrata e independente de plataforma.

Dois aspectos principais são considerados:

  • Complexidade de tempo: quantas operações elementares o algoritmo executa em função do tamanho da entrada.
  • Complexidade de espaço: quanta memória adicional o algoritmo utiliza durante sua execução.

O objetivo é determinar como esses custos crescem à medida que o tamanho da entrada aumenta, focando no comportamento para entradas grandes — o que chamamos de comportamento assintótico.

Notação Big O

A notação Big O (ou O grande) é a ferramenta mais utilizada para descrever a complexidade assintótica de algoritmos. Ela representa o limite superior do crescimento do custo de um algoritmo, ou seja, o pior caso possível.

As principais classes de complexidade são:

  • O(1) — Tempo constante: o número de operações não depende do tamanho da entrada. Exemplo: acesso a um elemento de array pelo índice.
  • O(log n) — Tempo logarítmico: a cada passo, o algoritmo reduz o espaço de busca significativamente. Exemplo: busca binária.
  • O(n) — Tempo linear: o custo cresce proporcionalmente ao tamanho da entrada. Exemplo: busca linear.
  • O(n log n) — Tempo quase linear: comum em algoritmos de ordenação eficientes como Merge Sort e Quick Sort.
  • O(n²) — Tempo quadrático: comum em algoritmos com dois loops aninhados, como Bubble Sort.
  • O(2ⁿ) — Tempo exponencial: o custo dobra a cada incremento na entrada. Exemplo: Fibonacci recursivo ingênuo.

É importante entender que a notação Big O descreve o crescimento, não o tempo absoluto. Um algoritmo O(n) com uma constante grande pode ser mais lento que um algoritmo O(n²) com constante pequena para entradas pequenas, mas para entradas grandes, o algoritmo com menor complexidade sempre será mais eficiente.

Calculando Complexidade de Tempo

Para calcular a complexidade de tempo, analisamos quantas operações fundamentais são executadas em função do tamanho n da entrada.

Exemplo 1 — Soma dos elementos de um array:

def soma_array(arr):
    total = 0
    for elemento in arr:
        total += elemento
    return total

O loop executa n iterações, onde n é o tamanho do array. Cada iteração realiza uma soma. Portanto, a complexidade é O(n).

Exemplo 2 — Verificar se um array contém elementos duplicados:

def tem_duplicatas(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

Temos dois loops aninhados. O número total de comparações é aproximadamente n(n-1)/2, o que resulta em complexidade O(n²).

Exemplo 3 — Busca binária:

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

A cada iteração, o espaço de busca é reduzido pela metade. Portanto, a complexidade é O(log n).

Complexidade de Espaço

A complexidade de espaço mede a quantidade de memória adicional que um algoritmo necessita, excluindo o espaço ocupado pela própria entrada.

Exemplo — Inverter um array criando um novo array:

def inverte_array(arr):
    novo = []
    for i in range(len(arr)-1, -1, -1):
        novo.append(arr[i])
    return novo

Criamos um novo array do mesmo tamanho do array original. A complexidade de espaço é O(n).

Versão in-place (sem memória extra significativa):

def inverte_array_inplace(arr):
    esquerda, direita = 0, len(arr)-1
    while esquerda < direita:
        arr[esquerda], arr[direita] = arr[direita], arr[esquerda]
        esquerda += 1
        direita -= 1
    return arr

Usamos apenas duas variáveis auxiliares, independentemente do tamanho do array. A complexidade de espaço é O(1).

A recursão também consome espaço na pilha de chamadas. Uma função recursiva que faz n chamadas aninhadas tem complexidade de espaço O(n) devido ao espaço ocupado pela pilha de execução.

Comparando Algoritmos

Vamos comparar alguns algoritmos clássicos para entender a importância da análise de complexidade.

Busca Linear vs. Busca Binária:

  • Busca linear: percorre todos os elementos até encontrar o alvo — O(n).
  • Busca binária: reduz o espaço de busca pela metade a cada iteração — O(log n).
  • Para um array com 1 milhão de elementos: busca linear pode levar 1 milhão de passos; busca binária, no máximo 20 passos.

Bubble Sort vs. Merge Sort:

  • Bubble Sort: O(n²) — para 10 mil elementos, aproximadamente 100 milhões de operações.
  • Merge Sort: O(n log n) — para 10 mil elementos, aproximadamente 132 mil operações.

A diferença é ainda mais dramática para entradas maiores: para 1 milhão de elementos, Bubble Sort levaria cerca de 1 trilhão de operações, enquanto Merge Sort levaria cerca de 20 milhões.

Pontos-chave

  • A análise de algoritmos permite comparar eficiência de forma independente de hardware
  • Big O descreve o comportamento assintótico do pior caso
  • Complexidade de tempo mede como o número de operações cresce com a entrada
  • Complexidade de espaço mede como o uso de memória cresce com a entrada
  • Algoritmos com menor complexidade são mais escaláveis para grandes entradas
  • A escolha do algoritmo ideal depende do problema, do tamanho da entrada e das restrições do sistema

FAQ — Perguntas Frequentes

Qual a diferença entre Big O, Big Theta e Big Omega?

Big O (O) representa o limite superior (pior caso) do crescimento. Big Omega (Ω) representa o limite inferior (melhor caso). Big Theta (Θ) representa um limite justo quando os limites superior e inferior coincidem, ou seja, quando a complexidade é exata e o algoritmo tem o mesmo comportamento assintótico tanto no pior quanto no melhor caso.

Por que ignoramos constantes na análise Big O?

Porque a notação Big O descreve o comportamento para entradas grandes (análise assintótica). Constantes fixas têm impacto limitado em comparação com o termo dominante quando n cresce. Por exemplo, O(2n) e O(1000n) são ambos simplificados para O(n), pois para n suficientemente grande o que importa é a taxa de crescimento linear.

Um algoritmo O(n²) é sempre pior que um O(n log n)?

Para entradas suficientemente grandes, sim. No entanto, para entradas pequenas, um algoritmo O(n²) com constantes menores pode ser mais rápido que um O(n log n) com alto overhead de implementação. Por isso, é importante considerar o contexto e o tamanho esperado da entrada ao escolher um algoritmo.

Como calcular a complexidade de algoritmos recursivos?

Para algoritmos recursivos, utilizamos relações de recorrência. Analisamos quantas chamadas recursivas são feitas em cada nível e como o tamanho do problema se reduz. Ferramentas como o Teorema Mestre e a árvore de recursão ajudam a resolver essas recorrências e determinar a complexidade assintótica.