This content originally appeared on DEV Community and was authored by Gissandro Gama
Complexidade de Algoritmos com Elixir: Entendendo o O(N^2) e Por que sua lista é tão lenta?
Se você programa em Elixir ou qualquer outra linguagem e já viu seu código funcionar perfeitamente com 10 itens, mas travar com 10.000, você esbarrou na Complexidade de Algoritmos.
A Notação Big O O(...) não mede o tempo em segundos, mas sim a regra de crescimento do tempo de execução em relação ao tamanho da entrada (N). É a ferramenta mais importante para escrever código que escala.
Acelerando e Desacelerando: O(1) vs. O(N)
Em Elixir, a estrutura de dados mais fundamental é a Lista Ligada Simples (Singly Linked List). Entender como ela funciona nos dá a base para o O(1) e o O(N).
🟢 O(1): Complexidade Constante
O tempo de execução é sempre o mesmo, não importa se sua lista tem 10 elementos ou 1 milhão.
- Exemplo Elixir: Colocar um novo elemento no início (prepend) da lista.
# O(1): Cria um novo nó que aponta para a lista antiga.
new_list = [novo_item | lista_antiga]
# O(1): Acesso à Cabeça
[head | _] = new_list
Essa é a operação mais comum em código funcional e a razão pela qual a criação de listas em Elixir é tão rápida.
🟡 O(N): Complexidade Linear
O tempo de execução cresce proporcionalmente ao tamanho da entrada. Se a lista dobra de tamanho, o tempo dobra.
- Exemplo Elixir: Varrer a lista (map, reduce) ou anexar um item no final.
# O(N): Percorre CADA elemento da lista
sum = Enum.reduce(list, 0, &(&1 + &2))
# O(N): Para anexar no final, o sistema deve percorrer a lista inteira.
list = list ++ [item_no_fim]
🔥 O(N^2): O Vilão Quadrático
A complexidade O(N^2) é o seu pior inimigo para escalabilidade. Se a entrada (N) dobra de tamanho, o tempo de execução quadruplica (2^2 = 4).
Causa: A presença de laços de repetição aninhados (um loop dentro de outro loop) onde o loop interno depende do tamanho total da entrada.
Exemplo Prático: Checagem Ingênua de Duplicatas
Imagine que queremos verificar se há duplicatas em uma lista. Se usarmos a abordagem ingênua, acabamos com O(N^2):
def check_duplicate_slow(list) do
# Enum.any? itera pela lista: N vezes
Enum.any?(list, fn current_element ->
# Para cada current_element, essa linha varre a lista INTEIRA novamente: N vezes
list
|> Enum.filter(&(&1 == current_element))
|> Enum.count() > 1
end)
end
Análise:
- O
Enum.any?externo executa N vezes. - Para cada execução, o
Enum.filterinterno varre toda a lista (N elementos). - Total de operações =~ N x N = O(N^2).
Se N = 10.000, o algoritmo fará 100.000.000 de operações (cem milhões). Um crescimento insustentável!
Próxima Parada: O Salto para $O(N)$
A solução O(N^2)$ é fácil de escrever, mas destrói a performance. Existe uma forma de resolver o problema de duplicatas visitando cada elemento apenas uma vez, transformando o algoritmo em um rápido O(N)?
No próximo post, exploraremos a técnica que usa estruturas de dados O(1) para eliminar o laço interno, transformando o código de lento e quadratico em rápido e linear. Não perca a Migração de O(N^2) para O(N) !
This content originally appeared on DEV Community and was authored by Gissandro Gama
Gissandro Gama | Sciencx (2025-11-29T23:45:14+00:00) O que é Big O? e o Vilão O(N^2). Retrieved from https://www.scien.cx/2025/11/29/o-que-e-big-o-e-o-vilao-on2/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.