Big-O를 넘어선 하드웨어 캐시 및 데이터 구조 최적화 전략

Context

이론적인 O(log n) 복잡도만으로는 실제 프로덕션 환경의 실행 시간을 보장할 수 없는 한계 존재. 데이터 정렬 비용, Random Access 제약, CPU 캐시 효율성 등의 변수가 실제 성능에 결정적 영향을 미침.

Technical Solution

• O(1) Random Access 보장 여부에 따른 알고리즘 선택으로 Linked List에서의 O(n log n) 성능 저하 방지
• 정렬 비용 O(n log n)과 단일 검색 비용 O(n)의 비교를 통한 Linear Scan 도입 결정
• CPU Cache Line(64 bytes)의 순차적 읽기 특성을 활용하여 소규모 데이터셋(~1,000 elements)에서 Linear Scan 적용
• Integer Overflow 방지를 위한 lo + Math.floor((hi - lo) / 2) 방식의 Mid-point 계산 로직 채택
• 단순 값 탐색을 넘어 Range Query 및 Duplicate Detection 해결을 위한 Lower Bound와 Upper Bound 변형 알고리즘 구현
• Disk I/O 비용 최소화를 위해 Binary Search 대신 Page Size 최적화된 B-tree 구조 활용