题
假设N = B-A + 1,I需要派生该算法的递推关系:
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]);
}
}
帮助?
解决方案
假设你的递归算法的复杂度是h(A,B)
。
这是你的代码,你可以h
分成两种情况:
h(A,B) = { complexity-of-if-branch if A = B
{ complexity-of-rest-of-the-code otherwise
在“如果 - 复杂性的分支”是微不足道的。对于“复杂性的休息的最代码”,因为它涉及recurringalgorithm
,你需要再包括h
。
举例来说,如果该函数被定义像
function hh(A,B) {
for (var i = A+1; i < B; ++ i)
hh(i, B);
}
然后,复杂性将是
hh(A,B) = hh(A+1, B) + hh(A+2, B) + ... + hh(B-1, B)
您可以与您的代码来概括相比较。
(顺便说一句,复杂度是h(A,B) = O(B * (B-A)!)
)
不隶属于 StackOverflow