빅오(Big-O) 표기법 - 로그(log)란 무엇인가?

알고리즘 시간 복잡도를 공부하다 보면 log n, n log n 같은 표현을 자주 보게 된다.
이때 많은 사람들이 헷갈리는 개념이 바로 **로그(log)**다.

이번 글에서는 수학 공식이 아닌, 직관적인 개념 중심으로 로그를 설명한다.

---

1. 로그를 한 문장으로 말하면

로그(log)는 “몇 번 나눠야 하는가”를 의미한다.

---

2. 예제로 이해하는 로그

다음 수식을 보자.

log₂ 8 = 3

이 뜻은 다음과 같다.

8을 2로 몇 번 나누면 1이 되는가? → 3번

과정을 직접 써보면:

8 → 4 → 2 → 1

총 3번 나누었으므로 log₂ 8 = 3이다.

---

3. 왜 알고리즘에서 로그가 중요한가?

로그가 등장한다는 것은 보통 다음과 같은 구조를 가진다.

• 한 번 처리할 때마다
• 문제 크기가 절반으로 줄어든다

n → n/2 → n/4 → n/8 → ...

이렇게 되면 데이터가 아무리 커도 필요한 처리 횟수는 매우 적다.

예를 들어:

log₂ 1,000,000 ≈ 20

➡ 데이터가 백만 개여도 약 20번만 처리하면 된다.

---

4. log n 이 빠른 이유

다음 두 가지를 비교해보자.

• O(n) : 데이터가 1,000,000개면 1,000,000번 처리
• O(log n) : 데이터가 1,000,000개여도 약 20번 처리

➡ 차이가 압도적으로 크다.

그래서 O(log n) 알고리즘은 매우 빠하다고 평가된다.

---

5. 로그가 사용되는 대표적인 예

🔹 이진 탐색 (Binary Search)

• 정렬된 데이터
• 탐색할 때마다 범위를 절반으로 줄임

➡ 시간 복잡도: O(log n)

---

🔹 트리 탐색 (균형 트리)

• 한 단계 내려갈 때마다 선택지가 절반 수준으로 줄어듦

➡ 시간 복잡도: O(log n)

---

6. 로그의 밑(base)은 중요할까?

알고리즘에서 로그의 밑은 중요하지 않다.

log₂ n
log₁₀ n
log n

모두 O(log n) 으로 표현한다.

왜냐하면 빅오 표기법에서는 상수 차이를 무시하기 때문이다.

---

7. 한 줄 요약

로그(log)는 문제를 반으로 계속 줄일 때 필요한 횟수다.

로그가 보인다면 이렇게 생각하면 된다.

“아, 이 알고리즘은 데이터를 계속 쪼개면서 처리하는구나”