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

Pensando Linear: Resolvendo Problemas Complexos em O(N) e o Segredo do O(1) de Elixir 🔑

Chegamos ao final da nossa jornada pela Complexidade de Algoritmos! Vimos o poder do Merge Sort O(N log N) e a velocidade da Busca Binária O(log N).

Neste post final, vamos:

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

Desafio O(N) Avançado: A Técnica dos Dois Ponteiros

Revisite o problema: Dada uma lista já ordenada nums, retorne o lista dos quadrados dos números, também ordenado.

A solução ingênua seria elevar ao quadrado O(N) e depois ordenar O(N log N), totalizando O(N log N).

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

A solução O(N) usa a técnica dos Dois Ponteiros para construir o resultado de trás para frente (do maior para o menor):

1. Um ponteiro (l) no início (-4).
2. Um ponteiro (r) no fim (10).
3. Comparamos os quadrados nas pontas. O maior quadrado é colocado na lista de resultados.
4. O ponteiro correspondente se move para dentro.

Código Elixir: Solução O(N)

Em Elixir, usamos o Enum.reduce para simular o movimento dos ponteiros e o [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: A técnica dos Dois Ponteiros garante que visitamos cada elemento exatamente uma vez O(N), evitando o O(N log N) da ordenação final.

O Segredo Final: Por Que O(1) não é mágica?

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 que a Erlang/Elixir utiliza: as Hash Array Mapped Tries (HAMT).

HAMT: O Motor Imutável do O(1)

1. Hashing: Quando você insere uma chave (ex: :user), ela é transformada em um Hash Code (um número).
2. Trie (Árvore Digital): Esse hash code é usado como um caminho para navegar em uma árvore de alta ramificação (a Trie). O HAMT só precisa descer alguns níveis da árvore para encontrar o endereço exato do valor.
3. Array Mapped: Em cada nível, em vez de ter muitos ponteiros, há um pequeno array (o “mapa”) que é usado para buscar o próximo ramo.

Vantagem da Imutabilidade: Quando você atualiza um MapSet em Elixir, o sistema não precisa copiar toda a estrutura. Ele reutiliza os ramos antigos da árvore (nós) que não foram alterados e apenas cria novos nós para o caminho que foi modificado. Isso é 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.

Parabéns! Fim da Série.

Você agora tem uma compreensão sólida das classes de complexidade, sabe identificar os gargalos O(N^2) 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.