Quicksort 알고리즘 복잡도

Quicksort 알고리즘의 평균 시간복잡도 수학적으로 증명하기

June 3, 2019 - 3 minute read -
algorithm

목표 정의

이전 포스팅에서 논의한 바와 같이 Quicksort의 시간 복잡도는 최악의 경우 이며, pivot을 랜덤하게 선택하면 평균적으로 의 복잡도를 가진다. 본 포스팅에서는 알고리즘의 평균 복잡도가 임을 수학적으로 증명한다.

Worst case

Pivot을 선택할 때 항상 배열의 최소값을 선택한다고 하자. 이 경우 Partition과정 종료 후 좌측 부분배열은 공집합일 것이다. 따라서 한번의 iteration이 종료된 후 pivot을 제외한 개의 원소들에 대해 알고리즘이 적용되게 된다.

즉, Pivot이 최소값일 경우에는 분할정복 알고리즘의 이점을 전혀 살리지 못한다. 각 iteration은 단순히 배열을 선형탐색한 후 오직 1개의 원소만을 제거할 뿐이다.

번째 iteration에서는 개의 원소를 탐색하게 되고 이므로 복잡도는 다음과 같다.

Best case

위 worst case는 분할정복의 이점을 살리지 못한다고 하였다. 그렇다면 항상 주어진 배열의 중간값(median)을 pivot으로 지정할 수 있다면 어떻게 될까?

  • 각 iteration마다 모든 부분배열의 원소들을 1번씩 선형탐색한다.
  • 한번에 정확히 2개씩 부분배열이 생성되므로 iteration은 약 번 진행된다.

이 경우 Mergesort와 정확히 동일하다는 것을 알 수 있다. 따라서 복잡도는 임을 알 수 있다. 하지만 중간값을 구하려면 위 과정을 진행하기 전에 한번 더 선형탐색을 해야 하는 번거로움이 있다.

Avg case

가장 구현이 편하고 직관적으로 생각하기 쉬운 pivot은 random pivot이다. Random pivot을 선택해도 평균적으로 Best case에 가까운 의 복잡도가 도출됨을 증명한다.

정의

  • : Quicksort의 표본공간. 즉, Quicksort에서 도출 가능한 모든 outcome들의 집합.
  • : 주어진 Quicksort 시행 에서 발생한 원소(element) 사이의 비교 회수.

Lemma

가 Quicksort 의 전체 Running time이라고 하자. 이 때 다음이 성립한다.

직관적으로 이는 자명하다. 알고리즘에서 원소간 비교를 제외한 연산은(예컨대 swap) 상수번 발생하기 때문이다.

Lemma에 따라 의 상한이 이므로 임을 증명하면 된다.

Indicator variable

주어진 배열의 두 원소가 비교되는지 여부를 Indicator variable로 선언하여 평균을 구한다.

가 각각 배열의 번째로 작은 원소일 때,

: Quicksort 진행과정에서 간의 비교 회수

라 정의하자.

Quicksort는 모든 iteration에서 pivot을 기준으로 나머지 원소들을 비교한다. 두개의 element 중 1개가 pivot으로 선택된다면 선형탐색시 모든 원소를 스캔하므로, 무조건 1번은 비교된다. 이후에는 서로 다른 부분 배열에 속하게 되므로 더이상 비교되지 않는다. 만일 두개의 element 모두 알고리즘 종결시까지 pivot으로 선택되지 못했다면, 애초에 두 원소는 서로 비교되지 않는다.

따라서 는 한번의 Quicksort 과정에서 무조건 0회 혹은 1회 비교된다.

Proof

임의의 에 대하여 모든 원소들간의 비교 회수를 더한 것이 곧 이므로

이다.

기대값의 선형성을 적용하면 다음과 같다.

에서 가 비교되지 않을 확률, 은 비교될 확률이라 하자.

기대값의 정의에 의해 이다.

에 대해 를 생각하자.

의 어떤 원소도 pivot으로 선택되지 않는다면 둘은 같은 recursive call에 속한다. 따라서 이 경우를 제외하고, 중 한 원소가 Pivot으로 선택될 경우를 생각하자.

  1. 혹은 가 pivot으로 최초 선택되면 둘은 비교된다.
  2. 그렇지 않다면 둘은 절대로 비교되지 않는다.

따라서 확률은 부터 까지 개의 원소들 중 2개가 선택될 확률과 동일하다.

에 의해 다음을 보이면 충분하다.

이 때, 이므로,

따라서 시간복잡도의 정의에 의해 이고 증명이 끝났다.

정리

Random pivot을 활용한 Quicksort 알고리즘의 평균 복잡도는 Best case와 동일한 이다. 배열의 원소들은 서로 최대 1회까지 비교된다는 사실을 활용하여 Indicator variable을 활용하여 평균을 계산할 수 있었다. 이와 같이 큰 문제를 작은 문제 여러개로 변환하여 푸는 방법론을 선형계획에서 Decomposition principle라 한다.