Big O란? 그리고 악당 O(N^2)
Source: Dev.to
Elixir와 함께 배우는 알고리즘 복잡도: O(N²)를 이해하고 리스트가 왜 이렇게 느린가?
Elixir 혹은 다른 언어로 프로그래밍하면서 코드가 10개의 아이템에서는 완벽히 동작하지만 10 000개에서는 멈춘다면, 알고리즘 복잡도에 부딪힌 것입니다.
Big O 표기법 O(...)은 초 단위의 실행 시간을 측정하는 것이 아니라, 입력 크기(N)에 대한 실행 시간 성장 규칙을 나타냅니다. 이는 확장 가능한 코드를 작성하기 위한 가장 중요한 도구입니다.
🟢 O(1): 상수 복잡도
실행 시간은 입력 크기에 관계없이 항상 동일합니다. 리스트에 10개의 요소가 있든 100만 개가 있든 차이가 없습니다.
Elixir 예시 – prepend (앞에 삽입):
# O(1): 기존 리스트를 가리키는 새로운 노드를 만든다.
new_list = [novo_item | lista_antiga]
# O(1): 헤드에 접근
[head | _] = new_list이것은 함수형 코드에서 가장 흔한 연산이며, Elixir에서 리스트 생성이 매우 빠른 이유이기도 합니다.
🟡 O(N): 선형 복잡도
실행 시간은 입력 크기에 비례해서 증가합니다. 리스트가 두 배가 되면 실행 시간도 두 배가 됩니다.
Elixir 예시 – 리스트 순회 (map, reduce) 혹은 끝에 추가하기:
# O(N): 리스트의 각 요소를 순회한다
sum = Enum.reduce(list, 0, &(&1 + &2))
# O(N): 끝에 요소를 추가하려면 리스트 전체를 순회해야 한다.
list = list ++ [item_no_fim]🔥 O(N²): 사각형 악당
O(N²) 복잡도는 확장성을 위협하는 최악의 적입니다. 입력(N)이 두 배가 되면 실행 시간은 네 배(2² = 4)로 증가합니다.
원인: 내부 루프가 전체 입력 크기에 의존하는 중첩 반복문.
실전 예시 – 순진한 중복 검사
def check_duplicate_slow(list) do
# Enum.any? 가 리스트를 N번 순회
Enum.any?(list, fn current_element ->
# 각 요소마다 리스트 전체를 다시 순회: N번
list
|> Enum.filter(&(&1 == current_element))
|> Enum.count() > 1
end)
end분석
- 외부
Enum.any?가N번 실행됩니다. - 각 실행마다 내부
Enum.filter가 전체 리스트(N요소)를 순회합니다. - 전체 연산 수 ≈
N × N = O(N²).
N = 10 000이라면 알고리즘은 100 000 000 번의 연산을 수행하게 됩니다(1억 회) – 지속 불가능한 성장입니다!
다음 단계: O(N) 로의 도약
O(N²) 해결책은 작성하기 쉽지만 성능을 파괴합니다. 중복 문제를 각 요소를 한 번만 방문하도록 바꾸면, O(1) 접근이 가능한 자료구조를 이용해 O(N) 의 빠른 알고리즘으로 전환할 수 있습니다. 다음 포스트에서는 이 기술을 자세히 살펴보겠습니다.