This content originally appeared on DEV Community and was authored by Gissandro Gama
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:
- 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.
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.
Entrada (nums) |
Quadrados | Resultado Ordenado |
|---|---|---|
[-4, -1, 0, 3, 10] |
[16, 1, 0, 9, 100] |
[0, 1, 9, 16, 100] |
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):
- Um ponteiro (
l) no início (-4). - Um ponteiro (
r) no fim (10). - Comparamos os quadrados nas pontas. O maior quadrado é colocado na lista de resultados.
- 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)
- Hashing: Quando você insere uma chave (ex:
:user), ela é transformada em um Hash Code (um número). - 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.
- 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.
This content originally appeared on DEV Community and was authored by Gissandro Gama
Gissandro Gama | Sciencx (2025-11-30T00:39:13+00:00) Desafio Final e o Segredo do O(N) (Dois Ponteiros). Retrieved from https://www.scien.cx/2025/11/30/desafio-final-e-o-segredo-do-on-dois-ponteiros/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.