O(n)과 O(log n)

알고리즘의 시간 복잡도(실행 속도)와 공간 복잡도(메모리 사용량)을 수학적으로 표현하는 방법인 Big-O Notation 중 O(n)과 O(log n)에 대하여 알아본다.

---

O(n)과 O(log n)의 성능 차이

실생활에서의 예시 - 도서관에서 책 찾기

1) 모든 책을 하나씩 확인하는 경우 O(n)

• n개의 책이 있는 도서관에서 처음부터 끝까지 한 권씩 확인하며 원하는 책을 찾는 경우 O(n)번 찾아야 한다.
  (Big O Notation은 최악의 상황을 가정하기에 끝까지 찾는 O(n)번 실행)
• 정렬되지 않은 도서관에서 책을 찾는다면 어쩔 수 없이 이 방법을 사용해야 함
• 1,000,000권의 책에서 찾는 경우 최대 1,000,000번 확인해야 함

2) 정렬된 도서관에서 절반씩 나누어 찾는 경우 O(log n)

• 책이 가나다순으로 정렬되어 있다면, 원하는 책의 제목과 비교하며 절반씩 영역을 줄여가며 탐색
• 찾는 범위에서 중간 책의 제목을 확인하여 앞쪽에 찾는 책이 있는지,
  뒤쪽에 찾는 책이 있는지 확인 후 절반씩 줄여가며 탐색
• 책이 16권 있는 경우 확인 횟수 : O(log 4)
  1번: 16권 → 8권
  2번: 8권 → 4권
  3번: 4권 → 2권
  4번: 2권 → 1권
• 1,000,000권의 책에서 찾는 경우 최대 20번을 확인해야 함

---

크기가 1,000,000개의 데이터를 O(n)과 O(log n)으로 연산하는 경우

• O(n) -> 1,000,000
• O(log n) -> 20