O(n) VS O(log n)

📌개요

개발자라면 ‘시간 복잡도’라는 용어를 자주 접한다. 하지만 막상 O(n)과 O(log n)의 차이가 얼마나 큰 영향력을 가지는지 체감하기 어려운 것 같다.

O(n)과 O(log n)의 성능 차이를 실생활 예시로 알아보고 데이터의 크기가 1백만 개 이상일 때 각각 대략 몇 번의 연산이 필요한지 비교 분석해보자.

📌내용

일상 속의 시간 복잡도

만만한 “전화번호부에서 이름 찾기”를 예로 들어보자.

O(n) 순차 검색

• 처음부터 끝까지 하나씩 확인하는 방식
• 최악의 경우 모든 ㅔ이지를 뒤져야 한다.
• 데이터가 2배 증가하면 검색 시간도 2배 증가한다.

O(log n) 이진 검색

• 가운데를 펴서 앞/뒤를 결정하는 방식
• 매 단계에서 검색 범위가 절반으로 줄어든다.
• 데이터가 2배 증가해도 검색 시간은 1단계만 더 필요하다.

수치로 보는 차이

• 1백만 개 이상의 데이터를 처리한다고 했을 때 무려 52,000배 이상의 효율 차이를 보인다.
  • O(n)은 1,048,576회 연산
  • O(log n)은 단 20회 연산

데이터 크기	O(n) 연산 횟수	O(log₂n) 연산 횟수	차이 비율
16	16	4	4:1
1,024	1,024	10	102:1
1,048,576	1,048,576	20	52,429:1

알고리즘 선택의 기준

O(n)이 나은 경우

• 데이터 규모가 매우 작을 때
• 구현이 간단해야 할 때
• 한 번만 실행되는 스크립트

O(log n)이 필수인 경우

• 대규모 시스템의 핵심 기능
• 실시간 처리 필요한 서비스
• 빈번하게 호출되는 API

🎯결론

성능 분석 자료를 정리하기 위해 자료를 찾아보면서 이미 많은 사람들이 질문했던 “어떻게 하면 선형 시간을 로그 시간으로 끌어올릴 수 있을까?” 같은 고민들을 엿볼 수 있었다.

왜 기업들 기술 인터뷰에서 O(log n) 알고리즘 구현을 강조하는지, 왜 데이터베이스에 인덱스를 생성하는지 같은 현업에서 마주하는 많은 질문들에 대한 근본적인 답을 얻을 수 있었다.

⚙️EndNote

사전 지식

• 시간 복잡도: 알고리즘이 입력 크기에 따라 어떻게 수행 시간이 증가하는지 나타내는 척도
• Big-O 표기법: 최악의 경우를 고려한 알고리즘의 상한 성능 표현
• 로그 함수: 지수 함수의 역함수, 알고리즘에서 문제 크기를 지속적으로 전반으로 나누는 과정에서 나타난다.

더 알아보기

• 인덱스 설계 전략
  • B-tree 인덱스는 기본적으로 O(log n) 복잡도 제공
  • Composite Index 설계 시 컬럼 순서가 로그 효율성에 영향
• 캐싱과의 조합
  • O(log n) 알고리즘 + LRU 캐시 = O(1)에 근접하는 성능
    • LRU: Least Recently Used
    • LFU: Least Frequently Used
• 점근 표기법의 한계: 최악의 경우만 보는 Big-O의 단점
• 분할 정복 알고리즘의 공간 복잡도 트레이드 오프

참고 자료

• Difference between O(n) and O(log(n)) - which is better and what exactly is O(log(n))
• Big-O Cheat Sheet: https://www.bigocheatsheet.com/