[자료구조] 기본 점화식 , 재귀호출

자신이 포함된 수식으로 표현하는 것을 점화관계라 한다.

예를 들어서 T(n)을 입력크기가 n인 이진 탐색의 시간 복잡도라 할 떄 T(n)은 

T(n) = T(n/2) + O(1) 점화식으로 표현 가능하다.

T(n) = T(n - 1) + Θ (1),  T(1) = Θ (1)  -> O(n) T(n) = T(n - 1) + Θ (n),  T(1) = Θ (1)  -> O(n^2) T(n) = T(n/2) + Θ (1),  T(1) = Θ (1)  -> O(logn) T(n) = T(n/2) + Θ (1),  T(1) = Θ (1)  -> O(n) T(n) =2 T(n/2) + Θ (1),  T(1) = Θ (1)  -> O(n) T(n) = 2T(n/2) + Θ (1),  T(1) = Θ (1)  -> O(nlogn)

기본 점화식

재귀호출 - 

프로그램 제어 구조나 데이터 구조 안에서 자신을 다시 호출하여 작업을 수행하는 방식으로 이를 이용하기 위해서는 스택을

사용함.    

처리속도가 느리고, 횟수가 지나 치게 많으면 프로그램이 정지함. 

대표적으로 팩토리얼 , 피보나치 수열, 하노이 탑 문제 등이 이용.