박테리아 소멸 과정으로 이해하는 시간복잡도 O(log N)

O(N)이나 O(N²)은 그래도 감이 오는데, O(log N)은 처음 보면 좀 낯섭니다. "로그가 갑자기 왜 튀어나오지?" 싶은 경우가 많습니다. 그런데 사실 O(log N)은 아주 익숙한 상황 하나만 떠올리면 금방 이해가 됩니다. 바로 뭔가를 계속 반으로 줄여나가는 상황입니다.

이번 글에서는 "박테리아가 매년 절반씩 줄어들다가 결국 사라지는" 아주 단순한 예시를 가지고, 왜 이런 상황이 O(log N)이 되는지 수식으로 직접 따라가 보고, 실제로 이 패턴이 어떤 알고리즘에서 쓰이는지도 같이 살펴보겠습니다.

---

1. 문제 상황

박테리아가 N마리 있고, 1년이 지날 때마다 그 수가 절반(½)으로 줄어든다고 해봅시다.

• 0년차: N
• 1년차: (½)¹ × N
• 2년차: (½)² × N
• 3년차: (½)³ × N
• ...
• Y년차: (½)ʸ × N

매년 절반씩 곱해지는 구조이기 때문에, Y가 1씩 늘어날 때마다 개체 수는 계속 절반이 됩니다.

여기서 궁금한 건 "그래서 박테리아는 언제 다 사라지는가"입니다. 사실 수학적으로는 ½을 아무리 곱해도 정확히 0이 되지는 않습니다. 그래서 대신 "1마리 미만이 되는 시점" 을 사실상의 소멸 시점으로 잡습니다. 이걸 부등식으로 쓰면 다음과 같습니다.

(½)ʸ × N < 1

이 부등식을 만족하는 가장 작은 Y가 바로 우리가 구하려는 값입니다.

---

2. 수식을 하나씩 풀어보기

(½)ʸ 부터 정리하기

(½)ʸ는 1/(2ʸ)와 같은 값입니다. 그대로 바꿔 쓰면 다음과 같습니다.

(½)ʸ = 1 / 2ʸ

이걸 원래 부등식에 대입하면 다음과 같습니다.

N / 2ʸ < 1

분수 없애기

분수가 있으면 계산하기 번거로우니, 양변에 2ʸ를 곱해서 없애줍니다. 2ʸ는 항상 양수이기 때문에 곱해도 부등호 방향은 그대로 유지됩니다.

N / 2ʸ × 2ʸ < 1 × 2ʸ

N < 2ʸ

2ʸ > N

로그를 취해서 Y 끌어내리기

여기까지 오면 Y가 지수 자리에 박혀 있어서, 이 상태로는 Y 값을 구할 수가 없습니다. 지수 자리에 있는 변수를 끌어내리려면 로그를 써야 합니다. 양변에 밑이 2인 로그를 취해봅니다.

log2(2ʸ) > log2(N)

로그의 정의상 log₂(2ʸ)는 그냥 Y입니다. ("2를 몇 제곱해야 2ʸ가 되냐"고 물으면 답은 당연히 Y입니다.) 그래서 정리하면 다음과 같습니다.

Y > log2(N)

지수 방정식에서 지수 자리의 변수를 구하려고 할 때 로그를 쓰는 건 이런 이유 때문입니다. 로그 자체가 "밑을 몇 제곱해야 이 값이 나오는가"를 구하는 연산이라, 2ʸ = N 꼴의 식에서 Y를 뽑아내려면 로그를 취하는 것이 자연스러운 선택입니다.

---

3. 그래서 왜 O(log N)인가

Y > log₂N이라는 결과는 "박테리아가 없어지려면 최소 log₂N년은 걸린다"는 뜻입니다. 즉 이 과정이 끝나는 데 필요한 반복 횟수(Y)는 N에 비례하는 것이 아니라 log₂N에 비례한다는 것입니다.

그런데 왜 그냥 "log N"이 아니라 앞에 O를 붙여서 O(log N)이라고 쓸까요? 이건 이전 글에서 다룬 빅오 표기법의 정의를 그대로 가져온 것입니다.

Y는 정확히 log₂N인 것이 아니라 log₂N보다 크거나 같은 값이었습니다 (Y > log₂N). 이 말은 결국 "Y라는 실제 반복 횟수는, log₂N이라는 함수를 기준으로 특정 시점 이후부터는 항상 그 값(에 상수를 곱한 것) 이하로 억제된다"는 뜻이고, 이것이 바로 이전 글에서 본 O(g(x))의 조건 그대로입니다. 그래서 log₂N 앞에 O를 붙여서 O(log N)이라고 쓰는 것입니다. (참고로 log의 밑이 2든 10이든 상수 배 차이일 뿐이라, 빅오 표기법에서는 밑을 아예 생략하고 그냥 O(log N)이라고 씁니다.)

자바로 직접 찍어보기

말로만 하면 감이 잘 안 오니, 코드로 직접 확인해봅니다. N마리에서 시작해서 매번 절반으로 줄이다가, 1마리 미만이 될 때까지 몇 번(Y) 반복되는지 세는 코드입니다.

public class BacteriaDecay {

    public static int countYearsUntilExtinct(double n) {
        int year = 0;
        while (n >= 1) {
            n = n / 2.0;
            year++;
        }
        return year;
    }

    public static void main(String[] args) {
        int[] sample = {10, 100, 1000, 1000000, 1000000000};

        for (int n : sample) {
            int years = countYearsUntilExtinct(n);
            double logN = Math.log(n) / Math.log(2); // log2(N)
            System.out.printf("N=%-12d 소멸까지 걸린 반복 횟수=%-4d log2(N)=%.2f%n",
                    n, years, logN);
        }
    }
}

실행해보면 결과는 다음과 같습니다.

N=10           소멸까지 걸린 반복 횟수=4    log2(N)=3.32
N=100          소멸까지 걸린 반복 횟수=7    log2(N)=6.64
N=1000         소멸까지 걸린 반복 횟수=10   log2(N)=9.97
N=1000000      소멸까지 걸린 반복 횟수=20   log2(N)=19.93
N=1000000000   소멸까지 걸린 반복 횟수=30   log2(N)=29.90

N이 10에서 10억까지, 즉 1억 배가 커졌는데도 반복 횟수는 고작 4번에서 30번으로 늘어난 게 전부입니다. 입력이 아무리 커져도 반복 횟수는 이렇게 아주 천천히 늘어난다는 것이 O(log N)의 진짜 의미입니다. (참고로 반복 횟수가 log₂N보다 살짝 더 큰 이유는, N이 확실히 1 밑으로 내려가는 시점까지 세었기 때문입니다.)

---

4. O(log N)

박테리아 문제의 핵심은 결국 "매번 대상을 절반으로 줄여나간다" 는 것 하나입니다. 그리고 이 패턴은 알고리즘을 공부하다 보면 정말 자주 마주치게 됩니다.

이 밖에도 O(log N)인 것들

• 이진 트리 탐색: 균형 잡힌 이진 탐색 트리에서 노드를 찾을 때도, 한 단계 내려갈 때마다 탐색 대상이 절반으로 줄어듭니다.
• 분할 정복 알고리즘의 재귀 깊이: 병합 정렬이나 퀵 정렬처럼 문제를 절반으로 쪼개 나가는 알고리즘의 재귀 깊이가 log N입니다.
• 거듭제곱 빠르게 계산하기: a^n을 구할 때 n을 절반씩 줄여가며 계산하면 O(log n)만에 끝낼 수 있습니다.

결국 공통점은 하나입니다. 한 번의 작업으로 대상 범위가 절반(혹은 일정 비율)씩 줄어든다는 것입니다. "N을 몇 번 절반으로 나눠야 1 이하가 되는가"라는 질문의 답은 늘 log₂N 근처로 수렴하기 때문에, 이런 구조를 가진 알고리즘은 예외 없이 O(log N)의 시간복잡도를 가지게 됩니다.

---

마무리

정리해보면, O(log N)은 대략 다음과 같은 흐름을 거쳐서 나오는 결과입니다.

1. 어떤 값(혹은 범위, 개체 수)이 매 단계마다 절반(또는 일정 비율)씩 줄어듭니다.
2. 이걸 "몇 단계 만에 1 이하(혹은 원하는 조건)에 도달하는가"를 구하는 문제로 바꿉니다.
3. 지수 방정식(2ʸ > N)이 나오고, 이걸 풀기 위해 로그를 취하면 Y > log₂N이라는 결과가 나옵니다.

박테리아 소멸 문제와 이진 탐색은 겉보기엔 완전히 다른 이야기 같지만, "매번 절반으로 줄인다"는 뼈대는 똑같아서 결국 같은 O(log N)에 도달하게 됩니다. 이렇게 패턴으로 기억해두면, 나중에 새로운 문제를 만났을 때도 "이거 절반씩 줄여나가는 구조네, O(log N)이겠다"라고 훨씬 빠르게 감을 잡을 수 있습니다.