반응형 점화식 풀이1 점화식 Recusion Tree로 풀기 [ 점화식 기본 수식 ] 재귀의 기초 지식 내용을 알아보기 전에 아래의 수식이 어떤 시간 복잡도를 가지고 있는지를 눈으로 읽혀둔다. 처음 봤을 때는 이게 무슨 말인지 모를 수도 있지만, 나중에 딱 이 수식만을 알기 위해 찾을 경우가 존재하므로 글의 가장 상단에 위치시켰다. 하나의 항목을 제거하기 위해 입력을 반복하는 재귀 알고리즘이다. $$T(n) = T(n-1) + n => O(n^2)$$ 입력을 2개로 분할 후, 정렬 작업을 수행하는 재귀 알고리즘이다.(Quick Sort, Merge Sort) $$T(n) = 2T(n/2) + cn => O(nlogn)$$ 하나의 단계마다 입력을 절반으로 줄이는 재귀 알고리즘이다.(Binary Search) $$T(n) = T(n/2) + c => O(logn)$$.. 2021. 4. 21. 이전 1 다음 반응형
