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

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

No Post 1 - O que é Big O? e o Vilão O(N^2), vimos que a complexidade O(N^2) é causada por um laço aninhado que obriga o sistema a varrer a lista inteira (N) para cada elemento (N). Se um algoritmo tem que fazer N x N operações, ele não vai escalar.

A chave para migrar de O(N^2) 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 uma 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?" de forma instantânea, sem precisar iterar.

Em Elixir, essa estrutura é o MapSet (Conjunto) ou o Map (Mapa). Eles utilizam uma técnica chamada Hashing para transformar a chave em um endereço de memória previsível.

Estrutura	Operação	Complexidade
Lista	Procurar um elemento	O(N)
MapSet	Procurar um elemento	O(1)

---

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

Para resolver o problema de duplicatas em tempo O(N), usaremos uma técnica de programação funcional chamada Acumulação. Vamos percorrer a lista apenas uma vez (Enum.reduce_while), usando um MapSet como nosso 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 # Usamos reduce_while para otimizar, parando assim que a duplicata for achada.
    |> Enum.reduce_while(initial_set, fn element, seen_elements ->
      # Checagem O(1)
      if MapSet.member?(seen_elements, element) do
        # 🟢 Sucesso no Melhor Caso (O(1)): Encontrado! Paramos.
        {:halt, true} 
      else
        # Atualização O(1): Adiciona o elemento e continua.
        new_set = MapSet.put(seen_elements, element)
        {:cont, new_set}
      end
    end) # Trata o resultado: se foi halt, retorna true; se percorreu tudo, retorna false.
    |> (&(&1 == true)).() 
  end

end

📈 Análise de Complexidade

Operação	Frequência	Complexidade
Enum.reduce_while	N vezes	O(N)
MapSet.member?	N vezes (dentro do reduce)	O(1)
MapSet.put	N vezes (dentro do reduce)	O(1)
Complexidade Total	N \times (O(1) + O(1))	O(N)

Ao trocar a busca interna de O(N) para O(1), eliminamos o fator N extra, garantindo que o algoritmo escale linearmente.

Além disso, o uso de Enum.reduce_while nos dá uma otimização no Melhor Caso: se a duplicata for o primeiro elemento, a execução é interrompida em O(1)!

---

Próxima Parada: O O(log N)

Se O(N) é 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) (Logarítmica), a verdadeira "Santa Graal" da velocidade de busca. Veremos por que a lista deve estar ordenada para que isso funcione e qual estrutura de dados de Elixir precisamos usar para implementá-la corretamente.