[이산수학] 재귀적 알고리즘

재귀적이란?

어떤 알고리즘이 문제를 보다 작은 입력을 갖는 동일한 문제로 단순화시켜 해결하는 것

 

분할정복

분해된 각각의 하위 문제는 간단한 방법으로 풀릴 수 있는 문제가 될 때까지 계속해서 분해, 마지막으로 분해된 하위 문제들의 해답들은 원래 문제의 해답을 얻기 위해 결합

 

n! 는 1에서 n까지의 곱으로 정의를 하는 것입니다. 

 

팩토리얼의 알고리즘

factorial (n) {
	if(n == 0)
    	return 1
    return n*
}

 

n!이 나오는 것을 본다면 

 

1. 기본단계

n이 0일 때 0! (=1)을 반환합니다.

 

2. 귀납단계

• (n-1)! 일 때 성립한다고 가정 n>0
• n에 대해서 성립하는지 가정
• n이 아니면 n * (n-1)! 시행
• (n-1)! * n = n! n일때 정확하게 n 성립

최종적으로 알고리즘은 정확하게 n!로 가정

 

로봇의 걸음

n 미터를 갈 수 있는 방법의 수 

Input : n
Output : walk(n)

walk(n) {
	if(n==1 V n ==2)
    	return n
    return walk(n-1) + walk(n-2)
}

walk(3) 호출

=> return walk(2) + walk(1) 명령에서 walk(2) 호출

r

하면 return 2가 반환됩니다.

walk(1) 호출

return 1반환됨

return 2+1 반환됨

 

 

합병 정렬

리스트를 각 부분 리스트가 하나의 원소만을 가질 때까지 동일한 크기의 두 부분 리스트들로 반복해서 나누는 것으로 진행이 됩니다. 

 

각 부분 리스트는 균형 이진 트리로 표현될 수 있습니다. 

 

각 단계에서 한 쌍의 부분 리스크는 오름차순의 원소들을 가진 하나의 리스크로 합병됩니다. 이 과정은 모든 부분 리스트들이 합병되면 종료됩니다. 

 

합병된 리스트들의 연쇄는 이진 트리로 표현될 수 있습니다. 

 

재귀적 합병 정렬

procedure mergesotr(L, 1, n) {L=a1, a2, ... , an}

if n > 1 then
	m := n/2
    L1 := a1, a2, ... ,am
    L2 := am+1, am+2, ... , an
    L  := merge(mergesort(L1, 1, m), mergesort(L2, m+1, n))

 

merge 합병

procedure merge(L1, L2 :sorted lists)
L:=empty list
while L1 and L2 are both nonempty
	remove smaller of first elements of L1 and L2 from its list;
    	put at the right end of L
    if this removal makes one list empty
    	then remove all elements from the other list of append them to L
return L {L is the merged list with the elements in increasing order}

Complexity of Merge : 각각 m개와 n개의 원소를 가진 두 개의 리스트를 합병하기 위해 최악의 경우 m + n - 1번의 비교가 필요하다.

 

merge 함수는 두 개의 각각 정렬된 리스트가 정렬해서 나올 때 두 부분 리스트의 합이 n이라고 하면 merge 함수의 복잡도는 n의 복잡도를 갑집니다. merge sort 알고리즘은 길이가 n인 것이 나오면 반반 나누어서 호출하기 때문에 호출할 때마다 1/2이 줄어듭니다.

 

이는 알고리즘 복잡도를 1/2씩 줄어들기 때문에 log n 의 복잡도가 됩니다. 그리고 나서 n으로 결합이 되기 때문에 최종적으로 

 

n log n 의 복잡도를 가지게 됩니다. 이보다 더 효율적인 알고리즘은 없습니다.