O(N^2)에서 O(N)으로의 전환: O(1)의 힘

Source: Dev.to

O(N²)에서 O(N)으로의 마이그레이션: O(1)의 힘

성장 억제: Elixir 데이터 구조로 O(N²)를 O(N)으로 변환하는 방법

이전 글에서는 O(N²) 복잡도가 각 요소(N)마다 전체 리스트(N)를 순회하는 중첩 루프에서 발생한다는 것을 살펴보았습니다. 알고리즘이 N × N 연산을 수행해야 한다면 확장성이 없습니다.

**O(N²)**에서 O(N) (선형) 으로 마이그레이션하기 위한 핵심은 입력의 각 요소가 상수 횟수만큼 방문되도록 보장하는 것입니다.

목표: “리스트에서 요소 찾기” 연산을 O(N)에서 O(1) 로 바꾸기.

O(1) 비밀: 맵과 집합

상수 시간 O(1) 검색 또는 삽입을 얻기 위해서는 기본 Elixir 리스트를 사용할 수 없습니다. “이 항목이 이미 존재하는가?”를 즉시 답할 수 있는 구조가 필요합니다(반복 없이).

Elixir에서 적합한 구조는 MapSet(집합) 또는 Map(맵)입니다. 이들은 해싱을 이용해 키를 예측 가능한 메모리 주소로 변환합니다.

Elixir에서 O(N) 솔루션: Reduce와 MapSet

중복 요소를 O(N) 시간에 해결하기 위해 누적이라는 함수형 기법을 사용합니다. Enum.reduce_while 로 리스트를 한 번만 순회하면서 MapSet을 누적기로 사용해 이미 본 요소들을 추적합니다.

Elixir 코드: 빠른 중복 검사

defmodule OptimizedDuplicationCheck do
  def contains_duplicate_fast(list) do
    # 1. 누적기: 빈 MapSet으로 시작합니다.
    initial_set = MapSet.new()

    list
    |> Enum.reduce_while(initial_set, fn element, seen_elements ->
      # O(1) 체크
      if MapSet.member?(seen_elements, element) do
        # 🟢 최선 경우 (O(1)): 찾았으므로 중단합니다.
        {:halt, true}
      else
        # O(1) 업데이트: 요소를 추가하고 계속합니다.
        new_set = MapSet.put(seen_elements, element)
        {:cont, new_set}
      end
    end)
    |> (&(&1 == true)).()
  end
end

📈 복잡도 분석

내부 검색을 O(N)에서 O(1)로 교체함으로써 추가적인 N 요인을 제거하고 알고리즘이 선형적으로 확장되도록 했습니다. Enum.reduce_while 를 사용하면 최선 경우에도 최적화가 이루어집니다: 중복이 첫 번째 요소라면 실행이 O(1) 로 종료됩니다.

다음 단계: O(log N)

O(N)도 훌륭하지만, 1천만 개 요소 리스트에서 약 24번만에 아이템을 찾을 수 있는 알고리즘을 상상해 보세요.

다음 글에서는 이진 탐색과 복잡도 O(log N) 을 다룰 예정이며, 이는 검색 속도의 진정한 “성배”입니다. 리스트가 정렬돼 있어야 하는 이유와 Elixir에서 이를 올바르게 구현하기 위한 데이터 구조를 살펴보겠습니다.