점화식 Recurrence relation 어떤 함수를 자신보다 더 작은 변수에 대한 동일 함수와의 관계로 표현한 것! 사전적 의미는 이렇다. 당연히 잘 이해가 되지 않는다. 풀어서 설명하면 다음과 같다. -> 동일한 함수가 등호나 부등호 양쪽에 나타난다. 이 두 함수의 변수 크기는 다르다. 하지만 동일하다. 입력 크기가 작으면 알고리즘의 효율성을 굳이 따질 필요가 없다. 허나 크기가 커지면 얘기가 다르다. 이런 경우를 위한 분석이 '점근적 분석 Asymptotic analysis'이다. 이번에는 점화식으로 표현한 재귀 알고리즘을 점근적 표기로 나타내는 방법을 알자. 재귀 알고리즘의 수행시간 ->점화식으로 표현 재귀로 표현한 병합정렬을 보자. mergeSort(A[ ], p, r) ▷ A[p ... r]..
