Introduction to Algorithms

1. Introduction- 재귀트리(Recursion Tree Method)- 재귀 알고리즘의 Big-Theta를 알아내기 위해서 고안된 직접적인 방법론을 의미한다.- 치환법(Substitution method)로 추측이 불가능 할 때를 의미한다.- 예제를 통해서 한번 자세히 알아보자. 2. Recursion Tree Method2.1. Example 1)- 해당 점화식이 있다고 생각해보자.- 위의 점화식을 다음과 같이 변형하자. - 그후 다음과 같이 재귀트리를 사용하여 계산해보자(n은 4의 거듭제곱 이라고 가정)- 이를 이용하여 전체 시간복잡도를 구해보면 다음과 같다.  2.2)Example2)- 이번엔 계수가 다를 때의 점화식의 시간복잡도를 한번 계산해보자.- 주어진 점화식은 다음과 같다. - 이..

1. Introduction- 분할 정복(DIvide & conquer)알고리즘의 시간복잡도를 구할 수 있는 네가지 방법중 가장 일반적인 "substitution method"에 대해 알아보자.- "substitution method"은 두가지 단계로 구성되어 있다.1)  해당 알고리즘의 시간복잡도를 n에 대한 함수로 가정2)  수학적 귀납법을 사용하여 그 해가 성립하는지 증명하고, 해당 상수를 찾아낸다. 2. Substitution Method- Substitution Method을 사용하면 재귀 알고리즘에서 상한 또는 하한을 설정가능하다(Big-O , Big-Omega)- 해당 방법을 이용하기 위해선 Big-Theta를 증명하려고 하기보단, - Big-O를 먼저 증명하고 그 다음에 Big-Omega를..

1.Introduction- Chapter4 부터는 분할 정복(Divide & Conquer) 응용을 살펴보고, - 분할 정복 알고리즘을 분삭할 때 생기는 점화식을 딥하게 알아보고자 한다. 1.1. 분할 정복(Divide & Conquer)- 주어진 문제를 재귀적으로 해결한다.- Base case(Bottoms Out) 같은 경우 재귀 없이 직접 해결 하고- Recursive case같은 경우 다음과 같이 세가지 단계로 나누어 문제를 해결한다 1) Divide(분할) : 문제를 더 작은 동일 문제의 하위 문제로 나눔2) Conquer(정복) : 하위 문제를 재귀적으로 해결함3) Combine(결합) : 하위 문제의 해결책을 결합하여 원래 문제의 해결책을 만듬  1.2. Recurrences(점화식)- 재..

1. Introduction- 효율적인 알고리즘을 구현하기 위해 이 "효율"을 계산하기 위한 "시간 복잡도"에 대해서 알아보자 2. Big-O Notation - Big-O Notation은 함수의 상한을 나타낸다. - 즉 상한을 걸어두고, 그 함수는 상한에 걸어둔 Big-O Notation보다 특정 순간부터 증가하지 않음을 의미한다.(이 때 최고차항을 기준으로 나타낸다.)- 예를들어 다음과 같은 함수가 있다고 생각해보자.- f(x) = n^3 + 2n+1 --> O(n^3)이라고 나타낼 수 있다. - 하지만 O(n^4),O(n^5)로도 나타낼 수 있다. 그 이유는 f(x)는 n^4 , n^5보다 느리게 증가하기 때문이다.- 따라서 c>=3 을 만족할 때 O(n^c)로 Big-O Notation으로 표현..