[알고리듬] 3주차: Recursion - Mergesort, Quicksort

* 피보나치 곱셈의 시간복잡도 분석

피보나치 곱셈의 pseudo code

한 자리씩 곱해서 10으로 나눈 나머지를 각 자리에 설정하는 방식이다.

 

교수님피셜) 내가 짠 건데 틀린 거다. 어디가 틀렸는지 찾아봐라

답: index가 범위를 넘어감

$m$은 $X$의 자리수고 $n$은 $Y$의 자리수인데, $k$의 범위가 $0\;\sim\;n+m-1$이고 $i$의 범위가 $0\;\sim\;k$이므로

$Y[k\,-\,i]$에서 $i=0$이고 $k=n+m-1$이면 $Y[n+m-1]$이 되어 $m \gt n$이면 index bound를 넘어간다.

 

Ex) $n=5,\;m=3$고 $k=2$일 때 $i=0\;\sim\;2$이므로 연산은 다음과 같이 진행된다.

$X[0] \times Y[2]$

$X[1] \times Y[1]$

$X[2] \times Y[0]$

 

이 경우에는 문제가 없다.

하지만 $k$가 $3$이 되면 $i=0 \sim 3$이므로 문제가 발생한다.

$X[0] \times Y[3]$

$X[1] \times Y[2]$

$X[2] \times Y[1]$

$X[3] \times Y[0]$

$Y$의 인덱스 범위는 $0\;\sim\;(3-1)$인데 인덱스 $3$으로 접근해서 Runtime error가 발생한다.

 

-> 안쪽 $for$ 문을 다음과 같이 수정한다.

 

$if(k \lt m)$

    $for(i\; =\; 0; i\; <=\; k; i++)$

$else\;if(k \lt n)\; //k \; \geq \; m \wedge k \; \lt \; n$

    $for(i\; =\; k - m + 1; i\; <=\; k; i++)$

$else\; //k\; \geq\; m$

    $for(i\; =\; k - m + 1; i\; <=\; k; i++)$

 

$if$ 문이 많아져 시간복잡도 분석이 다소 어려워진다. 어떻게 분석해야 할까?

$k$가 $0$부터 $n+m-1$까지 가는 동안 안쪽 for문이 도는 횟수(= $X$와 $Y$의 한 자리수 곱셈 횟수)를 다 더하면 됨

$hold\;+=\;X[i]*Y[k-i]$을 $nm$번 반복함 $\rightarrow\; O(nm)$

 

 

 

재귀(Recursion)

유한한 텍스트로 무한을 표현한다.

 

수학에서는 '재귀적 정의'를 하는 경우가 많다.

 

Ex) $n!\;=\;\begin{cases}1 & (n = 0) \\  n\cdot(n-1)!& (n > 0)\end{cases}$

자연수: $1$은 자연수다.

$n$이 자연수면 $n+1$도 자연수다.

 

 

Reduction

(In Algorithm) 어떤 문제를 다른 문제로 reduce한다.

= 풀리지 않은 문제 $X$를 위해 이미 풀린 문제 $Y$를 해결하는 algorithm을 가져다 쓴다

= $X$를 푸는 게 우리 목적인데, $Y$를 푸는 알고리즘을 가져다 쓰면 나머지가 쉽게 해결되는 경우

 

처음에 확인할 것: 정말 $Y$에 대한 알고리즘으로 $X$가 풀리는가?

$Y$에 대한 알고리즘이 어떻게 작동하는지는 알 필요가 없음(-> Black box)

-> $Y$가 어떻게 풀리는지(Inner working)는 고민할 필요가 없다: 라이브러리 갖다 쓰는 거랑 비슷함 => Reduction

 

즉 $X$를 푸는 데에 $Y$로 연결하기만 하면 됨.

$Y$를 푸는 법은 고민할 필요가 없다는 게($Black\; box$로 간주하는 게) 뽀인뜨

-> 문제의 난이도가 '줄어든다': Reduction

 

Ex) 배열에서 최소값 찾기

그냥 배열을 쭉 훑어도 되지만 배열 $A$를 정렬한 후 $return\; A[0]$해도 됨

-> 최소값 찾기($X$)를 정렬 문제($Y$)로 축소

정렬을 어떻게 할 지($Y$를 어떻게 풀 지)는 고민할 필요가 없다. 정렬의 결과가 뭔지만 알면 됨

 

$k$번째로 작은 값 찾기 -> Selection 문제를 sorting 문제로 reduce해서 해결

① $A$를 정렬한다

② $return\; A[k-1]$

 

Algorithm을 설계할 때 내가 사용한 Basic building block이 정확히 어떻게 구현되었는지 모를 수 있다. 애초에 몰라도 됨. 반대로 내가 설계한 algorithm이 언제 어떻게 사용하게 될 지 모름

함수 호출 시의 결과만 가정하고 그냥 가져다 쓰는 거

 

 

Recursion

Reduction의 한 종류

바로 풀 수 있으면 바로 풀고 그게 아니라면 같은 문제의 더 간단한 instance로 reduce한다.

-> 자기 자신으로의 reduction

 

Ex) Peasant multiplication

 

이 정의를 '곱셈의 재귀적 정의'로 볼 수 있다.

 

 

 

Hanoi Tower

$3$개의 peg가 있고 첫 번째 peg에 $n$개의 Disk가 있을 때 $n$개의 Disk를 세 번째 peg로 옮기는 퍼즐

 

일단 다 풀려고 하지 말고 맨 밑에 있는(제일 큰) disk를 옮기는 방법에 집중한다.

① $(n-1)$개의 Disk를 $Peg\;2$로 옮긴다.

② $n$ 번째 Disk를 옮긴다.

③ $(n-1)$개의 Disk를 원래 위치로 넣는다.

④ $(n-1)$번째 Disk를 옮기려면?

-> $n$개의 Disk를 옮기는 문제에서 $(n-1)$개를 옮기는 문제로 reduction되었다.

-> Recursive call을 할 수 있다.  

 

$Hanoi(n,\; src,\; dst,\; tmp)$

: $n$개의 disk를 Peg $src$에서 Peg $dst$로 Peg $tmp$를 이용해서 옮긴다

 

 

 

 

In general

Recursion을 loose하게 설명하면 다음과 같다.

$Base\; case$: 바로 풀 수 있는 instance면 바로 풂

$Recursion step$: 같은 문제의 더 간단한 instance로 reduce

 

 

Simplfy and delegate

Simplify: 더 작은 instance를 만들고

Delegate: 그냥 떠넘긴다

 

 

 

Hanoi Tower의 시간복잡도

$Hanoi(n,\; src,\; dst,\; tmp)$의 $move$ 연산 실행 횟수를 $T(n)$이라고 하자.

$T(0) = 0,\; T(1)= 1,\; T(2)=3,\; T(3)=7,\; \cdots$

$\rightarrow\; T(n)\;=\;\begin{cases}0 & (n = 0) \\ 2 \cdot T(n-1)+1& (n > 0)\end{cases}$

 

$n=0$일 때가 Base case에 해당하며 이런 식을 점화식이라 한다.

-> 점화식도 재귀에 해당한다.

 

 

Pseudo code를 다시 보면 $n-1$로 recursive call, $move$, $n-1$로 recursive call의 세 부분으로 이루어진다.

따라서 $n \gt 0$에 대해 $T(n) = T(n-1) + 1 + T(n-1) = 2\cdot T(n-1) + 1$이고, $n$개의 Disk를 옮기는 횟수는 $2^n -1$이 된다.

 

 

 

왜 재귀가 동작하는가?

$k$일 때 동작하면 $k+1$일 때도 동작한다.

-> 수학적 귀납법

 

 

 

Mergesort

① 주어진 배열을 둘로 (대략 절반) 나눈다.

② Recursion: 두 subarray를 각각 정렬한다.

③ 정렬된 두 subarray를 합쳐 하나의 정렬된 array로 만든다.

 

Pseudo code of mergesort

 

 

Merge

 

Recursion을 통해 이미 정렬된 배열을 합치는 함수.

 

$i$는 첫 번째 subarray의 시작 인덱스, $j$는 두 번째 subarray의 시작 인덱스로 초기화

이제 $[i]$와 $[j]$ 중 작은 수부터 $B$에 채워넣는다.

 

$j \lt n$: $subarray2$의 모든 요소를 다 가져온 상태이므로 $subarray1$의 요소를 그냥 가져와 $B$를 채움

$i \lt m$: $subarray1$의 모든 요소를 가져온 상태이므로 $subarray2$의 요소를 그냥 가져와 $B$에 채움

$A[i] \lt A[j], else$: 각 subarray의 요소를 비교한 후 작은 거부터 $B$를 채움

 

시간복잡도: $O(n)$

 

왜 동작하는가? (Correctness)

수학적 귀납법(Induction)으로 증명할 수있다.

$i)\; n=1$(base case)

$Trivial$

 

$ii)\; n \gt 1$(induction step)

Assumption: Mergesort가 $(n-1)$개 이하의 원소를 가진 배열은 정확히 정렬한다고 하자.

$n \gt 1$이므로 $m \lt n$이고, $n-m \lt n$이므로 가정에 의하면 두 번의 recursive call은 올바르게 동작해

두 개의 정렬된 배열을 만든다.

이 정렬된 배열을 merge하므로 전체가 정렬된다고 할 수 있다.

* 원래는 여기서 merge 제대로 동작함을 설명해야 하지만 여기서는 스킵

 

 

Time complexity

$MergeSort(A[1..n])$의 시간복잡도 함수를 $T(n)$이라 하자.

 

 

$m\;\leftarrow\;\lfloor n/2 \rfloor$: 상수

$MergeSort(A[1..m)])$: $m$개를 정렬 -> $T(m) = T(\lfloor n/2 \rfloor)$

$MergeSort(A[m+1..n)])$: $(n-m)$개 정렬 -> $T(n-m)$

$Merge(A[1..n], m)$: O(n)

-> $T(n)$의 점화식: $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$ $(\because (n-m) = \lceil n/2 \rceil)$

$T(n) = 2T(n/2) + O(n)$으로 단순화해서 생각할 수 있다.

 

그리고 이 점화식을 풀면

$T(n) = O(n\log{n})$

 

 

Quicksort

Mergesort: 반으로 나눠서 Recursion 후 나온 결과를 정리(merge)

Quicksort: 분류 작업(Partition) 후 Recursion

 

① 주어진 원소 중 아무거나 $pivot$으로 설정

② Partition: $pivot$을 기준으로 작은 원소는와 큰 원소를 분류해 이동

③ Recursion: 두 Subarray를 정렬한다.

 

Pseudo code of Quicksort

 

더 좋은 pivot을 고르는 방법도 있긴 한데 아무거나 골라도 잘 돌아감

 

$Partition(A, p)$: $pivot$을 기준으로 앞, 뒤 정리됨

 

$pivot$을 기준으로 작은 값은 앞으로, 큰 값은 뒤로 분류

return value는 분류 후의 $pivot$ 위치

$index$: 1 2 3 4 5 6 7 8

$value$: 5 2 1 4 6 7 3 8

$pivot$ = 4라 하면 $4$와 $8$을 swap 한다. ($4$는 index가 아닌 원소 값이다.)

=> 5 2 1 8 6 7 3 4

 

$l$은 pivot보다 작은 원소의 개수이므로 처음에는 0

 

$for$ 문

배열의 요소가 4보다 작으면 $l \leftarrow l + 1$, swap A[l], A[i]

 

$i = 1, l = 0$

$5 > 4\; \rightarrow\; continue$

=> 5 2 1 8 6 7 3 4

 

$i = 2, l = 0$

$2 < 4\; \rightarrow\; l = 1$, $A[2] = 2$와 $A[1] = 5$의 자리가 바뀜

=> 2 5 1 8 6 7 3 4

 

$i = 3, l = 1$

$1 < 4\; \rightarrow\; l = 2$, $A[3] =1$과 $A[2] =5$의 자리가 바뀜

=> 2 1 5 8 6 7 3 4

 

$i = 4, l = 2$

$8 > 4\; \rightarrow\; continue$

=> 2 1 5 8 6 7 3 4

 

$i = 5, l = 2$

$6 > 4\; \rightarrow\; continue$

=> 2 1 5 8 6 7 3 4

 

$i = 6, l = 2$

$7 > 4\; \rightarrow\; continue$

=> 2 1 5 8 6 7 3 4

 

$i = 7, l = 2$

$3 < 4\; \rightarrow\; l = 3$, $A[7] =3$과 $A[3] =5$의 자리가 바뀜

=> 2 1 3 8 6 7 5 4

 

$i = 7, l = 2$

$3 < 4\; \rightarrow\; l = 3$, $A[7] =3$과 $A[3] =5$의 자리가 바뀜

 

$for$ 문 종료

처음에 바꾼 pivot을 다시 중간으로 넣어줘야 함

중간 위치: $A[l+1]$

-> $l=3$이므로 A[8]과 A[4]를 바꿈

=> 2 1 3 4 6 7 5 8

$A[l+1]$은 당연히 $pivot$보다 큰 값이므로 바꿔도 문제가 없음

 

 

Correctness

Mergesort와 같은 방식으로 증명 가능(수학적 귀납법)

 

Base case: $n=1$일 때 ...

Induction step: $n \gt 1$일 때

Quicksort가 $n-1$개 이하의 원소를 갖는 배열은 정확하게 정렬한다고 하자.

Partition이 잘 돌아간다고 하면 ...

 

 

 

Time complexity

 

$QuiskSort(A[1..n])$의 시간복잡도 함수를 $T(n)$이라 하자.

$T(n)$의 점화식을 구한다: $T(n) = T(r-1) + T(n-r) + O(n)$

 

최악의 경우: $r = 1,\; r = n$

-> $T(n) = T(n-1) + O(n) = O(n^2)$

 

평균적 분석: $O(n \log{n})$ 걸림

= 다양한 경우의 배열($n!$)에 대해 분석해서 평균을 냈더니 $O(n \log{n})$이 나왔다