求分一个recursive function的复杂度

请问f(x)的复杂是多少？
int f(int x){
if (x<1) return 1;
else return f(x-1)+g(x);
}
int g(int x){
if (x<2) return 2;
else return f(x-1)+g(x/2);
}

First rewrite g in terms of f. You get:

1.     static int g1(int x) {
   
2.         if (x < 2) {
   
3.             return 2;
   
4.         } else {
   
5.             return f(x - 1) + f(x/2) -f(x/2-1);
   
6.         }
   
7.     }

复制代码

Then rewrite f in terms if f. You get:

1.     static int f1(int x) {
   
2.         if (x < 1) {
   
3.             return 1;
   
4.         } else {
   
5.             return 2 * f(x-1) +f(x/2)-f(x/2-1);
   
6.         }
   
7.     }

复制代码

To calculate a given n, you have to spent twice the time spent on (n-1). This is O(2^n).
the time complexity of f(x / 2) and f(x / 2 - 1) is O(log n).
So O(f(n)) = O(2^n) + O(log n), Or simply O(2^n).


In my machine,
f(19) ~ 3 ms
f(20) ~ 6 ms
f(21) ~ 11 ms
f(22) ~ 23 ms
f(23) ~ 45 ms
f(24) ~ 92 ms
f(25) ~ 186 ms
f(26) ~ 370 ms
f(27) ~ 756 ms
f(28) ~ 1479 ms
f(29) ~ 2952 ms
f(30) ~ 5862 ms
f(31) ~ 12001 ms
...
f(99) ~ STILL RUNNING, should take about 2*10^14 yrs.

This is much too slow.

真精准！大赞