Desafio Final e o Segredo do O(N) (Dois Ponteiros)

Introdução

Chegamos ao final da nossa jornada pela Complexidade de Algoritmos! Já vimos o poder do Merge Sort O(N log N) e a velocidade da Busca Binária O(log N).
Neste post final, vamos:

• Aplicar o conhecimento de O(N) em um desafio avançado (o “problema dos quadrados”);
• Revelar o segredo técnico por trás da promessa de O(1) dos Mapas de Elixir.

Revisite o problema

Dada uma lista já ordenada nums, retorne a lista dos quadrados dos números, também ordenada.

Solução ingênua

Elevar ao quadrado cada elemento → O(N)
Ordenar o resultado → O(N log N)

Total: O(N log N).

Solução O(N) com Dois Ponteiros

O truque é usar a informação de que a entrada já está ordenada. Os maiores quadrados estarão sempre nas pontas da lista de entrada, devido aos números negativos com alto valor absoluto.

A técnica dos Dois Ponteiros constrói o resultado de trás para frente (do maior para o menor):

1. Ponteiro l no início (valor -4);
2. Ponteiro r no fim (valor 10);
3. Compare os quadrados nas pontas; o maior quadrado é colocado na lista de resultados;
4. O ponteiro correspondente avança para dentro.

Complexidade: O(N).

Implementação em Elixir

Em Elixir, usamos Enum.reduce para simular o movimento dos ponteiros e [square | acc] (prepend) para construir o resultado de trás para frente em O(1) por passo.

defmodule SortedSquares do
  @doc "Solução O(N) com Dois Ponteiros, construindo o resultado em ordem inversa."
  def sorted_squares(nums) do
    # l: ponteiro esquerdo (0), r: ponteiro direito (N-1)
    {result_reversed, _} =
      0..(length(nums) - 1)
      |> Enum.reduce({[], {0, length(nums) - 1}}, fn _, {acc, {l, r}} ->
        left_square = Enum.at(nums, l) * Enum.at(nums, l)
        right_square = Enum.at(nums, r) * Enum.at(nums, r)

        if left_square > right_square do
          # Se o da esquerda for maior, movemos o ponteiro l
          {[left_square | acc], {l + 1, r}}
        else
          # Se o da direita for maior (ou igual), movemos o ponteiro r
          {[right_square | acc], {l, r - 1}}
        end
      end)

    result_reversed
  end
end

Conclusão da técnica dos Dois Ponteiros

A técnica garante que visitamos cada elemento exatamente uma vez (O(N)), evitando o custo de ordenação final (O(N log N)).

O(1) nos Mapas e MapSets de Elixir

Ao longo desta série, prometemos que a busca/inserção em Map e MapSet de Elixir é O(1). Por que é tão rápido e, mais importante, como o Elixir consegue fazer isso garantindo a imutabilidade?

A resposta está na estrutura de dados utilizada pela Erlang/Elixir: Hash Array Mapped Tries (HAMT).

• Hashing: ao inserir uma chave (ex.: :user), ela é transformada em um hash code (um número).
• Trie (Árvore Digital): esse hash code serve como caminho para navegar em uma árvore de alta ramificação. O HAMT precisa descer apenas alguns níveis para encontrar o endereço exato do valor.
• Array Mapped: em cada nível, em vez de muitos ponteiros, há um pequeno array (o “mapa”) que permite buscar o próximo ramo.

Vantagem da Imutabilidade

Quando você atualiza um MapSet em Elixir, o sistema não copia toda a estrutura. Ele reutiliza os ramos antigos da árvore que não foram alterados e cria novos nós apenas para o caminho modificado. Esse mecanismo é conhecido como Compartilhamento Estrutural (Structural Sharing).

Graças ao HAMT, a promessa de O(1) (tempo constante) para busca e inserção é mantida, e o código Elixir permanece rápido e seguro para concorrência na BEAM.

Resumo Final

Você agora tem uma compreensão sólida das classes de complexidade, sabe identificar gargalos O(N²) e possui as ferramentas de Elixir (Merge Sort, MapSet e reduções) para escrever código que não apenas funciona, mas que escala de forma eficiente.