A Migração de O(N^2) para O(N): O Poder do O(1)

Source: Dev.to

A Migração de O(N²) para O(N): O Poder do O(1)

Domando o Crescimento: Como Transformar O(N²) em O(N) com Estruturas de Dados Elixir

No post anterior vimos que a complexidade O(N²) surge de um laço aninhado que varre a lista inteira (N) para cada elemento (N). Quando um algoritmo precisa fazer N × N operações, ele não escala.

A chave para migrar de O(N²) para O(N) (Linear) é garantir que cada elemento da entrada seja visitado um número constante de vezes.

Objetivo: Transformar a operação de “procurar um elemento na lista” de O(N) para O(1).

O Segredo O(1): Mapas e Conjuntos

Para obter busca ou inserção em tempo constante O(1) não podemos usar a lista padrão de Elixir. Precisamos de uma estrutura que responda “Este item já existe?” instantaneamente, sem iteração.

Em Elixir, as estruturas adequadas são MapSet (conjunto) ou Map (mapa). Elas utilizam hashing para transformar a chave em um endereço de memória previsível.

A Solução O(N) em Elixir: Reduce e MapSet

Para resolver o problema de duplicatas em tempo O(N) usamos a técnica funcional de acumulação. Percorremos a lista apenas uma vez com Enum.reduce_while, usando um MapSet como acumulador para rastrear os elementos já vistos.

Código Elixir: Duplicata Rápida

defmodule OptimizedDuplicationCheck do
  def contains_duplicate_fast(list) do
    # 1. Acumulador: iniciamos com um MapSet vazio.
    initial_set = MapSet.new()

    list
    |> Enum.reduce_while(initial_set, fn element, seen_elements ->
      # Checagem O(1)
      if MapSet.member?(seen_elements, element) do
        # 🟢 Melhor caso (O(1)): encontrado, interrompemos.
        {:halt, true}
      else
        # Atualização O(1): adiciona o elemento e continua.
        new_set = MapSet.put(seen_elements, element)
        {:cont, new_set}
      end
    end)
    |> (&(&1 == true)).()
  end
end

📈 Análise de Complexidade

Ao substituir a busca interna O(N) por O(1), eliminamos o fator N extra, garantindo que o algoritmo escale linearmente. O uso de Enum.reduce_while também oferece otimização no melhor caso: se a duplicata for o primeiro elemento, a execução termina em O(1).

Próxima Parada: O(log N)

Se O(N) já é excelente, imagine um algoritmo que requer apenas ~24 passos para encontrar um item em uma lista de 10 milhões de elementos.

No próximo post exploraremos a Busca Binária e a complexidade O(log N), a verdadeira “Santo Graal” da velocidade de busca. Veremos por que a lista deve estar ordenada e qual estrutura de dados de Elixir usar para implementá‑la corretamente.