구현: 세 가지 차수를 직접 재 보기

이 장에서는 O(n) 선형 탐색, O(log n) 이진 탐색, O(n²) 쌍 세기를 Python으로 구현하고 timeit으로 시간을 잰 뒤, 같은 문제를 O(n²)과 O(n)으로 푸는 두 합(two-sum) 함수를 C++, Java, TypeScript로 옮겨 봅니다.

Python 구현

import timeit

def linear_search(items, target):          # O(n)
    for i, x in enumerate(items):
        if x == target:
            return i
    return -1

def binary_search(items, target):          # O(log n), 정렬된 입력
    lo, hi = 0, len(items)
    while lo < hi:
        mid = (lo + hi) // 2
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    if lo < len(items) and items[lo] == target:
        return lo
    return -1

def count_pairs_with_sum(items, target):   # O(n²)
    count = 0
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] + items[j] == target:
                count += 1
    return count

한 줄씩 보면 다음과 같습니다.

• linear_search는 앞에서부터 비교하므로 최악 Θ(n)입니다.
• binary_search는 [lo, hi) 범위를 유지합니다. 가운데 값이 목표보다 작으면 왼쪽 절반을 버리고, 아니면 오른쪽 절반을 버립니다. 반복마다 범위가 절반이 되므로 약 log₂ n + 1번 돕니다. 끝나면 lo는 목표 이상인 첫 위치입니다(bisect.bisect_left와 같음).
• count_pairs_with_sum은 i < j인 모든 쌍을 봅니다. 앞 장에서 센 것처럼 비교가 n(n-1)/2번이라 Θ(n²)입니다.

timeit으로 재기

timeit은 같은 코드를 여러 번 실행하고 그동안 가비지 컬렉션을 꺼서 잡음을 줄입니다. repeat로 여러 차례 재고 가장 작은 값을 씁니다. 큰 값은 다른 프로세스 등이 만든 잡음일 때가 많습니다.

def bench(func, *args, number=100, repeat=7):
    timer = timeit.Timer(lambda: func(*args))
    return min(timer.repeat(repeat=repeat, number=number)) / number

for n in (1_000, 2_000, 4_000):
    data = list(range(n))
    lin = bench(linear_search, data, -1)        # 없는 값: 최악의 경우
    bi = bench(binary_search, data, -1)
    pairs = bench(count_pairs_with_sum, data, -1, number=1, repeat=5)
    print(f"{n:>6} {lin * 1e6:8.1f}us {bi * 1e6:8.2f}us {pairs * 1e3:8.1f}ms")

한 컴퓨터에서 실행한 예입니다(환경마다 다릅니다).

n을 두 배로 늘릴 때 선형 탐색은 약 2배, 쌍 세기는 약 4배 늘고, 이진 탐색은 거의 변하지 않습니다. 이처럼 n을 두 배씩 늘려 시간 비율을 보는 방법(doubling experiment)은 차수를 확인하는 가장 간단한 실험입니다. 비율 2는 n, 4는 n², 8은 n³을 뜻합니다. 1 µs도 안 되는 측정은 잡음이 커서 비율이 들쭉날쭉합니다.

같은 문제, 두 차수: 두 합

합이 target인 두 원소의 위치를 찾습니다. 모든 쌍을 보면 O(n²)이고, 이미 본 값을 해시 맵에 기억하면 한 번 훑는 O(n)(평균)으로 줄어듭니다.

def two_sum_quadratic(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return i, j
    return None

def two_sum_linear(nums, target):
    seen = {}                        # 값 -> 처음 나온 위치
    for j, x in enumerate(nums):
        i = seen.get(target - x)     # 짝을 본 적 있나? 평균 O(1)
        if i is not None:
            return i, j
        seen.setdefault(x, j)
    return None

nums = [8, 3, 11, 5, 2]
print(two_sum_quadratic(nums, 13), two_sum_linear(nums, 13))  # (0, 3) (0, 3)

답이 여러 개면 두 함수가 찾는 쌍은 다를 수 있습니다. 아래 세 언어도 같은 두 함수를 구현합니다.

C++

#include <iostream>
#include <optional>
#include <unordered_map>
#include <utility>
#include <vector>

using Pair = std::optional<std::pair<int, int>>;

// O(n^2): 모든 쌍을 확인
Pair twoSumQuadratic(const std::vector<int>& nums, int target) {
    for (std::size_t i = 0; i < nums.size(); ++i)
        for (std::size_t j = i + 1; j < nums.size(); ++j)
            if (nums[i] + nums[j] == target) return std::make_pair(int(i), int(j));
    return std::nullopt;
}

// O(n) 평균: 본 값을 해시 맵에 기억
Pair twoSumLinear(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;  // 값 -> 처음 나온 위치
    for (std::size_t j = 0; j < nums.size(); ++j) {
        auto it = seen.find(target - nums[j]);
        if (it != seen.end()) return std::make_pair(it->second, int(j));
        seen.emplace(nums[j], int(j));
    }
    return std::nullopt;
}

int main() {
    std::vector<int> nums{8, 3, 11, 5, 2};
    if (auto r = twoSumLinear(nums, 13)) std::cout << r->first << ' ' << r->second << '\n';  // 0 3
}

Java

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    // O(n^2): 모든 쌍을 확인
    static int[] twoSumQuadratic(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++)
            for (int j = i + 1; j < nums.length; j++)
                if (nums[i] + nums[j] == target) return new int[] {i, j};
        return null;
    }

    // O(n) 평균: HashMap으로 한 번 훑기
    static int[] twoSumLinear(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();  // 값 -> 처음 나온 위치
        for (int j = 0; j < nums.length; j++) {
            Integer i = seen.get(target - nums[j]);
            if (i != null) return new int[] {i, j};
            seen.putIfAbsent(nums[j], j);
        }
        return null;
    }

    public static void main(String[] args) {
        int[] r = twoSumLinear(new int[] {8, 3, 11, 5, 2}, 13);
        System.out.println(r == null ? "none" : r[0] + " " + r[1]);  // 0 3
    }
}

TypeScript

// O(n^2): 모든 쌍을 확인
function twoSumQuadratic(nums: number[], target: number): [number, number] | null {
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      if (nums[i] + nums[j] === target) return [i, j];
  return null;
}

// O(n) 평균: Map으로 한 번 훑기
function twoSumLinear(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>(); // 값 -> 처음 나온 위치
  for (let j = 0; j < nums.length; j++) {
    const i = seen.get(target - nums[j]);
    if (i !== undefined) return [i, j];
    if (!seen.has(nums[j])) seen.set(nums[j], j);
  }
  return null;
}

console.log(twoSumQuadratic([8, 3, 11, 5, 2], 13), twoSumLinear([8, 3, 11, 5, 2], 13)); // [ 0, 3 ] [ 0, 3 ]

정리

• 선형 탐색 O(n), 이진 탐색 O(log n), 쌍 세기 O(n²)는 두 배 실험에서 약 2배, 거의 그대로, 약 4배로 드러납니다.
• timeit은 여러 번 재서 최솟값을 씁니다.
• 두 합은 해시 맵으로 O(n) 메모리를 더 써서 O(n²)을 O(n)으로 줄이는 전형적인 시간-공간 교환입니다.