5.4 재귀 알고리즘과 머지소트merge sort 시간복잡도

시작하기에 앞서특정한 입력값 집합으로 이루어진 문제에 대한 정답은 같은 문제에 대한 작은 입력 값 집합에 대한 정답으로 축소할 수 있습니다. (이것은 부분 문제subproblem 이라는 꽤 중요한 표현입니다.)예를 들어, 두 양의 정수 a, b의 최대공약수(GCD)를 구하는 문제를 생각해보자. 여기서 b>a. 이 문제는 더 작은 입력값인 b mod a 와 a의 최대공약수를 구하는 문제로 축소될 수 있다. 왜냐하면 gcd(b mod a, a) = gcd(a, b)이기 때문이다.이런 문제 축소가 수행될 수 있다면, 원 문제의 정답은 이런 축소된 문제의 흐름(좀 더 엄밀하게는 축소된 문제의 나열sequence of reductions) 속에서 찾아 낼 수 있다. 계속 축소하다보면 정답을 정확하게 알 수 있는 ..
Discrete mathmatics and Problem Solving/5 재귀와 귀납 2018. 1. 9. 18:42
1