algorithm - 查找此算法的递归关系？

假设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]);
  }
}

帮助

最佳答案

假设递归算法的复杂性是h(A,B)。
从代码中可以将h分为两种情况：

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

“IF分支的复杂性”是微不足道的。对于“其余代码的复杂性”，因为它涉及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)!)）

关于algorithm - 查找此算法的递归关系？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2197813/