DEV Community

Gissandro Gama
Gissandro Gama

Posted on

O que é Big O? e o Vilão O(N^2)

#elixir #algorithms #webdev #performance

Complexidade de Algoritmos com Elixir: Entendendo o O(N^2) e Por que sua lista é tão lenta?

Se você programa em Elixir ou qualquer outra linguagem e já viu seu código funcionar perfeitamente com 10 itens, mas travar com 10.000, você esbarrou na Complexidade de Algoritmos.

A Notação Big O O(...) não mede o tempo em segundos, mas sim a regra de crescimento do tempo de execução em relação ao tamanho da entrada (N). É a ferramenta mais importante para escrever código que escala.

Acelerando e Desacelerando: O(1) vs. O(N)

Em Elixir, a estrutura de dados mais fundamental é a Lista Ligada Simples (Singly Linked List). Entender como ela funciona nos dá a base para o O(1) e o O(N).

🟢 O(1): Complexidade Constante

O tempo de execução é sempre o mesmo, não importa se sua lista tem 10 elementos ou 1 milhão.

  • Exemplo Elixir: Colocar um novo elemento no início (prepend) da lista.
# O(1): Cria um novo nó que aponta para a lista antiga.
new_list = [novo_item | lista_antiga]

# O(1): Acesso à Cabeça
[head | _] = new_list
Enter fullscreen mode Exit fullscreen mode

Essa é a operação mais comum em código funcional e a razão pela qual a criação de listas em Elixir é tão rápida.

🟡 O(N): Complexidade Linear

O tempo de execução cresce proporcionalmente ao tamanho da entrada. Se a lista dobra de tamanho, o tempo dobra.

  • Exemplo Elixir: Varrer a lista (map, reduce) ou anexar um item no final.
# O(N): Percorre CADA elemento da lista
sum = Enum.reduce(list, 0, &(&1 + &2))

# O(N): Para anexar no final, o sistema deve percorrer a lista inteira.
list = list ++ [item_no_fim]
Enter fullscreen mode Exit fullscreen mode

🔥 O(N^2): O Vilão Quadrático

A complexidade O(N^2) é o seu pior inimigo para escalabilidade. Se a entrada (N) dobra de tamanho, o tempo de execução quadruplica (2^2 = 4).

Causa: A presença de laços de repetição aninhados (um loop dentro de outro loop) onde o loop interno depende do tamanho total da entrada.

Exemplo Prático: Checagem Ingênua de Duplicatas

Imagine que queremos verificar se há duplicatas em uma lista. Se usarmos a abordagem ingênua, acabamos com O(N^2):

def check_duplicate_slow(list) do
  # Enum.any? itera pela lista: N vezes
  Enum.any?(list, fn current_element ->
    # Para cada current_element, essa linha varre a lista INTEIRA novamente: N vezes
    list
    |> Enum.filter(&(&1 == current_element))
    |> Enum.count() > 1
  end)
end
Enter fullscreen mode Exit fullscreen mode

Análise:

  1. O Enum.any? externo executa N vezes.
  2. Para cada execução, o Enum.filter interno varre toda a lista (N elementos).
  3. Total de operações =~ N x N = O(N^2).

Se N = 10.000, o algoritmo fará 100.000.000 de operações (cem milhões). Um crescimento insustentável!

Próxima Parada: O Salto para $O(N)$

A solução O(N^2)$ é fácil de escrever, mas destrói a performance. Existe uma forma de resolver o problema de duplicatas visitando cada elemento apenas uma vez, transformando o algoritmo em um rápido O(N)?

No próximo post, exploraremos a técnica que usa estruturas de dados O(1) para eliminar o laço interno, transformando o código de lento e quadratico em rápido e linear. Não perca a Migração de O(N^2) para O(N) !

Top comments (0)