[자료구조] O(n)과 O(log n)의 성능 차이

1. O(n)의 예시

실생활 예시:
책장에 100만 권의 책이 꽂혀 있다고 가정하자.
특정 책을 찾기 위해 1번 책부터 하나씩 차례대로 확인하는 방식이다.

특징

• 운이 좋으면 첫 번째 책에서 바로 찾는다.
• 운이 나쁘면 100만 번째 책까지 확인해야 한다.
• 책이 1,000만 권이면?
  • 확인해야 할 책 수도 10배 증가한다.

즉,데이터 개수(n)에 비례해서 탐색 시간이 1:1로 증가한다.
→ 이것이 선형 시간 O(n)

---

2. O(log n)의 예시

실생활 예시:
1부터 100만까지의 숫자 중 하나를 맞히는 게임을 생각하자.
가장 효율적인 전략은:

1. 중간값인 50만을 먼저 질문한다.
2. 정답이 50만보다 큰지/작은지에 따라 범위를 절반으로 줄인다.
3. 남은 범위에서도 또 절반, 또 절반… 반복

특징

• 매 탐색마다 남은 후보가 절반으로 줄어든다.
• 100만 개라도 많아야 약 20번 정도 물어보면 된다.
• 데이터 개수가 2배, 10배 늘어나도 탐색 횟수는 조금씩만 증가한다.

즉,O(log n)은 n이 커져도 증가율이 매우 느린 알고리즘이다.

---

3.O(n) vs O(log n) 비교 테이블

구분	O(n) (선형 탐색)	O(log n) (이진 탐색)
실생활 비유	책 100만 권을 앞에서부터 한 권씩 확인	숫자를 절반씩 제거하며 맞히는 Up/Down 게임
처리 방식	모든 데이터를 차례대로 확인	탐색 범위를 절반으로 나누며 진행
최악의 경우 연산 수 (n=1,000,000)	약 1,000,000번	약 20번
데이터가 10배 증가하면	연산 수도 10배 증가	연산 횟수는 1~2번만 증가
시간 증가 특성	n에 비례하여 증가	매우 느리게 증가
사용 예	정렬되지 않은 배열 탐색, 전체 순회	정렬된 배열 탐색
장점	구현이 단순	매우 높은 성능, 대규모 데이터에 강함
단점	데이터가 클수록 속도 급격히 악화	전제 조건(정렬, 구조 유지) 필요