알고리즘 복잡도: Big-O 라벨에서 Java 실행 비용 모델까지

$O(n)$이 $O(n^2)$보다 빠르다는 문장은 입력, 구현, 실행 환경이 빠진 채로는 완전하지 않다. 점근 표기는 입력이 커질 때 특정 자원 사용량의 증가율을 분류한다. 벽시계 시간, JVM 객체 byte, GC pause를 직접 보장하지 않는다.

1. 분석 계약: n과 기본 연산부터 고정한다

문제는 int[]에 중복이 있는지 판단하는 것이다. $n$은 배열 길이, 기본 연산은 두 값을 비교하거나 hash set에 삽입을 시도하는 한 단계로 잡는다. 첫 중복을 발견하면 즉시 종료하며 null은 유효한 빈 배열이 아니라 계약 위반이다.

비교 대상은 두 구현이다.

• 모든 쌍 (i, j)를 직접 비교하는 구현
• 앞에서 본 값을 HashSet<Integer>에 보관하는 구현

두 번째가 평균적으로 적은 단계를 기대하지만 hash 분산, boxing, resize를 공짜로 취급해서는 안 된다.

2. 최선·최악·기댓값은 서로 다른 질문이다

첫 두 값이 같으면 이중 loop도 비교 한 번에 끝난다. 모든 값이 다르면 비교 횟수는 다음 합이다.

따라서 최악의 증가율은 $\Theta(n^2)$이다. HashSet 구현은 중복이 없을 때 정확히 $n$번 add를 시도하지만, 각 add가 평균 상수 시간이라는 결론은 hash가 bucket에 충분히 분산된다는 가정에 의존한다. 공격적 collision이나 구현 세부에 따라 개별 연산의 최악 비용은 달라진다.

3. 상태 추적: 결과뿐 아니라 비용도 출력한다

입력 [1,2,3,4,5]에는 중복이 없다.

불변식: 이중 loop에서 바깥 index i를 시작할 때 i보다 작은 첫 좌표를 가진 모든 쌍은 이미 중복이 아님을 확인했다. HashSet 구현에서 index i를 시작할 때 seen에는 정확히 values[0..i)의 값이 있다.

두 불변식 때문에 중복을 발견하면 true를 반환해도 되고, 끝까지 없으면 모든 가능한 이전 값과의 관계가 검사됐으므로 false가 맞다.

실행 재현

아래 코드는 설명용 조각이 아니라 main에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

import java.util.HashSet;
import java.util.Set;

public final class ComplexityDemo {
    record Result(boolean duplicate, long inspections) {}

    static Result quadratic(int[] values) {
        if (values == null) throw new IllegalArgumentException("values must not be null");
        long inspections = 0;
        for (int i = 0; i < values.length; i++) {
            for (int j = i + 1; j < values.length; j++) {
                inspections++;
                if (values[i] == values[j]) return new Result(true, inspections);
            }
        }
        return new Result(false, inspections);
    }

    static Result hash(int[] values) {
        if (values == null) throw new IllegalArgumentException("values must not be null");
        Set<Integer> seen = HashSet.newHashSet(values.length);
        long inspections = 0;
        for (int value : values) {
            inspections++;
            if (!seen.add(value)) return new Result(true, inspections);
        }
        return new Result(false, inspections);
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        int[] distinct = {1, 2, 3, 4, 5};
        check(quadratic(distinct).inspections() == 10, "n(n-1)/2 comparisons");
        check(hash(distinct).inspections() == 5, "n hash insertions");
        check(quadratic(new int[] {7, 7}).duplicate(), "duplicate");
        check(!hash(new int[0]).duplicate(), "empty");
        System.out.println("quadratic=" + quadratic(distinct));
        System.out.println("hash=" + hash(distinct));
    }
}

javac --release 21 ComplexityDemo.java
java ComplexityDemo

직접 실행한 출력은 다음과 같다.

quadratic=Result[duplicate=false, inspections=10]
hash=Result[duplicate=false, inspections=5]

컴파일러와 런타임은 javac 21.0.11, OpenJDK 21.0.11을 사용했다. assert 옵션에 의존하지 않고 실패 시 AssertionError를 던지므로 위 명령 그대로 검증된다.

4. O, Ω, Θ를 어떻게 읽을까

$O(g(n))$은 충분히 큰 $n$에서 상수배 $g(n)$이 상한임을 뜻한다. $\Omega(g(n))$은 하한, $\Theta(g(n))$은 상한과 하한이 같은 차수임을 뜻한다. 실무에서 흔히 “Big-O”라고만 부르지만, 정확한 증가율을 주장할 수 있으면 $\Theta$가 더 많은 정보를 준다.

상수와 낮은 차수 항을 버리는 이유는 무시해도 된다는 뜻이 아니다. $3n+10$과 $1000n+10$은 모두 $\Theta(n)$이지만 실제 crossover 이전에는 큰 상수가 지배한다. 그래서 점근 분석은 후보를 거르는 단계이고, production 선택은 측정으로 끝내야 한다.

5. 시간과 공간을 같은 표에서 섞지 않는다

int[] 자체는 heap의 array object다. method parameter와 local reference는 frame의 local variable에 들어가지만 배열 원소가 stack에 복사되는 것은 아니다. HashSet<Integer>는 primitive-specialized set이 아니므로 범위를 벗어난 값은 boxing 객체를 추가로 만들 수 있다. 정확한 byte 수는 JVM의 object header, compressed oops, alignment에 따라 달라지므로 JOL 조건 없이 숫자를 단정하지 않는다.

6. amortized cost는 최악을 숨기는 말이 아니다

동적 배열이나 hash table의 resize는 한 연산에서 $O(n)$ 복사를 만들 수 있다. 용량이 기하급수적으로 증가하고 충분히 긴 연산열에 비용을 나누면 연산당 amortized $O(1)$이 될 수 있다. 이는 “모든 호출이 상수 시간”이라는 뜻이 아니다. tail latency가 중요한 요청 경로에서는 resize가 발생하는 개별 호출도 관측해야 한다.

7. 측정은 JMH, 할당은 JFR/JOL로 질문을 나눈다

System.nanoTime() 한 번으로 두 method를 재면 class loading, JIT warm-up, dead-code elimination, GC가 뒤섞인다. JMH는 warm-up, measurement iteration, fork, result consumption을 통제하는 공식 OpenJDK benchmark harness다.

• JMH: 특정 입력 분포에서 throughput/latency crossover를 비교한다.
• JFR: jdk.ObjectAllocationInNewTLAB, GC, CPU sample로 allocation source를 찾는다.
• JOL: 한 JVM 설정에서 int[], Integer, collection node의 layout을 확인한다.

측정 보고서에는 JDK, VM flags, hardware, fork/warm-up/iteration, 데이터 분포를 남긴다. 숫자 없이 도구 이름만 붙이는 것도 검증이 아니다.

8. 대안 선택

정렬 후 인접 비교는 $O(n\log n)$이며 입력을 제자리 변경할 수 있다. 원본 보존을 위해 복사하면 $O(n)$ 공간이 추가된다. “HashSet이 언제나 정답”이 아니다.

9. 실제 도메인에서 비용 모델을 세운다

API idempotency key 중복 검사는 key 수뿐 아니라 보존 기간, hash collision, heap occupancy, GC pause, false rejection을 본다. batch dedup은 input rows, distinct cardinality, spill bytes를 기록한다. rate-limit key는 동시 갱신이 있으므로 단일 HashSet이 아니라 atomicity와 expiry를 제공하는 저장소 계약까지 필요하다.

10. 이건 피한다

• 평균 $O(1)$을 SLA로 쓴다. collision·resize·GC가 p99를 흔든다. capacity와 입력 분포를 정하고 JFR/JMH로 긴 꼬리를 확인한다.
• 입력 공간을 보조 공간으로 센다. 호출자가 이미 가진 int[]와 알고리즘이 새로 만든 set을 분리하지 않으면 대안 비교가 왜곡된다.
• 작은 benchmark 한 번으로 결론 낸다. JIT가 덜 데워졌거나 결과가 제거될 수 있다. JMH fork와 warm-up을 사용하고 원본 workload로 재검증한다.
• Big-O가 같으면 구현도 같다고 본다. 연속 primitive array와 node-based collection은 cache locality와 allocation이 다르다. 실제 자료 표현을 함께 기록한다.

Reference

• Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition — Analysis of Algorithms
• Oracle, The Java Virtual Machine Specification, Java SE 21 — Runtime Data Areas
• Oracle, HashSet — Java SE 21 API
• OpenJDK, JMH — Java Microbenchmark Harness
• OpenJDK, JOL — Java Object Layout
• Oracle, Troubleshoot Performance Issues Using Flight Recorder