빅오(Big-O) 표기법 - log n vs n log n 차이 완벽 비교

알고리즘 시간 복잡도를 공부하다 보면 log n 과 n log n 이 가장 헷갈린다.
둘 다 로그가 들어가 있어서 비슷해 보이지만, 의미와 성능 차이는 매우 크다.

이번 글에서는 두 복잡도의 차이를 직관 + 예시 중심으로 정리해본다.

---

1. 한 문장으로 요약하면

• log n : 문제를 계속 반으로 줄여가며 처리
• n log n : n개를 모두 처리하되, 각 처리가 매우 빠름

---

2. log n 이란?

🔹 개념

log n 은

데이터를 처리할 때마다 범위가 절반으로 줄어드는 구조를 의미한다.

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

이때 필요한 처리 횟수가 바로 log n 이다.

---

🔹 예시: 이진 탐색

• 정렬된 배열에서 값 하나를 찾음
• 탐색할 때마다 절반을 버림

데이터 1,000,000개 → 약 20번 비교

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

---

3. n log n 이란?

🔹 개념

n log n 은 다음 구조를 가진다.

n번 반복 × (각각 log n만큼의 작업)

즉,

• 전체 데이터는 전부 한 번씩 처리해야 하고
• 각 처리 과정은 로그 시간으로 빠르게 진행된다.

---

🔹 예시: 정렬 알고리즘

대표적인 n log n 알고리즘:

• Merge Sort
• Heap Sort
• Quick Sort (평균)

정렬을 기준으로 보면:

• 데이터 개수만큼 비교가 필요 → n
• 비교 과정은 계속 반씩 쪼개짐 → log n

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

---

4. 직관적인 비유로 비교

📦 log n

상자를 계속 반으로 쪼개서
목표 상자 하나를 찾는 과정

• 쪼개는 횟수만 중요

---

📦 n log n

상자 n개를 전부 정리하는데
각 상자를 매우 빠른 방법으로 정리

• 상자 개수(n) × 정리 속도(log n)

---

5. 숫자로 보면 차이가 확 난다

n	log₂ n	n log₂ n
10	3	30
1,000	10	10,000
1,000,000	20	20,000,000

➡ log n 과 n log n 은 차원이 다르다

---

6. 언제 어떤 복잡도가 나올까?

log n 이 나오는 경우

• 탐색 대상이 하나
• 처리할 때마다 범위가 절반으로 감소

예)

• 이진 탐색
• 균형 이진 트리 탐색

---

n log n 이 나오는 경우

• 전체 데이터를 모두 처리해야 함
• 내부 처리 과정이 로그 구조

예)

• 정렬
• 분할 정복 알고리즘

---

7. 한 줄 정리

**log n 은 “찾는 과정”**이고
**n log n 은 “정리하는 과정”**이다.

그리고 성능 관계는 다음과 같다.

log n ≪ n log n ≪ n²