알고리즘에서 log n과 n log n은 무슨 뜻일까?

많은 알고리즘 문제에서 시간복잡도로 O(log n)이나 O(n log n)을 자주 보게 됩니다.
처음 접하면 log는 도대체 뭐지? 싶지만, 알고 보면 아주 단순한 개념입니다.
이 글에서는 로그의 개념부터 O(log n)과 O(n log n)의 차이를 실제 알고리즘과 함께 쉽게 설명해 드리겠습니다.

---

1. 로그(log)란?

✔️ 정의

로그는 "몇 번 곱해야 이 수가 되나요?"라는 질문입니다.

예를 들어,

2 × 2 × 2 = 8 → log₂(8) = 3
10 × 10 × 10 = 1000 → log₁₀(1000) = 3

즉, log₂(8)은 2를 몇 번 곱해야 8이 되는지를 묻습니다 → 정답은 3입니다.

---

2. 알고리즘에서 log n은 log₂(n)

❗ 주의

수학에서는 log n을 log₁₀(n)으로 보는 게 일반적이지만,
알고리즘에서는 항상 log₂(n), 즉 밑이 2인 로그를 기본으로 합니다.

왜냐하면 컴퓨터는 2진수(Binary)를 쓰고,
많은 알고리즘이 데이터를 반씩 나누며 처리하기 때문입니다.

---

3. O(log n)이란?

개념

• 입력 크기 n을 반씩 줄여가며 처리하는 구조

• 탐색 범위가 계속 절반이 되는 알고리즘

대표 예시

• 이진 탐색 (Binary Search)

• 힙에서 삽입/삭제

• 균형 이진 트리에서 삽입/검색

예

n = 1024일 때 log₂(n) = 10
→ 단 10번만 비교하면 결과에 도달

---

4. O(n log n)이란?

개념

• 전체 데이터를 n개 모두 훑으면서,
  각 원소마다 log n만큼 추가 작업이 들어가는 구조

대표 예시

• 병합 정렬 (Merge Sort)

• 힙 정렬 (Heap Sort)

• 우선순위 큐 정렬

• 세그먼트 트리 계산

예

n = 1024
→ log₂(n) = 10
→ 1024 × 10 = 약 10,000번 작업 → O(n log n)

---

5. 차이점 비교표

---

6. 한 줄 정리

O(log n): 반씩 줄이며 찾는다
O(n log n): 전체를 보되, 그 안에서 log n 반복이 있다

---