알고리즘 시간 복잡도(Big-O) 이해하기

알고리즘을 공부하다 보면 O(1), O(N), O(N²) 같은 표기를 자주 보게 된다.

처음에는 단순히

O(1) < O(log N) < O(N) < O(N log N) < O(N²)

순서만 외웠는데, 실제 코드를 볼 때는 이것만으로 부족했다.

중요한 건 **"데이터가 증가했을 때 이 코드는 얼마나 더 많은 일을 해야 하는가?"**였다.

Big-O는 실행 시간이 아니다

Big-O는 코드가 정확히 몇 초 만에 실행되는지를 나타내는 값이 아니다.

입력 데이터의 크기를 N이라고 했을 때 N이 증가함에 따라 필요한 연산량이 어떤 비율로 증가하는지 표현한다.

예를 들어 두 코드가 있다고 해보자.

// A
for (User user : users) {
    process(user);
}
 
// B
for (User user : users) {
    for (User other : users) {
        compare(user, other);
    }
}

A는 데이터 N개를 한 번씩 확인하므로 연산량이 N에 비례한다.

N
→ O(N)

B는 N개의 데이터마다 다시 N개의 데이터를 확인한다.

N × N
→ O(N²)

데이터가 10개일 때는 각각 10번과 100번 정도라 큰 차이가 없어 보인다.

하지만 N이 커지면 이야기가 달라진다.

데이터가 10배 증가했을 때 O(N)은 연산량도 10배 증가하지만, O(N²)은 100배 증가한다.

결국 시간 복잡도를 보는 이유는 현재 데이터에서 코드가 빠른지를 보는 게 아니라, 데이터가 커졌을 때도 괜찮을지를 판단하기 위해서다.

자주 보는 시간 복잡도

실무나 알고리즘 문제에서 자주 접하는 시간 복잡도를 정리하면 다음과 같다.

단순히 순서로 보면 다음과 같다.

O(1)
 ↓
O(log N)
 ↓
O(N)
 ↓
O(N log N)
 ↓
O(N²)

아래로 갈수록 N이 커졌을 때 연산량이 더 빠르게 증가한다.

O(1) — 데이터가 늘어나도 일정하다

대표적인 예가 List의 인덱스 접근이다.

List<String> names = List.of("Kim", "Lee", "Park");
 
String name = names.get(1);

names에 데이터가 3개 있든 100만 개 있든 get(1)을 하기 위해 처음부터 데이터를 탐색하지 않는다.

인덱스를 알고 있기 때문에 해당 위치에 바로 접근할 수 있다.

O(1)

HashMap의 조회도 대표적인 예다.

Map<Long, User> users = new HashMap<>();
 
users.put(1L, new User("Kim"));
users.put(2L, new User("Lee"));
 
User user = users.get(2L);

Key의 해시값을 이용해 데이터가 저장된 위치를 찾기 때문에 일반적으로 조회와 삽입을 **평균 O(1)**로 본다.

여기서 HashMap = 무조건 O(1)이라고 생각하면 조금 다르다. 해시 충돌 등의 상황에서는 추가 탐색이 발생할 수 있기 때문이다.

그래서 HashMap의 O(1)은 보통 평균 시간 복잡도를 의미한다.

O(log N) — 확인할 범위를 계속 줄인다

O(log N)의 대표적인 예는 **이진 탐색(Binary Search)**이다.

정렬된 데이터에서 15를 찾는다고 해보자.

1  3  5  7  9  11  13  15  17

앞에서부터 찾는다면 다음과 같이 확인해야 한다.

1 → 3 → 5 → 7 → 9 → 11 → 13 → 15

하지만 이진 탐색은 가운데부터 확인한다.

1 3 5 7 [9] 11 13 15 17

15는 9보다 크다. 따라서 왼쪽 데이터는 더 이상 확인할 필요가 없다.

11 13 [15] 17

한 번 비교할 때마다 확인해야 할 범위가 절반 정도로 줄어든다.

Java에서는 Collections.binarySearch() 같은 방식으로 사용할 수 있다.

List<Integer> numbers =
        List.of(1, 3, 5, 7, 9, 11, 13, 15, 17);
 
int index = Collections.binarySearch(numbers, 15);

데이터가 1,024개라면 약 10번이면 탐색 범위를 하나까지 줄일 수 있다.

1024
512
256
128
64
32
16
8
4
2
1

데이터가 약 100만 개가 되어도 약 20번 정도다.

N = 1,024       → 약 10번
N = 1,048,576   → 약 20번

그래서 O(log N)은 데이터가 많아져도 상당히 효율적이다.

다만 이진 탐색에는 중요한 조건이 있다.

데이터가 정렬되어 있어야 한다.

정렬되지 않은 List에 이진 탐색만 적용한다고 O(log N)이 되는 것은 아니다.

O(N) — 전체 데이터를 한 번 확인한다

가장 쉽게 볼 수 있는 형태가 단일 반복문이다.

for (User user : users) {
    if (user.getId().equals(targetId)) {
        return user;
    }
}

찾으려는 사용자가 마지막에 있거나 존재하지 않는다면 모든 데이터를 확인해야 한다.

10명      → 최대 10번
1,000명   → 최대 1,000번
1,000,000명 → 최대 1,000,000번

데이터가 N개라면 최대 N개를 확인하므로 O(N)이다.

컬렉션을 새로 만드는 작업도 마찬가지다.

List<User> result = users.stream()
        .filter(User::isActive)
        .toList();

Stream을 사용한다고 시간 복잡도가 사라지는 것은 아니다.

활성 사용자를 찾기 위해서는 결국 기존 사용자를 한 번씩 확인해야 하므로 O(N)이다.

O(N log N) — 정렬에서 자주 만난다

O(N log N)은 효율적인 정렬 알고리즘에서 자주 볼 수 있다.

대표적으로 Merge Sort가 있다.

데이터를 계속 절반으로 나누면,

8개
↓
4개 + 4개
↓
2개 + 2개 + 2개 + 2개
↓
1개 + 1개 + ...

약 log N 단계가 필요하다.

그리고 각 단계에서는 전체 N개의 데이터를 비교하고 합치는 작업이 필요하다.

그래서

N × log N
→ O(N log N)

이 된다.

N이 1,000이라면 대략

1,000 × log₂1000
≈ 1,000 × 10
≈ 10,000

정도의 연산 규모로 볼 수 있다.

같은 1,000개의 데이터를 O(N²)으로 처리하면 약 1,000,000번이므로 데이터가 커질수록 차이가 커진다.

여기서 정렬 알고리즘도 항상 같은 시간 복잡도를 갖는 것은 아니다.

예를 들어 Quick Sort는 보통 다음과 같이 본다.

평균 → O(N log N)
최악 → O(N²)

입력 데이터와 Pivot 선택에 따라 성능이 달라질 수 있기 때문이다.

따라서 알고리즘의 Big-O를 볼 때는 평균인지, 최악의 경우인지도 함께 확인해야 한다.

O(N²) — 각각의 데이터마다 다시 전체를 확인한다

실제 코드에서 특히 조심해서 보게 되는 형태다.

for (User user : users) {
    for (Order order : orders) {
        if (user.getId().equals(order.getUserId())) {
            process(order);
        }
    }
}

사용자 N명에 대해 주문 N개를 다시 확인한다면,

N × N
→ O(N²)

이 된다.

데이터가 1,000개라면 약 100만 번, 10,000개라면 약 1억 번의 비교가 발생할 수 있다.

그래서 데이터가 많아질 가능성이 있는 코드에서 중첩 탐색이 보이면 한 번쯤 시간 복잡도를 생각해볼 필요가 있다.

반복문이 두 개라고 O(N²)은 아니다

시간 복잡도를 처음 공부할 때 다음처럼 외우기 쉽다.

for문 1개 = O(N)
for문 2개 = O(N²)

하지만 반복문 개수만 보고 판단하면 안 된다.

다음 코드는 반복문이 두 개다.

for (User user : users) {
    process(user);
}
 
for (User user : users) {
    save(user);
}

첫 번째 반복문이 N번, 두 번째 반복문도 N번 실행된다.

N + N
= 2N

Big-O에서는 상수를 제거하므로

O(2N)
→ O(N)

이다.

반면 반복문이 중첩되어 있다면 다르다.

for (User user : users) {
    for (User other : users) {
        compare(user, other);
    }
}

N번의 반복 안에서 다시 N번 반복한다.

N × N
= N²

따라서 O(N²)이 된다.

핵심은 반복문이 몇 개인지가 아니라 입력 데이터 N이 증가할 때 연산량이 어떻게 증가하는가다.

Big-O에서는 왜 상수를 무시할까

어떤 알고리즘의 연산량이 다음과 같다고 해보자.

3N + 10

정확한 연산 횟수를 따지면 3과 10도 의미가 있다.

하지만 N이 충분히 커지면 전체 증가율을 결정하는 것은 N이다.

그래서 Big-O에서는

O(3N + 10)
→ O(N)

으로 표현한다.

마찬가지로

O(N² + N + 100)
→ O(N²)

이 된다.

Big-O는 정확한 연산 횟수보다는 입력 데이터가 커질 때 어떤 항이 성능을 지배하는지에 관심이 있기 때문이다.

자료구조를 바꾸면 O(N²)을 O(N)으로 줄일 수도 있다

시간 복잡도를 실제 코드에 적용할 때 가장 이해하기 좋았던 부분이다.

사용자 목록과 주문 목록이 있고, 사용자의 주문을 찾는다고 해보자.

for (User user : users) {
    for (Order order : orders) {
        if (user.getId().equals(order.getUserId())) {
            process(order);
        }
    }
}

각 컬렉션의 크기를 N이라고 하면 O(N²)이다.

이걸 주문 조회용 Map을 먼저 만드는 방식으로 바꿀 수 있다.

Map<Long, Order> orderMap = orders.stream()
        .collect(Collectors.toMap(
                Order::getUserId,
                Function.identity()
        ));
 
for (User user : users) {
    Order order = orderMap.get(user.getId());
 
    if (order != null) {
        process(order);
    }
}

Map을 만드는 데 O(N)이 필요하다.

orders → Map
O(N)

이후 사용자 N명을 순회하면서 Map을 조회한다.

HashMap 조회를 평균 O(1)이라고 보면,

N × O(1)
→ O(N)

전체적으로는

O(N) + O(N)
= O(2N)
→ O(N)

수준으로 볼 수 있다.

중첩 반복문 자체를 조금 빠르게 만드는 게 아니라 조회에 적합한 자료구조를 만들어 탐색 방식 자체를 바꾼 것이다.

List.contains()도 반복문 안에서는 달라진다

비슷한 사례가 contains()다.

List<Long> ids = ...;
 
ids.contains(targetId);

List의 contains()는 원하는 값을 찾기 위해 데이터를 순차적으로 확인할 수 있으므로 O(N)이다.

한 번 호출하는 것만 보면 별문제가 없어 보인다.

하지만 다음과 같이 반복문 안에서 사용하면,

for (User user : users) {
    if (ids.contains(user.getId())) {
        process(user);
    }
}

외부 반복 N번마다 List를 다시 탐색할 수 있다.

N × O(N)
→ O(N²)

반복적으로 존재 여부만 확인하는 것이 목적이라면 HashSet을 고려할 수 있다.

Set<Long> ids = new HashSet<>(idList);
 
for (User user : users) {
    if (ids.contains(user.getId())) {
        process(user);
    }
}

HashSet 생성은 O(N)이지만 이후 contains()는 평균 O(1)로 조회할 수 있다.

HashSet 생성    → O(N)
사용자 순회     → O(N)

전체            → O(N)

알고리즘을 새로 만드는 것뿐 아니라 목적에 맞는 자료구조를 선택하는 것도 시간 복잡도를 개선하는 방법이라는 걸 알 수 있다.

결국 무엇을 봐야 할까

시간 복잡도를 공부하면서 처음에는 각각의 Big-O를 외우는 데 집중했다.

지금은 코드를 볼 때 오히려 다음 질문들을 먼저 생각하는 편이 이해하기 쉽다.

전체 데이터를 몇 번 확인하는가?

전체를 한 번
→ O(N)

한 번 처리할 때마다 범위가 줄어드는가?

절반씩 감소
→ O(log N)

각 데이터마다 전체 데이터를 다시 확인하는가?

N × N
→ O(N²)

반복문 안에서 다른 컬렉션을 다시 탐색하고 있지는 않은가?

for (...) {
    list.contains(...);
    list.stream().filter(...);
}

코드만 보면 단순한 한 줄이지만 내부에서 O(N) 탐색이 발생한다면 전체 시간 복잡도는 달라질 수 있다.

결론

Big-O를 단순하게 정리하면 다음과 같다.

O(1)
→ 데이터가 늘어나도 작업량이 거의 일정하다.

O(log N)
→ 작업할 때마다 탐색 범위를 줄인다.

O(N)
→ 전체 데이터를 한 번 확인한다.

O(N log N)
→ 전체 데이터를 처리하면서 범위를 반복적으로 나눈다.

O(N²)
→ 각각의 데이터에 대해 다시 전체 데이터를 확인한다.

하지만 이것보다 더 기억해둘 만한 질문은 하나였다.

데이터가 10배, 100배 늘어나면 이 코드는 얼마나 더 많은 일을 해야 하는가?

현재 데이터가 몇백 건뿐이라면 O(N²) 코드도 아무 문제 없이 동작할 수 있다. 반대로 데이터가 커지고 같은 로직이 자주 호출된다면 작은 구조 차이가 큰 성능 차이로 이어질 수 있다.

특히 반복문 내부에서 다른 컬렉션을 계속 탐색하고 있다면 HashSet, HashMap처럼 조회에 적합한 자료구조로 바꿀 수 있는지 확인해볼 만하다.

결국 시간 복잡도를 이해하는 목적은 모든 코드를 무조건 O(1)로 만드는 데 있지 않다.

현재 데이터의 규모와 사용 패턴에서 이 코드의 비용이 어떻게 증가할지를 예상하고, 필요할 때 더 적절한 알고리즘과 자료구조를 선택할 수 있는 기준을 갖는 것.

그게 Big-O를 알아야 하는 이유라고 생각한다.