시간 복잡도와 빅-O

시간 복잡도(time complexity)는 입력 크기 n이 커질 때 알고리즘의 실행 단계 수가 얼마나 빨리 늘어나는지 나타낸 것이다. 같은 일을 하는 알고리즘이라도 n이 커지면 속도 차이가 수천 배로 벌어지므로, 알고리즘을 고를 때 가장 먼저 본다. 실기 시험은 빅-O 표기법(big-O notation)의 빠르기 순서와 각 복잡도의 대표 알고리즘을 짝짓게 한다.

빅-O 표기법

빅-O 표기법은 실행 단계 수를 n의 식으로 쓰되, 가장 빨리 커지는 항만 남기고 계수는 버린 표기다. 예를 들어 단계 수가 3n² + 5n + 2이면 O(n²)라고 쓴다. n이 충분히 크면 n² 항이 나머지를 압도하기 때문이다. 보통 가장 나쁜 입력, 곧 최악의 경우를 기준으로 쓴다. 그래서 컴퓨터 성능이나 언어와 관계없이 알고리즘끼리 비교할 수 있다.

복잡도 순서와 대표 알고리즘

위에서 아래로 갈수록 느려진다. 표에 나오는 삽입 정렬(insertion sort)·선택 정렬(selection sort)·버블 정렬(bubble sort)·퀵 정렬(quick sort)·병합 정렬(merge sort)·힙 정렬(heap sort)은 정렬 문서에서 다룬다. 이진 검색(binary search)은 아래에서 설명한다.

표기	이름	대표 예
O(1)	상수 시간	배열 인덱스 접근, 스택 push·pop
O(log n)	로그 시간	이진 검색
O(n)	선형 시간	순차 검색, 1중 반복문
O(n log n)	선형 로그 시간	병합 정렬, 힙 정렬, 퀵 정렬 평균
O(n²)	제곱 시간	삽입·선택·버블·셸(Shell) 정렬, 퀵 정렬 최악, 2중 반복문
O(2ⁿ)	지수 시간	재귀(recursion)로 구한 피보나치 수

O(1)은 n과 관계없이 단계 수가 일정하다. 스택의 맨 위에 넣고 빼는 일은 데이터가 아무리 많아도 한 번이면 된다.

O(log n)은 한 단계마다 남은 범위가 절반으로 줄어드는 경우다. 이진 검색은 정렬된 배열의 가운데 값과 비교해 절반을 버린다. n이 16이면 4번, 100이면 7번 만에 범위가 1로 줄어든다.

O(n²)은 반복문 안에 또 반복문이 있는 경우다. 바깥이 n번, 안쪽이 최대 n번 돌면 단계 수가 n²에 비례한다. 안쪽 반복이 i부터 n까지만 돌아도 n(n+1)/2번이라 역시 O(n²)이다. n이 10이면 55번이다.

O(2ⁿ)은 한 번 호출이 자신을 두 번 부르는 재귀에서 나온다. 피보나치 수를 fib(n-1) + fib(n-2)로 그대로 구하면 같은 값을 계속 다시 계산해 호출 수가 지수적으로 늘어난다. fib(5) 하나에 호출이 15번 일어난다.

최선·평균·최악

같은 알고리즘도 입력에 따라 단계 수가 다르다. 퀵 정렬은 평균 O(n log n)이지만 최악은 O(n²)이다. 삽입 정렬은 이미 정렬된 입력에서는 O(n)이지만 최악은 O(n²)이다. 그래서 문제가 "최악의 시간 복잡도"를 묻는지 "평균"을 묻는지 먼저 확인해야 한다. 시험은 최악의 시간 복잡도로 묻는 일이 많아, 퀵 정렬을 O(n²) 쪽에 넣어 답하게 하기도 한다. 셸 정렬(shell sort)은 삽입 정렬을 멀리 떨어진 원소끼리 먼저 하는 개량형인데, 처음 제안된 간격 방식으로는 최악이 O(n²)이다.

시험 포인트

• 빠른 순서: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
• 이진 검색 → O(log n). 순차 검색 → O(n).
• 병합·힙 정렬 → O(n log n). 삽입·선택·버블·셸 → O(n²). 퀵 정렬 최악 → O(n²).
• 재귀 피보나치 → O(2ⁿ).
• 빅-O는 최고차항만 남기고 계수를 버린다.