嵌套在循环中的递归函数的复杂性

Question

我正在尝试计算循环内递归调用的复杂性：

Calculate(n,m){
for(i=1; i<n; i++){
    if(n==1) return 1;
    Calculate(n-1,m);
 }
for(j=1; i<m; i++){
    Calculate(n,m-1);
    if(m==1) return 1;
} 
}

这是我计算它的方法：

C(m,n) = 1 + C(m-1,n) + C(m-2,n) + .... + C(1,n) 
           + C(m,n-1) + C(m,n-2) + .... + C(m,1)

复杂度=2^(m+n)??

Answer 1

您是正确的：要将 m 或 n 减 1，您需要进行 2 次调用；因为你需要将它们都减少到零，所以你需要通过 O(m+n) 'levels'.

因此调用次数为O(2^(m+n))。