[C언어 알고리즘] 3.3.1 퀵 정렬 알고리즘 성능 분석
퀵 정렬 알고리즘 성능을 분석합시다.
퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리)
조건(n<=1)
종료
피벗을 선택한다.
피벗과 맨 앞의 요소를 교환한다.
big:=0
small:=n
반복(big<small)
반복(big:=big+1; big<n; big:=big+1)
조건(compare(base[0],base[big])<0)
루프 탈출
반복(small:small-1;small>0;small:small-1)
조건(compare(base[0],base[small])>0)
루프 탈출
조건(big<small)
교환(base [big], base [small])
교환(base [0], base [small])
퀵 정렬(base,small, compare)
퀵 정렬(base+big, n-big, compare)
n 개의 원소인 배열을 정렬할 때 걸리는 수행 시간을 T(n)이라고 합시다. 퀵 정렬은 재귀적인 방법으로 해결하고 반 씩 나누어 재귀 호출이 이루어지는데 재귀 호출이 진행하기 전에 비교에 걸리는 시간을 S(n)이라고 합시다. 그리고 n 개인 원소를 재귀 호출 전에 비교하는 횟수는 n번이므로 S(n)=n입니다.
T(n) = 2*T(n/2) + n = n^2T(n/n^2) + 2*n = ... = h*n
재귀는 원소 개수가 1보다 작으면 탈출하므로 n^h =1 일 때 더 이상 재귀 호출은 발생하지 않습니다.
h = logn이므로 T(n) = nlogn
그런데 이처럼 퀵 정렬에서 재귀 호출 시에 절반으로 나누어지는 것은 피벗을 잘 선택하였을 때입니다. 따라서 퀵 정렬의 수행 시간은 ω(n log n)이라고 말할 수 있습니다.
최악은 매 번 분할 시 피벗이 제일 큰 값이거나 제일 작은 값일 때 발생합니다. 만약 피벗이 제일 큰 값이면 피벗보다 작은 값들이 있는 부분만 재귀 함수가 동작합니다. 따라서 T(n)은 다음과 같습니다.
T(n) = T(n-1) + n = T(n-2) + n + n-1 = T(n-3) +n + n-2 + n-1 = ...
이처럼 분할하면 퀵 정렬의 수행 시간은 O(n^2)이라고 말할 수 있습니다.
'언어 자료구조 알고리즘 > 디딤돌 알고리즘 (C언어)' 카테고리의 다른 글
[C언어 알고리즘] 3.4.2 이진 탐색 트리(Binary Search Tree) (0) | 2016.11.30 |
---|---|
[C언어 알고리즘] 3.4.1 트리의 용어 (0) | 2016.11.30 |
[C언어 알고리즘] 3.4 이진 탐색 트리 (0) | 2016.11.30 |
[C언어 알고리즘] 3.3.3 퀵 정렬 알고리즘 소스 코드 (0) | 2016.11.30 |
[C언어 알고리즘] 3.3.2 퀵 정렬 알고리즘 구현 (0) | 2016.11.30 |
[C언어 알고리즘] 3.3 퀵 정렬(Quick Sort) 알고리즘 (0) | 2016.11.30 |
[C언어 알고리즘] 3.2.3 하노이 타워 알고리즘 소스 코드 (0) | 2016.11.30 |
[C언어 알고리즘] 3.2.2 하노이 타워 알고리즘 구현 (0) | 2016.11.30 |
[C언어 알고리즘] 3.2.1 하노이 타워 알고리즘 성능 분석 (0) | 2016.11.30 |
[C언어 알고리즘] 3.2 하노이 타워 (0) | 2016.11.30 |