좋은 개발자가 되기 위해서는 문제 해결 능력이 필수적입니다. 제가 쓴 책 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"에서는 다양한 문제 해결 기법과 예제들을 소개합니다.

대문자 O 표기법과 퀵 정렬의 시간 복잡도

[처음으로] [모든 글 보기] [같은 카테고리의 글 보기: 알고리즘]


대문자 O 표기법은 가장 널리 사용되는 알고리즘의 시간 복잡도 표기 방법이다. 그 자세한 정의는 수학적으로 약간 까다롭지만, 흔히 잊지 않고 기억하는 것은 이것이다:

대문자 O 표기법은 수행 시간의 상한을 나타낸다.

이 말이 틀린 말은 아니지만, 이 정의는 혼란을 가져오기 쉽다. 바로 다음과 같은 질문이 나오는 배경이 되기 때문이다.

"우리가 흔히 $O(n\lg n)$ 정렬이라고 말하는 퀵 정렬의 경우 Worst Case는 $O(n^2)$이 된다. 교수님이 설명하시길 알고리즘의 시간 복잡도는 Worst Case를 기준으로 측정한다고 얘기했는데 퀵 정렬은 Average Case를 기준으로 할 때만 $O(n\lg n)$이 되는 것인데, 그렇다면 과연 퀵 정렬을 $O(n \lg n)$ 정렬이라고 부르는 것이 맞는가?"

듣고 보면 그럴 듯 하다. (구현 방법에 따라 다르지만) 퀵 정렬은 최악의 경우 $n^2$에 비례하는 시간이 걸리는데, 왜 $O(n \lg n)$이라고 쓰는 걸까?

이 직관이 왜 틀렸을까? 대문자 O 표기법은 그냥 정확하게 쓰자면 너무 길고 복잡한 함수를 "적당히 정확하게" 표현하는 방법일 뿐, 최악의 경우/평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이기 때문이다.

잘 알고 있듯이, 알고리즘의 시간 복잡도는 입력의 크기에 대한 함수로 정의된다. 이 때 어떤 입력이 주어지느냐에 따라서 알고리즘의 수행 시간이 변한다면, 우리는 각각 최선의 경우, 평균적인 경우, 그리고 최악의 경우를 흔히 계산하곤 한다. 이 때 이 세 수행 시간은 세 개의 각각 다른 함수이다. 퀵 정렬의 평균적인 경우의 시간 복잡도는 $n\lg n$이 중간에 포함된 복잡한 함수이고, 최악의 경우의 시간 복잡도는 $n^2$가 어딘가에 포함된 복잡한 함수이다. $O(n\lg n)$과 $O(n^2)$는 이들을 간단하게 표현하기 위한 방법일 뿐이다.

따라서 앞에서 말한 질문의 경우, "알고리즘의 (최악/최선/평균) 경우의 시간 복잡도는 그 상한을 대문자 O 표기법으로 쓴다"는 기준을 "알고리즘의 시간 복잡도는 그 상한을 기준으로 쓴다"라고 혼동해서 나온 질문이라고 할 수 있다.

왜 퀵 소트에 대해서만 이런 착각을 하게 되는 것일까? 알고리즘 입문 시간에 처음 배우는 간단한 알고리즘의 경우 기대치와 최악의 수행 시간이 다르지 않다. 예를 들면 선택 정렬 같은 경우가 그러하다. 선택 정렬은 어떤 배열이 주어지더라도 $\frac{N\cdot(N-1)}{2}$번의 비교를 수행하게 된다. 따라서 최악의 경우와 평균적인 경우, 최선의 경우 시간 복잡도는 모두 $O(n^2)$로 쓸 수 있다. 따라서 퀵 정렬을 배우는 것은 잘못된 착각을 눈치챌 첫 번째 기회인 셈이다.

처음에 설명한 대문자 O 표기법에 대한 문장을 고쳐 쓰면 다음과 같을 것이다.

대문자 O 표기법은 주어진 (최악/최선/평균) 경우의 수행 시간의 상한을 나타낸다.


[처음으로] [모든 글 보기] [같은 카테고리의 글 보기: 알고리즘]

2012 구종만