홍라이프 계산기빅오 증가율 계산기 쉽게 이해하기 — 개념과 원리
빅오(Big-O) 표기법은 입력 크기 n이 커질 때 알고리즘의 작업량이 얼마나 빨리 늘어나는지를 나타냅니다. 이 계산기는 자주 쓰는 여섯 가지 증가 차수를 입력한 n에 대한 연산 횟수로 바꾸고, 초당 연산 속도로 나누어 실제 걸리는 시간으로 보여 줍니다. 어떤 알고리즘이 현실적으로 쓸 만하고 어떤 것이 감당할 수 없는지 한눈에 비교할 수 있습니다.
계산 방법
- 연산 횟수: log₂ n, n, n·log₂ n, n², n³, 2ⁿ
- 걸리는 시간 ≈ 연산 횟수 ÷ 초당 연산 수
- 시간은 크기에 따라 µs, ms, s, 일, 년으로 표시하며, n이 1,000을 넘으면 2ⁿ은 '천문학적(astronomical)'으로 표시합니다.
빅오와 마찬가지로 상수배와 낮은 차수 항은 무시합니다.
원리
n이 충분히 크면 가장 빨리 커지는 항이 나머지를 압도하므로 빅오는 그 항만 남깁니다. n을 두 배로 늘리면 log n 알고리즘은 한 단계만 늘고, O(n)은 2배, O(n²)는 4배, O(n³)는 8배가 되며, O(2ⁿ)은 작업량이 제곱이 됩니다. 초당 10⁹회라는 속도는 최신 CPU 코어 하나의 대략적인 규모일 뿐이며, 실제 코드는 메모리 접근이나 분기, 언어 처리 비용 때문에 이보다 훨씬 적은 연산을 처리하는 경우가 많습니다.
예제 풀이
- 입력값: n = 1,000,000, 속도 = 초당 10⁹회입니다.
- O(log n): log₂ 10⁶ ≈ 19.93회이므로 약 0.0199 µs입니다.
- O(n): 10⁶회이므로 1 ms입니다.
- O(n log n): 10⁶ × 19.93 ≈ 19,930,000회이므로 19.9 ms입니다.
- O(n²): 10¹²회이므로 1,000 s(약 17분)입니다.
- O(n³): 10¹⁸회, 즉 10⁹초이므로 86,400 × 365.25로 나누면 31.7년입니다.
- O(2ⁿ): n이 1,000보다 훨씬 크므로 천문학적입니다.
결과 해석
사용자가 기다리는 작업이라면 1초보다 충분히 짧아야 합니다. n = 10⁶이면 O(n)과 O(n log n)은 여유롭지만 O(n²)는 이미 너무 느리고 O(n³)는 불가능합니다. 초당 10⁸~10⁹회를 기준으로 하면 O(n²)는 n이 대략 10⁴까지, O(n³)는 수백까지, O(2ⁿ)은 30 안팎까지가 현실적인 한계입니다.
흔한 실수
- 빅오를 정확한 실행 시간으로 오해하는 경우입니다. 상수가 큰 O(n log n)은 n이 작을 때 O(n²)보다 느릴 수 있습니다.
- 최악과 평균을 구분하지 않는 경우입니다. 퀵 정렬은 평균 O(n log n)이지만 최악 O(n²)입니다.
- CPU 클럭 수를 연산 속도로 그대로 쓰는 경우입니다.
자주 묻는 질문
빅오에서 로그의 밑은 무엇인가요?
밑이 달라도 상수배 차이일 뿐이라 빅오에서는 구분하지 않습니다. 반씩 나누는 경우가 많아 여기서는 밑 2를 씁니다.
O(n log n)은 O(n)보다 많이 느린가요?
log₂ n배 차이로, 백만 개에서 약 20배, 10억 개에서 약 30배입니다.
O, Θ, Ω는 어떻게 다른가요?
O는 상한, Ω는 하한, Θ는 상한과 하한이 모두 성립하는 정확한 차수입니다.
출처: D. E. Knuth, "Big Omicron and Big Omega and Big Theta", SIGACT News 8(2), 1976 · T. H. Cormen 외, Introduction to Algorithms, MIT Press