이 알고리즘의 반복 관계를 찾으십니까?

Question

n = B-A + 1이라고 가정하면이 알고리즘의 반복 관계를 유도해야합니다.

void recurringalgorithm(int *a, int A, int B){ 
    if (A == B){ 
    for (int j=0;j<B;j++){ 
     cout<<a[j]; 
    } 
    cout<<endl; 
    return; 
    } 
    for (int i=A;i<B;i++){ 
    dosomething(a[A],a[i]); 
    recurringalgorithm(a,A+1,B); 
    dosomething(a[A],a[i]); 
    } 
} 

Help?

Answer 1

재귀 알고리즘의 복잡도가 h(A,B)이라고 가정합니다. 코드에서

하면 2 가지 경우로 h을 분할 할 수 있습니다 :

h(A,B) = { complexity-of-if-branch   if A = B 
     { complexity-of-rest-of-the-code otherwise 

은 "복잡성의-IF-분기"간단하다. "코드 나머지 부분의 복잡성"에는 recurringalgorithm이 포함되어 있으므로 h을 다시 포함해야합니다. 예를 들어

, 함수가 그런 복잡성이

hh(A,B) = hh(A+1, B) + hh(A+2, B) + ... + hh(B-1, B) 

당신은 일반화 코드와이를 비교할 수있을 것입니다

function hh(A,B) { 
    for (var i = A+1; i < B; ++ i) 
     hh(i, B); 
} 

같이 정의됩니다.

(복잡성은 h(A,B) = O(B * (B-A)!)입니다.)