[Big-O] 헷갈리기 쉬운 개념

Big-O Notation | Notion

 

• Big-O의 구체적인 의미: 함수가 충분히 큰 입력에서 어떤 기준 함수보다 빠르게 커지지 않는다는 상한(upper limit)을 표현한다. 상수 계수와 낮은 차수 항을 숨긴다.
• 로그 밑의 차이도 상수 배 차이이므로 보통 중요하지 않다.
• Omega는 하한, Theta는 상한과 하한이 같은 tight bound를 의미한다. “이 알고리즘은 O(n)”이라는 말은 n보다 빨리 커지지 않는다는 상한을 말할 뿐, 정확히 n번 돈다는 뜻이 아니다.
• O log(n)은 입력을 절반씩 줄이는 구조에서 자주 나온다. 정렬된 배열의 이분 탐색은 한 번 비교할 때마다 남은 후보가 절반으로 줄어든다.
• O nlog(n)은 비교 기반 정렬에서 자주 등장한다.
• O (2^n)은 입력 하나가 늘 떄 경우의 수가 두 배가 되는 구조다.
• 코드 리뷰에서 “이 API는 O(n^2)입니다”라고 말할 때는 입력 목록이 커질수록 비교 횟수가 제곱으로 증가한다는 구체적인 주장이어야 한다.
• Big-O는 DB 인덱스, 네트워크 지연, lock 대기, serialization 비용을 모두 설명하지 않는다. O log(n)인 DB index scan도 디스크 I/O나 캐시 hit ratio에 따라 실제 시간은 달라진다.
• SLA가 있는 API에서는 “현재 100건에서는 괜찮다”보다 “10,000건에서 성장률이 어떻게 되는가”가 더 중요하다. Big-O는 데이터가 커질 때 위험해지는 코드를 찾는 도구다.
• O(n) 코드가 O(log n) 코드보다 항상 빠르거나 느린 것은 아니다.