Big-O로 배우는 알고리즘 복잡도: 코드 예제로 쉽게 이해하기

1. 개요

Big-O는 입력 크기가 증가할 때 실행 시간(또는 메모리)이 어떻게 증가하는지를 설명하는 방법입니다. 이 글에서는 건조한 수식을 사용하지 않고, 실제 Java 코드로 일반적인 복잡도 수준들을 살펴보면서 어느 부분에서 비용이 발생하는지 분석합니다. 이 글을 다 읽고 나면, 코드를 보고 손으로 계산하지 않고도 그것이 O(1), O(n), O(n log n), O(n²) 중 어느 것인지 바로 판단할 수 있을 것입니다.

2. Big-O란 무엇이고, 왜 신경 써야 할까

Big-O는 이 질문에 답합니다: “입력이 두 배가 되면, 실행 시간은 얼마나 증가하나?” Big-O는 상수와 작은 요소들을 무시하고, n(입력 크기)이 무한대로 향할 때의 성장 추세만 나타냅니다.

n = 1.000      -> O(n)은 ~1.000 단계 실행
n = 1.000.000  -> O(n)은 ~1.000.000 단계 실행 (선형 증가)
n = 1.000.000  -> O(n²)은 ~10^12 단계 실행 (급격히 증가)

두 개의 코드가 “겉보기에는 비슷할 수” 있지만, 한쪽에 함수 호출 내부에 숨겨진 중첩 루프가 있으면 복잡도가 완전히 다릅니다. Big-O를 이해하면 100개의 테스트 레코드에서는 잘 실행되지만 프로덕션에서 1천만 개의 레코드를 만나면 “멈추는” 코드를 피할 수 있습니다.

주의: Big-O는 일반적인 관례상 최악의 경우(worst case)를 설명합니다. 최선의 경우나 평균 경우를 명시적으로 언급하지 않는 한 그렇습니다.

3. O(1) – 상수 시간

실행 시간이 입력 크기에 관계없이 항상 동일합니다.

public class InventoryCache {

    private final Map<String, Integer> stockBySku = new HashMap<>();

    public Integer getStock(String sku) {
        return stockBySku.get(sku); // HashMap.get은 평균적으로 O(1)
    }
}

HashMap의 get() 메서드는 키의 해시값을 계산한 후 해당 버킷으로 직접 이동하므로, 맵의 원소 개수에 영향을 받지 않습니다. 마찬가지로 array[i] 접근이나 ArrayList의 list.get(i)도 O(1)입니다. 단지 오프셋 주소를 계산하면 되기 때문입니다.

4. O(n) – 선형 시간

실행 시간이 입력 크기에 정비례하여 증가합니다.

public class OrderValidator {

    public boolean hasExpiredItem(List<Order> orders) {
        for (Order order : orders) {
            if (order.isExpired()) {
                return true; // 조기에 종료하지만 최악의 경우 전체를 순회
            }
        }
        return false;
    }
}

for 루프는 최대 n개의 orders 원소를 순회합니다. 최악의 경우는 만료된 주문이 없을 때 발생하며, 이 경우 전체 리스트를 확인해야 합니다. 이것이 전형적인 O(n) 패턴입니다: 단일 루프, 중첩되지 않음.

4.1. 흔한 함정: 루프 내 contains() 호출

public class DuplicateChecker {

    // List의 contains()가 O(n)이고 n번 반복되므로 O(n²)
    public boolean hasDuplicateSlow(List<String> emails) {
        List<String> seen = new ArrayList<>();
        for (String email : emails) {
            if (seen.contains(email)) {
                return true;
            }
            seen.add(email);
        }
        return false;
    }
}

seen.contains(email)은 ArrayList에서 O(n)이므로, 찾기 위해 선형으로 검색해야 합니다. 루프 내에서 이를 호출하면 전체 함수가 O(n²)가 됩니다 — 복잡도를 신경 쓰지 않으면 매우 쉽게 빠질 수 있는 함정입니다.

public class DuplicateChecker {

    // HashSet.add/contains가 O(1)이므로 O(n)
    public boolean hasDuplicateFast(List<String> emails) {
        Set<String> seen = new HashSet<>();
        for (String email : emails) {
            if (!seen.add(email)) { // 이미 존재하면 add()가 false 반환
                return true;
            }
        }
        return false;
    }
}

List를 HashSet으로 바꾸기만 해도 복잡도가 O(n²)에서 O(n)으로 줄어듭니다. 이것은 데이터 구조 선택이 “미크로 최적화”보다 얼마나 더 중요한지를 보여주는 실제 예제입니다.

5. O(log n) – 로그 시간

각 단계에서 검색 공간의 절반을 제거합니다.

public class PriceLookup {

    // sortedPrices는 먼저 오름차순으로 정렬되어야 합니다
    public int findIndex(int[] sortedPrices, int target) {
        int low = 0;
        int high = sortedPrices.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (sortedPrices[mid] == target) {
                return mid;
            } else if (sortedPrices[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

이진 검색은 매 while 루프에서 배열을 반으로 나누므로, n = 1.000.000일 때 약 20단계(log₂ 1.000.000 ≈ 20)만 필요하여 결과를 찾을 수 있습니다. 이는 백만 개의 원소를 모두 선형으로 순회하는 것과는 완전히 다릅니다.

class PriceLookupTest {

    @Test
    void shouldFindIndexInSortedArray() {
        int[] prices = {10, 20, 30, 40, 50};
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(prices, 40);

        assertThat(index).isEqualTo(3);
    }

    @Test
    void shouldReturnMinusOneWhenNotFound() {
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(new int[] {1, 2, 3}, 99);

        assertThat(index).isEqualTo(-1);
    }
}

이 테스트는 찾음(index 반환)과 찾지 못함(-1 반환) 모두의 경우에 대해 정확한 동작을 확인합니다. 이진 검색의 가장 중요한 두 분기입니다.

6. O(n log n) – 선형과 로그의 결합

이것은 merge sort, quick sort(평균 경우), 또는 Collections.sort()과 같은 효율적인 정렬 알고리즘의 복잡도입니다.

public class RevenueReport {

    public List<Order> sortByAmountDescending(List<Order> orders) {
        List<Order> copy = new ArrayList<>(orders);
        copy.sort(Comparator.comparing(Order::amount).reversed()); // O(n log n)
        return copy;
    }
}

Java의 Collections.sort()/List.sort()는 Timsort(merge sort의 변형)를 사용하여 최악의 경우 O(n log n)을 보장합니다. sort()를 n번 반복되는 루프 내에서 호출하는 코드를 본다면, 전체 복잡도는 O(n² log n)으로 증가합니다 — 리팩토링이 필요한 신호입니다.

7. O(n²) – 이차 시간

두 개의 중첩 루프, 각각이 전체(또는 거의 전체) 입력을 순회합니다.

public class PairFinder {

    // 합계가 target인 모든 상품 쌍 찾기
    public List<int[]> findPairsSlow(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] + prices[j] == target) {
                    result.add(new int[] {prices[i], prices[j]});
                }
            }
        }
        return result;
    }
}

바깥쪽 루프는 n번 실행되고, 바깥쪽 루프의 각 실행마다 안쪽 루프는 최대 n번 실행됩니다 — 총 비교 작업은 약 n²/2이므로 복잡도는 O(n²)입니다. n = 10.000일 때, 이는 5천만 번의 비교 — 여전히 실행될 수 있지만 눈에 띄게 느립니다.

public class PairFinder {

    // HashSet에서 이미 본 값을 저장하므로 O(n)
    public List<int[]> findPairsFast(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        for (int price : prices) {
            int complement = target - price;
            if (seen.contains(complement)) {
                result.add(new int[] {complement, price});
            }
            seen.add(price);
        }
        return result;
    }
}

각 쌍을 비교하는 대신, 단일 루프와 HashSet에서의 O(1) 조회만 필요합니다. 이것이 “시간을 메모리로 바꾸는” 매우 흔한 기법입니다: seen을 저장할 추가 공간을 사용하지만, 복잡도를 O(n²)에서 O(n)으로 줄입니다.

8. O(2^n) – 지수 시간

입력이 1 증가할 때마다 실행 시간이 두 배가 됩니다 — 모든 부분집합을 계산하는 재귀 함수에서 흔히 볼 수 있습니다.

public class SubsetGenerator {

    public List<List<Integer>> generateAllSubsets(List<Integer> items) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(items, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(List<Integer> items, int index,
                            List<Integer> current, List<List<Integer>> result) {
        if (index == items.size()) {
            result.add(new ArrayList<>(current));
            return;
        }
        // 분기 1: item[index] 선택 안함
        backtrack(items, index + 1, current, result);

        // 분기 2: item[index] 선택
        current.add(items.get(index));
        backtrack(items, index + 1, current, result);
        current.remove(current.size() - 1);
    }
}

각 원소는 2개의 재귀 분기(선택 또는 미선택)를 만들므로, n개의 원소는 2^n개의 부분집합을 생성합니다. n = 20일 때 이미 100만 개 이상의 부분집합이고, n = 40이면 어떤 머신도 합리적인 시간 내에 완료할 수 없습니다. 이는 문제가 허용한다면 동적 프로그래밍(dynamic programming) 알고리즘을 고려해야 한다는 신호입니다.

9. 실제 벤치마크로 빠르게 비교하기

O(n)과 O(n²) 사이의 차이를 “직접 보기” 위한 간단한 테스트 예제:

class DuplicateCheckerBenchmarkTest {

    @Test
    void fastVersionShouldHandleLargeInputQuickly() {
        List<String> emails = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) {
            emails.add("user" + i + "@example.com");
        }
        DuplicateChecker checker = new DuplicateChecker();

        long start = System.nanoTime();
        boolean hasDuplicate = checker.hasDuplicateFast(emails);
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;

        assertThat(hasDuplicate).isFalse();
        assertThat(elapsedMs).isLessThan(500); // O(n)이므로 100k개 원소에서도 여전히 매우 빠름
    }
}

hasDuplicateFast를 같은 100.000개의 이메일로 hasDuplicateSlow로 바꾸면, 실행 시간이 500ms를 훨씬 초과합니다 — 실제 데이터에서 O(n)과 O(n²) 사이의 차이에 대한 시각적 증거입니다.

10. 종합 표와 빠른 인식 규칙

Big-O	코드의 신호	예시
O(1)	루프 없음, 직접 접근 (배열 인덱스, HashMap.get)	map.get(key)
O(log n)	각 단계에서 검색 공간의 일부 제거	이진 검색
O(n)	입력을 순회하는 단일 루프	List 순회 for
O(n log n)	루프와 정렬의 결합, 또는 분할 정복	Collections.sort()
O(n²)	중첩 루프, 모두 입력을 순회	모든 쌍 비교
O(2^n)	각 단계에서 2개 분기 재귀, 가지치기 없음	모든 부분집합 생성

빠른 계산 규칙: 입력을 순회하는 중첩 루프의 개수를 세기 — 각 루프 레이어는 하나의 “n 지수”를 더합니다. 루프 내에서 라이브러리 함수(contains, sort, indexOf)를 호출하면, 그 함수의 복잡도를 먼저 찾은 후 총합에 더합니다.

주의: Big-O는 실제 상수에 대해 아무것도 말하지 않습니다. 큰 상수를 가진 O(n) 알고리즘(예: 각 루프에서 파일을 읽음)은 n이 충분히 크지 않을 때 작은 상수를 가진 O(n log n)보다 느릴 수 있습니다. 실제로 프로파일링하기 전에 Big-O를 맹목적으로 최적화하지 마세요.

11. 결론

Big-O는 절대 수치가 아니라 추세를 예측하는 도구입니다 — 하지만 바로 그 추세가 데이터가 증가할 때 코드가 살아남는지 망가지는지를 결정합니다. 가장 실용적인 팁: 루프를 작성할 때마다 스스로 물어보세요 “이 루프 내에 O(n) 함수 호출이 있나?” — 이것이 실제로 원하지 않은 O(n²) 버그의 대부분의 원인입니다. 위의 6가지 복잡도 수준을 확실히 이해하면 매일 만나는 대부분의 알고리즘 코드를 읽고 평가할 수 있을 것입니다.