[알고리즘 분석] 02 - 3 빠른정렬(Quicksort)

빠른정렬(Quicksort)

• 1962년에 영국의 호아(C.A.R. Hoare)의 의해서 고안
• 빠른정렬(quicksort)란 이름이 오해의 여지가 있음. 왜냐하면 사실 절대적으 로 가장 빠른 정렬 알고리즘이라고 할 수는 없기 때문이다. 차라리 “분할교환정렬(partition exchange sort)”라고 부르는 게 더 정확함.
• 보기: 15 22 13 27 12 10 20 25

*빠른정렬 알고리즘의 수행절차. 부분배열은 네모로 둘러싸 여 있는 데 반해, 기준 아이템은 그렇지 않다.

 

빠른정렬 알고리즘

• 문제: n개의 정수를 비내림차순으로 정렬
• 입력: 정수 n > 0, 크기가 n인 배열 S[1..n]
• 출력: 비내림차순으로 정렬된 배열 S[1..n]
• 알고리즘:

분할 알고리즘

• 문제: 빠른정렬을 하기 위해서 배열 S를 둘로 나눈다.
• 입력: (1) 첨자 low, high (2) S의 부분배열 (첨자는 low에서 high)
• 출력: 첨자 low에서 high까지의 S의 부분배열의 기준점(pivot point), pivotpoint

*j: pivotitem 보다 작은 그룹의 제일 우측끝 데이터의 위치

- not stable

 

partition 프로시저의 예

분할알고리즘(partition) 분석 

- 분할 알고리즘의 모든 경우를 고려한 시간복잡도 분석

• 단위연산: S[i]와 pivotitem과의 비교
• 입력크기: 부분배열이 가지고 있는 항목의 수, n = high - low + 1
• 분석: 배열의 첫번째 항목만 제외하고 모든 항목을 한번씩 비교하므로, T(n) = n - 1이다.

quicksort 분석

- 빠른정렬 알고리즘의 최악의 경우를 고려한 시간복잡도 분석

• 단위연산: 분할알고리즘의 S[i]와 pivotitem과의 비교
• 입력크기: 배열이 S가 가지고 있는 항목의 수, n
• 분석: 입력이 비내림차순으로 정렬이 되어 있는 경우가 최악. 첫번째(기 준점) 항목보다 작은 항목은 없으므로, 크기가 n인 배열은 크기가 0인 부 분배열은 왼쪽에 오고, 크기가 n-1인 부분배열은 오른쪽에 오도록 하여 계속 쪼개진다. 따라서, T(n) = T(0) +T(n - 1) + n - 1 그런데, T(0) = 0이므로, 재현식은 다음과 같이 된다. T(n) = T(n - 1) + n - 1, n > 0이면 T(0) = 0

[예] S = [1,2,3,4,5,6,7,8]

 

분석

이 재현식을 풀면,

결론적으로 빠른정렬 알고리즘의 최악의 시간복잡도는 n(n-1)/2.

그러면 시간이 더 많이 걸리는 경우는 있을까? 이 경우가 최악의 경우이며, 따라서 이 보다 더 많은 시간이 걸릴 수가 없다는 사실을 수학적으로 엄밀 하게 증명해 보자.

 

평균의 경우를 고려한 시간복잡도 분석

• 단위연산: 분할알고리즘의 S[i]와 pivotitem과의 비교
• 입력크기: 배열 S가 가지고 있는 항목의 수, n
• 분석: A(n)을 n개의 데이터를 정렬하는데 걸리는 평균시간이라고 한다. pivotitem이 정렬 후 p번째 데이터가 될 확률은 1/n. 기준점이 p일 때 두 부분배열을 정렬하는데 걸리는 평균시간은 [A(p - 1) + A(n - p)]이고, 분 할하는데 걸리는 시간은 n - 1이므로, 평균적인 시간복잡도는

행렬 곱셈(matrix multiplication)

- 단순한 행렬곱셈 알고리즘

• 문제: n × n 크기의 행렬의 곱을 구하시오.
• 입력: 양수 n, n × n 크기의 행렬 A와 B
• 출력: 행렬 A와 B의 곱인 C

2 × 2 행렬곱셈(단순한 방법):

• 문제: 두 2 × 2 행렬 A와 B의 곱(product) C,

• 시간복잡도 분석: 8번의 곱셈과 4번의 덧셈이 필요

쉬트라쎈(Strassen)의 방법

n × n 행렬곱셈: 쉬트라쎈의 방법

쉬트라쎈의 알고리즘

• 문제: n이 2의 거듭제곱일 때, n × n 크기의 두 행렬의 곱을 구하시오.
• 입력: 정수 n, n × n 크기의 행렬 A와 B
• 출력: 행렬 A와 B의 곱인 C

• 용어: 임계점(threshold)이란? 두 알고리즘의 효율성이 교차하는 문제의 크기.

분석

- 단순한 방법의 시간복잡도 분석

• T(n): n × n 크기의 행렬 A와 B를 곱하는데 걸리는 시간
• 단위연산: 곱셈하는 연산
• 입력크기: 행과 열의 수, n
• 모든 경우 시간복잡도 분석: 임계값을 1이라고 하자. (임계값은 차수에 전혀 영향을 미치지 않는다.) 재현식은

이 식을 전개해 보면,

*더 효율적인 것이 없음

 

쉬트라센 방법의 시간복잡도 분석 I

• 단위연산: 곱셈하는 연산
• 입력크기: 행과 열의 수, n
• 모든 경우 시간복잡도 분석: 임계값을 1이라고 하자. (임계값은 차수에 전혀 영향을 미치지 않는다.) 재현식은

이 식을 전개해 보면,

*행렬의 크기가 2의 지수가 아닌 경우에는 크기를 2의 지수로 만들기 위해 필요한 만큼의 0 데이터를 넣는다.

 

쉬트라센방법의 시간복잡도 분석 II

• 단위연산: 덧셈/뺄셈하는 연산
• 입력크기: 행과 열의 수, n
• 모든 경우 시간복잡도 분석: 위에서와 마찬가지로 임계값을 1이라고 하 자. 재현식은

도사정리의 3가지 중에서 1번을 이용하면 간단히 해를 구할 수 있다.

n×n 행렬을 곱하는 두 알고리즘의 비교

Discussion

큰 정수곱셈

• 문제: 2개의 큰 정수 u와 v를 곱하라
• 입력: 큰 정수 u와 v, 크기 n
• 출력: prod(u와 v의 곱)

큰 정수곱셈2

• 문제: 2개의 큰 정수 u와 v를 곱하라
• 입력: 큰 정수 u와 v, 크기 n
• 출력: prod2(u와 v의 곱)

prod2 최악의 경우 시간복잡도 분석:

• prod2(x+y, w+z) n/2 ≤ 입력크기 ≤ n/2+1
• prod2(x, w) n/2
• prod2(y,z) n/2

임계값결정

• divide-and-conquer방법에서 큰 문제를 어느 크기의 문제가 될 때까지 분 할 할 것인가
• optimal threshold value를 결정하는 방법
• 문제 크기가 줄어들면 재귀호출을 계속 수행하는 것 보다는 다른 알고리 즘을 활용하는 것이 효과적
• mergesort2의 분할하고 재합병하는데 걸리는 시간(running time): 32n μs로 가정

• 단순화 시키면

• 교환정렬을 이용하면

분할정복을 사용하지 말아야 하는 경우

• 크기가 n인 입력이 2개 이상의 조각으로 분할되며, 분할된 부분들의 크기가 거의 n에 가깝게 되는 경우 ⇒ 시간복잡도: 지수(exponential) 시간

ex) T(n) = 2T(n −1) + n

• 크기가 n인 입력이 거의 n개의 조각으로 분할되며, 분할된 부분의 크기가 n/c인 경우. 여기서 c는 상수이다. ⇒ 시간복잡도:

ex) T(n) = nT(n / 2) + n

 

도사 정리(The Master Theorem)

• a와 b를 1보다 큰 상수라 하고, f(n)을 어떤 함수라 하고, 음이 아닌 정수 n에 대해서 정의된 재현식 T(n)이 다음의 형태를 이룬다고 하자.

도사정리 적용의 예

 

도사보조정리