다섯 살도 알 수 있게 · 시스템SW
알고리즘 복잡도(Big-O)가 뭐예요?
시간 복잡도와 Big-O 표기법을, 정비공장 규모가 커질 때 일이 얼마나 빨리 늘어나는지 재는 자 이야기로 풀어봤어요.
차가 10대일 땐 괜찮던 일이, 1만 대가 되니 끝나질 않아요.어떤 일은 차가 늘어난 비율보다 시간이 훨씬 더 많이 늘어요.
'차가 늘어난 만큼만 시간이 늘겠지'는 일하는 방법에 따라 틀려요.시간이 늘어나는 정도는 일하는 방법에 따라 완전히 달라요.
Big-O = 차가 많아질 때 일이 얼마나 빨리 느는지 재는 자예요.몇 초라는 숫자 하나가 아니라, 일이 늘어나는 모양을 재는 거예요.
O(1)번호판으로 바로 찾기, 차가 늘어도 시간이 같아요
O(log n)이진트리처럼 매번 후보를 반씩 줄여요
O(n)한 줄로 서서 하나씩 확인해요
O(n²)모든 차끼리 서로 다 비교해요
차 수 n이 커지면 방식별 걸음 수 차이가 확 벌어져요.O(n²)는 걸음 수가 금방 감당 못 할 만큼 커져요.
Big-O는 일이 늘어나는 모양만 재고, 실제 초는 재지 않아요.실제로 몇 초 걸리는지는 장비·상황마다 달라요.
한 줄로
Big-O(시간 복잡도) = 차(자료) 수가 늘어날 때, 해야 할 일이 얼마나 빠르게 늘어나는지 그 '모양'을 재는 자.
시간 복잡도는 입력 크기 n이 커질 때 알고리즘의 실행 시간이 얼마나 빠르게 증가하는지를 나타내는 척도예요. O(1)은 입력 크기와 무관하게 일정하고, O(log n)은 이진 탐색처럼 매번 절반씩 줄어들며, O(n)은 전체를 한 번씩 훑고, O(n²)은 모든 쌍을 비교하는 식으로 n이 커질수록 급격히 느려져요. Big-O는 상수항이나 실제 하드웨어 속도를 무시하고 오직 '증가하는 추세'만 비교하는 표기법이에요.
어른들은 이렇게 불러요
- O(1)
O(1) - 번호판으로 바로 찾기, 늘 똑같은 시간. 입력이 늘어도 시간이 그대로예요.
- O(log n)
O(log n) - 매번 반씩 줄여가는 탐색. 입력이 늘어도 시간은 아주 천천히 늘어나요.
- O(n)
O(n) - 한 줄로 서서 하나씩 확인하기. 시간이 입력 크기에 비례해 늘어나요.
- O(n²)
O(n²) - 모든 차끼리 서로 다 비교하기. n이 커지면 시간이 감당 못 할 만큼 가파르게 늘어요.
- 이진트리 탐색(O(log n)의 예)
Binary Tree Search (an O(log n) example) - 갈림길마다 반씩 줄여가는 선반 지도. O(log n)이 실제로 어떻게 생기는지 여기서 봐요. → 갈림길에서 반씩 줄여가는 선반 지도
- 스택·큐의 push/pop(O(1)의 예)
Stack/Queue push-pop (an O(1) example) - 상자를 쌓거나 줄 세우는 규칙. push/pop·enqueue/dequeue는 보통 O(1)이에요. → 상자는 쌓고, 차는 줄 세우고
- 캐시 적중/미스
Cache Hit/Miss - 찾는 공구가 공구함에 있으면 적중, 없으면 미스. 같은 O(1) 조회도 적중이냐 미스냐로 실제 속도가 갈려요. → 바로 옆에 놓아둔 공구함
- CPU 스케줄링
CPU Scheduling - 리프트에 누가 먼저 올라갈지 정하는 규칙. 순서판을 정렬·검색하는 비용도 이 자로 재요. → 리프트에 누가 먼저 올라갈까
다음 이야기
크기 순서로 차를 세우는 여러 방법 →