재귀 메서드의 큰 O

Question

간단한 재귀 메서드의 큰 O를 결정하는 데 어려움이 있습니다. 메서드가 여러 번 호출 될 때 어떤 일이 일어날 지 내 머리를 감쌀 수 없습니다. 나는 혼란스러운 부분에 대해 더 구체적으로 설명 할 것이지만, 지금은 일부 hw 질문에 답하려고 노력하고 있으며, 속이기를 원하지 않는 대신에,이 게시물에 응답하는 모든 사람들은 간단한 재귀 적 방법으로 말한 방법의 큰 O의 간단한 설명을 제공하십시오. (가급적 자바에서 ... 내가 배우는 언어입니다.)

고맙습니다.

Answer 1

재귀 적으로 순서를 정의 할 수도 있습니다. 예를 들어 함수 f가 있다고 가정 해 보겠습니다. f (n)을 계산하려면 k 단계가 필요합니다. 이제 f (n + 1)을 계산하려고합니다. f (n + 1)이 f (n)을 한 번 호출하면 f (n + 1)은 k + 몇 가지 일정 단계를 취한다고 가정합니다. 각 호출은 일정한 단계를 추가로 수행하므로이 메소드는 O (n)입니다.

이제 다른 예를 살펴보십시오. 당신은 이전의 두 결과를 추가하여 순진 피보나치을 구현 말할 수 있습니다 :

fib(n) = { return fib(n-1) + fib(n-2) } 

은 이제 FIB를 계산할 수 말할 수 (N-2) 및 FIB (N-1) K 단계에 대한 모두. fib (n)을 계산하려면 k + k = 2 * k 걸음이 필요합니다. 이제 fib (n + 1)를 계산한다고 가정 해 보겠습니다. 그래서 fib (n-1)의 2 배의 단계가 필요합니다. 그래서 이것은 O (2^N) 인 것 같습니다.

틀림없이 이것이 형식적이지는 않지만,이 방법을 사용하면 약간의 느낌을 가질 수 있습니다.

Answer 2

재귀 적 방법의 큰 O를 찾는 마스터 정리를 참조 할 수 있습니다. 위키피디아 문서는 다음과 같습니다. http://en.wikipedia.org/wiki/Master_theorem

트리와 같은 재귀적인 문제를 생각하고 싶습니다. 그런 다음 나무의 각 수준과 필요한 작업량을 고려하십시오. 문제는 일반적으로 루트 무거운 (첫 번째 반복 >> 나머지 트리), 균형 (각 레벨은 동일한 양의 작업), 리프 무거운 (마지막 반복 >> 나머지 트리)의 3 가지 범주로 분류됩니다. 예를 들어

촬영 병합 정렬 :

define mergeSort(list toSort): 
    if(length of toSort <= 1): 
     return toSort 
    list left = toSort from [0, length of toSort/2) 
    list right = toSort from [length of toSort/2, length of toSort) 
    merge(mergeSort(left), mergeSort(right)) 

당신은 차례로 머지 소트의 각 호출 1/2 원래 길이의 2 이상 mergeSorts를 호출하는 것을 볼 수 있습니다. 병합 절차에는 병합되는 값의 수에 비례하여 시간이 걸립니다.

그런 다음 반복 관계는 T (n) = 2 * T (n/2) + O (n)입니다. 두 개는 2 개의 호출에서 나오고 n/2는 각 호출의 절반에 불과합니다. 그러나 각 레벨에는 병합해야 할 요소 n이 동일하므로 각 레벨에서의 일정 작업은 O (n)입니다.

우리는 작업이 고르게 분포되어 있고 깊이가 log_2 (n)이므로 트리의 재귀 함수가 O (n * log (n))라고 가정합니다.