PostAddsense


태그 : 재귀 요약보기전체보기목록닫기

1

4.4 The recursion-tree method for solving recurrences

4.4 The recursion-tree method for solving recurrences재귀-나무에서 각각의 노드는 재귀함수 호출집합 어딘가에 있는 한 개의 부분 문제의 비용을 나타낸다. 레벨당 비용을 구하기 위해 나무의 각 레벨 내에 있는 비용을 더한다. 그리고 모든 재귀 레벨의 비용을 결정하기 위해 레벨당 비용을 모두 더한다. 재귀 ...

4.3 The substitution method for solving recurrences

재귀를 풀기 위한 치환법(substitution method) 2단계1. 답의 형태를 추측하라.2. 상수를 찾기 위해 수학적 귀납법을 사용하고 답이 작동하는 것을 보여라.재귀에 관한 상계 또는 하계를 만들기 위해 치환법을 사용할 수 있다. 예제로 4.19 재귀식을 한 번 살펴보자.4.19 재귀식의 답을 T(n) = O(n lg n) 이라고 추측...

Chapter 4 : Divide-and-Conquer

분할하고 정복하기 3단계분할하라 : 문제를 보다 더 작은 하위 문제로 분할하라정복하라 : 재귀적으로 하위 문제를 풀어 정복하라. 그러나 하위 문제의 크기가 작다면 직접적인 방법으로 하위 문제를 풀어라.조합하라 : 하위 문제에 대한 답을 원래 문제에 대한 답으로 조합하라.recursive case : 하위 문제가 충분히 커서 재귀할 수 있는 경우base ...
1