아래 글 쓰다가 퀵소트 얘기를 하니 생각나서.. 옛날에 soyoja 님 블로그에서 얘기했던 주제 를 다시 꺼내 본다. (God, the power of procrastination..)
퀵소트 (Quick sort) 는 수많은 표준 라이브러리의 소트 함수에서 쓰고 있는 효율적인 비교 기반 소트 함수이다. 퀵소트은 의 시간 복잡도를 가지며, 같은 시간 복잡도를 갖는 다른 소트에 비해 좀 더 시스템 메모리 등을 효율적으로 사용하기 때문에 실질적으로 더 빠른 속도를 갖는다.
퀵소트에 대해 사람들이 대개 쉽게 이해하지 못하는 것은, 퀵소트의 시간 복잡도는 이라는 주장은 알고리즘의 시간 복잡도는 최악의 경우에 대해 계산한다고 하는 상식과 상반된다는 점이다. 퀵소트의 구현 방식에 따라 퀵소트의 시간 복잡도는 최대
까지 올라갈 수 있다 (물론 기준을 찾는 알고리즘pivoting algorithm 을 바꿔서 최악의
을 보장할 수도 있지만, 여기서는 일반적으로 사용하는 median-of-three, 혹은 임의 기준의 퀵소트에 대해 얘기하자).
결론부터 말하자면, 대개 알고리즘의 시간 복잡도는 최악의 경우로 재는 것이 아니다. 이와 같은 오해의 근원은, 알고리즘의 시간 복잡도를 대문자 O 표기법 (Big-O Notation) 으로 쓰는 것에서 유래한다.
시간 복잡도의 개념을 배울 때 모두 배우듯이, 대문자 O 표기법은 은 어떤 함수가 주어질 때 그 함수의 상한을 표기하는 방법이다. (상수 범위 내에서..) 그래서, 크기가 n 인 입력을 해결하기 위한 알고리즘의 수행 시간을 라 할 때,
이라고 쓰면 실제로 최악의 경우 알고리즘의 시간 복잡도를 나타내게 된다. 때문에, 사람들이 알고리즘의 수행 시간을 최악의 경우로 평가한다고 생각하기 쉽다.
그러나, 실제로 Big-O notation 은 시간 복잡도의 표기를 간단하게 하기 위해 도입한 방법일 뿐, 알고리즘의 최악의 경우에 대한 시간을 측정하기 위해 도입한 방법은 아니다. 따라서, Big-O 가 항상 '최악의 경우' 와 연관되어 있다는 직관은 잘못된 것이다.
퀵소트의 경우, 실제 실행 시간 을 보는 것이 아니라 수행 시간의 기대값 (expected running time)
을 대신 보게 되는데, 이 때
의 최고차항과
의 최고차항이 각각
과
이기 때문에 최악의 경우엔
, 기대값은
이라는 말은 완전히 정당한 것이 된다. ^^
덧) 이와 같은 오해가 횡행하는 또 다른 이유로, expected running time 과 worst running time 의 order 가 다른 알고리즘이 많지 않다는 것이 있다. 머지소트나 힙소트의 경우에는 n 이 주어졌을 때 실행 시간 함수 이 deterministic 하게 결정되고.. 선형검색 같은 경우에도, 중간에 찾았을 경우 곧장 리턴하는 방법을 쓰더라도, expected time 은
이고 worst time 은
이니까,
=
가 된다. 그래서, 글을 쓰는 사람들은 average 와 worst 를 가리지 않고 Big O 표기법을 써서 표기하게 되고, 글을 읽는 사람들은 '아, 최악의 경우에 대해 계산했구나' 라고 생각하는 것.
