자료구조 공부를 했다면 퀵소트가 버블소트보다 빠르다는 사실은 다 알 것이다. 퀵소트의 평균적인 시간복잡도가 O(nlogn) 인데 비해 버블소트는 항상 O(n^2)인 알고리즘이기 때문이다. 그러나 O (big-oh로 발음, asymptotic upper bound, 즉, 상한을 말하는 것이고 때에 따라서 보다 엄밀한 tight bound인 big-theta를 쓰기도 한다)의 수학적인 정의를 들여다보면 맹점을 내포하고 있어서 실제 프로그래밍을 할 때는 주의를 기울여야한다.

수식 때문에 머리가 아프지만, 잠시 O의 엄밀한 수학적 정의를 복습해보면: 주어진 어떤 함수 g(n)에 대해 O(g(n))이라는 함수의 집합을 다음과 같이 표현한다.
쉽게 풀어설명하면, 어떤 알고리즘의 수행 시간이 10000*n^2 - 100*n 로 표현이 된다고 하자. 여기서 n은 데이터의 개수이다. 직관적으로 n^2 항이 있으므로 이 알고리즘은 O(n^2)임을 알 수 있다. 엄밀하게 이 알고리즘이 O(n^2)임을 보이려면 위의 정의에서 적절한 상수 c, k만 고르면 된다. 대략 c, k를 충분히 큰 수로 잡으면 간단히 증명된다. O 표기법은 알고리즘의 전체적인 시간 복잡도를 잘 설명해주지만 방금 말한 c, k로 인해 맹점을 가지고 있다고 볼 수 있다. 어떤 개선한 알고리즘이 O(n)를 가진다고 하더라도 c, k가 아주 큰 숫자라면 O(n^2)인 경우가 더 좋은 경우도 많기 때문이다. 이러한 경우 constant factor 혹은 그냥 오버헤드가 커서 그렇다고 말할 수 있다. 실제 프로그래밍에서 볼 수 있는 문제로 이 맹점에 대해서 알아보자.


C 라이브러리의 qsort의 구현 중 도입부는 아래와 같다.
보다시피 CUTOFF (실험결과로부터 8로 정의되어있다)보다 작은 개수의 데이터가 들어올 때는 그냥 무식한 버블소트나 Insertion Sorting 방법을 이용한다. 왜냐면 퀵소트를 하기 위해서는 이것저것 셋업해야하는 것도 많고 복잡한 컨트롤이 들어가기 때문에, 몇 개 안되는 경우는 for 루프 두번으로 돌리는 것이 더 빠르기 때문이다. 어느 정도 데이터가 있어야 퀵소트가 가지는 오버헤드를 극복할 만큼의 효과를 가지기 때문이다. (다 아시는 당연한 얘기를 해서 죄송합니다...)

위의 qsort 같은 경우는 이렇게 if문 하나로 매우 간단히 퀵소트를 정말로 쓸지 아닐지를 결정할 수 있어서 최적 실행을 보장할 수 있다. 그러나 이런 경우가 힘든 경우가 있다. 지금 내가 만든 어떤 프로그램에서 링크드 리스트 자료구조가 있고 여기에 노드가 수십개에서 많게는 수만개씩 삽입/삭제 및 검색이 되는 경우가 있다. 바이너리 서치 같은 것을 쓰지 못하기 때문에 검색을 하려면 어쩔 수 없이 선형 탐색을 할 수 밖에 없다. 그런데 정말 수만개의 노드가 생기는 경우에는 이 선형탐색이 프로그램 성능의 bottleneck이 되어버린다. 그래서 해쉬 테이블을 이용하여 검색 속도를 높이도록 하였다. 대신에 삽입/삭제는 더 큰 부담이 있다. 리스트에 노드 추가 삭제는 거의 오버헤드가 없다. 이미 일정량의 노드를 미리 할당하였기 때문에 메모리 할당/해지 오버헤드는 없다. 반면, 해쉬 테이블의 경우에는 이것보다는 오버헤드가 많이 크다고 볼 수 있다.

골치아픈 문제는 노드의 개수가 항상 많다면 해쉬 테이블의 선택이 옳은데, 어떤 경우에는 노드의 개수가 수백개 밖에 되지 않은 경우가 있다. 그리고 이 범위 안에서 매우 자주 삽입/삭제하는 경우가 있다. 이런 경우에는 안타깝게도 그냥 선형탐색 및 리스트를 그대로 쓰는 것이 더 빠르다.
즉, 위 그래프에서 어떤 경우는 이 빨간 동그라미 오른쪽의 시나리오가 펼쳐져서 해쉬 테이블이 훨씬 우수하고, 반대로 어떤 경우에는 왼쪽 시나리오가 발생하여 그냥 리스트 쓰는 경우가 더욱 좋다.

그렇다면 여기서 능동적으로, adaptive하게 자료구조를 선택하면 되겠네라는 아주 간단한 답을 얻을 수 있다. 위에서 언급한 qsort 경우 처럼. 그러나 불행하게도 나의 프로그램에서 이런 능동적인 선택을 하기가 그렇게 쉽지 않다. 단순히 노드의 개수 뿐만 아니라 삽입/삭제가 일어나는 빈도도 고려해야하는 등 변수가 생각보다 많았다. 더 아이러니한 것은 이러한 선택을 하기 위해 들어가는 코드가 또 오버헤드를 유발한다는 점이다!

물론 수업시간에 어느 정도의 초기 구간에서는 오히려 시간복잡도가 나쁜 알고리즘이 좋을 수 있다는 것을 배웠지만 실제 상황에서 이런 경우를 만나면 그렇게 단순하지는 않은 것 같다. 예전에도 해쉬 테이블이냐 선형 탐색이냐 고민한 적이 있었다. 다행히 이때는 오직 탐색만 일어나는 경우였기 때문에 비교적 쉽게 답을 얻을 수 있었다. 엑셀로 정리한 실험 자료는 지금 잃어버려서 확실치 않지만, 약 40~50개까지는 오히려 선형탐색이 우수하다는 결과를 얻었는 것으로 기억한다.



<최악의 경우에도 항상 O(n) 복잡도를 가지는 알고리즘이 오히려 안 좋은 경우>

CLRS 알고리즘 책, 9과에 보면 주어진 리스트에서 i 번째의 원소를 찾는 두 개의 알고리즘이 나와있다. 먼저, 첫번째 방법은 퀵소트의 파티션 루틴을 이용한 RANDOMIZED-SELECT라는 것이다. 알고리즘은 매우 간단하다. 그리고 이 알고리즘 수행시간의 기대값은 O(n)으로 주어진다. 왜 기대값이라는 표현을 쓰냐면 초기 리스트의 형태에 따라 수행시간이 달라지기 때문에, 확률을 고려해야한다. 퀵소트 역시 최악의 경우 O(n^2)의 복잡도를 가진다. 그러나 이러한 경우를 회피하기 위해 랜덤하게 피봇 값을 뽑는 등 여러 테크닉을 사용한다. 그래서 정말 O(n^2)인 경우는 벌어지지 않는다고 말할 수 있다. 마찬가지로 RANDOMIZED-SELECT 알고리즘도 일반적인 경우에는 O(n)이기 때문에 매우 빠르게 작동한다. 그러나 최악의 경우 O(n^2)인 경우가 있으나 이 경우를 만드는 것도 그리 쉽지 않을 만큼 매우 드문 일이다.

그러나 어떠한 경우에도 O(n)에 찾기가 가능한 알고리즘이 개발이 되었고 CLRS 책에 자세히 나와있다. (단, pseudo code가 없다. 그래서 숙제로 내기에 참 좋다...) 최악의 경우에도 O(n)이 되도록 아주 재밌는 트릭을 쓰는 방법이다. 굳이 이 트릭까지 설명하기에는 너무 길기 때문에 간단히 그림 하나로 때운다. 알고리즘의 핵심은 대충 이러하다: 5개씩 그룹으로 나눈 뒤, 거기서 median을 찾고, 이 median 들 중에서 또 median을 찾으면, 적어도 이 median들의 median보다 확실히 크거나 작은 데이터를 가려낼 수 있다.그리고 알고리즘 시간 복잡도는 O(n)으로 증명이 된다.

실제 프로그램을 만들어서 돌려봐도 첫번째 알고리즘이 *훨씬* 빨랐다. 그것도 수천만개 데이터를 줘도 말이다. 그래서 욕 엄청하면서 숙제를 했던 기억이 난다. 사실 이건 당연할 수 밖에 없는 결과이다. 첫 번째 알고리즘이 대부분 O(n)으로 돌아가기 때문이다. 조교 말로는 첫번째 알고리즘이 O(n^2)가 될 수 있는 상황을 만들어, 두번째 - 언제나 O(n)인 - 알고리즘이 더 빨리 돌아가는 것을 보여준 친구도 있다고 했다;; 누군지 몰라도 덜덜덜... 역시 알고리즘은 내 적성이 아니라는 결론을 다시 확인한다.

ps. 조교는 또 악날하게 아주 희한한 데이터셋 {1, 1, 1, .... 백만개의 1 .... , 2} 이러한 데이터를 테스트하는 바람에 나를 포함한 많은 친구들이 감점을 당하기도 하였다. 별도 처리가 없으면 이 경우 무려 20시간이 걸리는 황당한 결과가 나온다. 물론 이런 경우를 다 고려해서 아주 잘 만든 친구도 있다고 했다 :) 역시 덜덜덜.