알고리즘의 성능을 표현할 때 O(n), O(log n)과 같은 시간 복잡도를 사용한다.
시간 복잡도는 데이터의 크기가 증가했을 때 필요한 연산이 얼마나 증가하는지를 나타낸다.
예를 들어 데이터가 10개일 때는 두 알고리즘의 차이가 크지 않을 수 있다.
하지만 데이터가 100만 개, 1억 개처럼 많아지면 O(n)과 O(log n)의 차이는 매우 커진다.
1. O(n)이란
O(n)은 데이터의 개수에 비례해서 연산 횟수가 증가하는 시간 복잡도이다.
데이터가 10개라면 최대 약 10번, 100개라면 최대 약 100번을 확인하는 식이다.
데이터 10개
→ 약 10번
데이터 100개
→ 약 100번
데이터 1,000개
→ 약 1,000번
대표적인 예가 순차 탐색이다.
int[] numbers = {3, 7, 10, 15, 20};
for (int number : numbers) {
if (number == 20) {
break;
}
}
20을 찾기 위해 앞에서부터 하나씩 확인한다.
3 확인
↓
7 확인
↓
10 확인
↓
15 확인
↓
20 확인
찾으려는 값이 마지막에 있으면 모든 데이터를 확인해야 한다.
따라서 데이터가 n개라면 최대 n번 정도의 비교가 필요하다.
O(n)
이 된다.
2. O(n)을 실생활로 생각해보면
100만 페이지짜리 전화번호부가 있다고 생각해보자.
그런데 전화번호부가 아무런 순서 없이 섞여 있다.
Kim
Lee
Park
Choi
...
특정 사람을 찾으려면 첫 페이지부터 하나씩 확인해야 한다.
1번째 확인
↓
2번째 확인
↓
3번째 확인
↓
...
↓
1,000,000번째 확인
운이 좋으면 빨리 찾을 수도 있지만 최악의 경우 100만 개를 모두 확인해야 한다.
이것이 O(n)에 가까운 방식이다.
3. O(log n)이란
O(log n)은 한 번 연산할 때마다 확인해야 하는 데이터의 범위를 크게 줄이는 방식이다.
대표적인 예가 이진 탐색 Binary Search이다.
정렬된 숫자가 있다고 해보자.
1 2 3 4 5 6 7 8
여기에서 7을 찾는다고 해보자.
처음부터 하나씩 확인하는 대신 가운데 값을 확인한다.
1 2 3 4 | 5 | 6 7 8
↑
7은 5보다 크다.
그러면 왼쪽 절반은 확인할 필요가 없다.
6 7 8
다시 가운데를 확인한다.
6 | 7 | 8
↑
7을 찾았다.
전체 데이터를 모두 확인하지 않고 몇 번의 비교만으로 원하는 값을 찾았다.
4. O(log n)을 실생활로 생각해보면
이번에는 사전에서 단어를 찾는 상황을 생각해보자.
사전에는 단어가 알파벳 순서대로 정렬되어 있다.
Spring이라는 단어를 찾는다고 해보자.
첫 페이지부터 하나씩 확인할 필요가 없다.
먼저 사전의 가운데를 펼친다.
전체 사전
↓ 절반 확인
앞쪽 절반 | 뒤쪽 절반
찾으려는 단어가 뒤쪽에 있다는 것을 알았다면 앞쪽 절반은 전부 버릴 수 있다.
다시 남은 부분의 가운데를 확인한다.
남은 절반
↓
다시 절반 제거
이 과정을 반복한다.
1,000,000개
↓
500,000개
↓
250,000개
↓
125,000개
↓
62,500개
↓
31,250개
↓
...
↓
1개
한 번 확인할 때마다 탐색 범위가 절반으로 줄어든다.
이런 방식이 O(log n)이다.
5. 왜 log가 나올까
이진 탐색에서는 한 번 비교할 때마다 데이터의 절반을 제거한다.
n
↓
n / 2
↓
n / 4
↓
n / 8
↓
...
↓
1
100만 개의 데이터를 계속 절반으로 나눠보면 다음과 같다.
1,000,000
500,000
250,000
125,000
62,500
31,250
15,625
7,812
3,906
1,953
976
488
244
122
61
30
15
7
3
1
약 20번 정도 절반으로 나누면 1개까지 줄어든다.
그래서
log₂(1,000,000)
≈ 19.93
이고 대략 20번의 연산이면 된다.
6. 데이터가 100만 개라면
데이터가
n = 1,000,000
개 있다고 해보자.
O(n) 알고리즘은 최악의 경우 데이터 전체를 확인한다.
약 1,000,000번
반면 O(log n)은 매번 탐색 범위를 절반씩 줄인다.
log₂(1,000,000)
≈ 20
따라서 대략 비교하면 다음과 같다.
| 시간 복잡도 | 100만 개 데이터에서 필요한 연산 |
|---|---|
| O(n) | 약 1,000,000번 |
| O(log n) | 약 20번 |
차이는 약
1,000,000 ÷ 20
= 50,000
이다.
단순한 연산 횟수 모델로 보면 약 5만 배의 차이가 나는 셈이다.
다만 Big O는 실제 프로그램의 정확한 실행 횟수나 실행 시간을 의미하는 것은 아니다.
CPU, 메모리 접근, 구현 방식과 같은 여러 요소가 실제 성능에 영향을 준다.
여기서 100만 번과 20번은 시간 복잡도의 증가 차이를 이해하기 위한 대략적인 비교이다.
7. 데이터가 커질수록 차이가 커진다
데이터가 적을 때는 차이가 크게 느껴지지 않을 수 있다.
| 데이터 개수 | O(n) | O(log₂ n) |
|---|---|---|
| 10 | 약 10 | 약 4 |
| 100 | 약 100 | 약 7 |
| 1,000 | 약 1,000 | 약 10 |
| 1,000,000 | 약 1,000,000 | 약 20 |
| 1,000,000,000 | 약 1,000,000,000 | 약 30 |
O(n)은 데이터가 증가한 만큼 연산도 계속 증가한다.
1,000
↓
1,000,000
데이터 1,000배 증가
연산도 약 1,000배 증가
반면 O(log n)은 데이터가 크게 증가해도 연산 횟수가 매우 천천히 증가한다.
데이터 1,000개
→ 약 10번
데이터 1,000,000개
→ 약 20번
데이터 1,000,000,000개
→ 약 30번
이것이 O(log n)의 가장 큰 장점이다.
8. O(log n)이 항상 O(n)보다 좋은 것은 아니다
시간 복잡도만 보면 O(log n)이 O(n)보다 효율적이다.
하지만 모든 상황에서 O(log n) 알고리즘을 사용할 수 있는 것은 아니다.
예를 들어 이진 탐색을 사용하려면 기본적으로 데이터가 정렬되어 있어야 한다.
정렬되지 않은 데이터
8 1 5 3 9 2
→ 가운데 값을 봐도
어느 방향으로 가야 할지 판단할 수 없음
반면 정렬되어 있다면
1 2 3 5 8 9
↑
찾는 값이 더 크다
→ 오른쪽만 탐색
이 가능하다.
즉 O(log n)의 성능을 얻기 위해서는 그에 맞는 자료구조나 조건이 필요하다.
9. 자료구조에서도 볼 수 있다
Java 컬렉션에서도 비슷한 차이를 볼 수 있다.
예를 들어 ArrayList에서 특정 값이 존재하는지 contains()로 찾으면 일반적으로 앞에서부터 값을 비교해야 한다.
ArrayList.contains()
A
↓
B
↓
C
↓
D
↓
찾음
O(n)
반면 TreeMap이나 TreeSet은 내부적으로 균형 Tree 구조를 사용한다.
50
/ \
25 75
/ \ / \
한 번 비교할 때마다 탐색할 범위를 줄일 수 있기 때문에 검색, 삽입, 삭제가 일반적으로
O(log n)
이다.
그래서 시간 복잡도는 자료구조를 선택할 때도 중요한 기준이 된다.
10. 핵심 정리
O(n)은 데이터의 개수가 증가한 만큼 연산 횟수도 증가한다.
O(n)
1,000개
→ 약 1,000번
1,000,000개
→ 약 1,000,000번
O(log n)은 한 번 연산할 때마다 탐색 범위를 크게 줄인다.
O(log n)
1,000개
→ 약 10번
1,000,000개
→ 약 20번
100만 개의 데이터를 기준으로 비교하면
O(n)
→ 약 1,000,000번
O(log n)
→ 약 20번
으로 매우 큰 차이가 발생한다.
한 문장으로 정리하면
O(n)은 데이터가 증가하는 만큼 연산도 증가하지만, O(log n)은 매 연산마다 탐색 범위를 크게 줄이기 때문에 데이터가 많아질수록 성능 차이가 크게 벌어진다.