시간 복잡도는 입력 크기 n이 커질 때 알고리즘이 얼마나 더 많은 일을 하는지 설명하는 방법입니다. Big-O는 그 증가율을 표현하는 표기법입니다. 예를 들어 배열을 한 번 훑으면 O(n), 이중 loop로 모든 쌍을 비교하면 O(n²), binary search는 O(log n)으로 볼 수 있습니다.
Big-O는 정확한 실행 시간을 말하는 것이 아니라 입력이 커질 때의 성장 경향을 보는 것입니다. 그래서 상수나 작은 항은 보통 생략하고 가장 지배적인 항을 남깁니다.
꼬리질문
조금 더 깊게 물어본다면
답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.
O(1)은 정말 항상 한 번에 끝난다는 뜻인가요?
정확히 한 번이라는 뜻이 아니라 입력 크기와 무관하게 일정한 시간에 가깝다는 뜻입니다. hash table lookup은 평균 O(1)이라고 말하지만 collision에 따라 달라질 수 있습니다.
상수 시간이란 입력 증가에 비례해 커지지 않는다는 의미입니다.
O(log n)은 왜 빠르다고 하나요?
입력을 매번 일정 비율로 줄이기 때문입니다. binary search는 탐색 범위를 절반씩 줄이므로 입력이 크게 늘어도 단계 수는 천천히 증가합니다.
정렬된 데이터라는 전제도 함께 필요합니다.
최악, 평균, 최선 시간 복잡도는 어떻게 다른가요?
최선은 가장 운 좋은 경우, 최악은 가장 나쁜 경우, 평균은 일반적인 입력 분포에서의 기대 비용입니다. 같은 알고리즘도 어떤 기준으로 보느냐에 따라 복잡도가 다를 수 있습니다.
시간복잡도는 최악, 평균, amortized 중 어떤 기준인지에 따라 달라질 수 있습니다.
공간 복잡도도 봐야 하나요?
네. 시간만 빠르고 memory를 지나치게 많이 쓰면 문제가 될 수 있습니다. 추가 배열, recursion stack, cache 저장소 등이 공간 복잡도에 영향을 줍니다.
시간과 공간의 trade-off를 같이 보는 것이 좋습니다.
부가 설명
for (const item of items) { console.log(item);}
입력 길이만큼 한 번 실행되므로 O(n)입니다.
for (const a of items) { for (const b of items) { compare(a, b); }}
모든 쌍을 비교하면 O(n²)에 가깝습니다.
Big-O는 실제 성능의 전부는 아닙니다. O(n) 알고리즘이 작은 입력에서는 O(log n) 알고리즘보다 빠를 수도 있고, cache locality나 I/O 같은 요인이 중요할 수도 있습니다.
하지만 입력이 커질 때 병목을 예측하고 알고리즘을 비교하는 공통 언어로 유용합니다.
한 줄 정리
Big-O는 입력 크기가 커질 때 알고리즘의 실행 비용이 어떤 속도로 증가하는지 표현하는 표기법입니다.