说明下列函数的时间复杂度和空间复杂度（包含过程）如题说明下列函数的时间复杂度和空间复杂度（包含过程）intfun(intn){if(n==0||n==1){return1;}else{return2*fun(n-2)+1;}}

Question

说明下列函数的时间复杂度和空间复杂度（包含过程）如题
说明下列函数的时间复杂度和空间复杂度（包含过程） int fun(int n) { if (n==0 || n==1) {return 1;} else {return 2 * fun(n-2) +1;} }

Answer 1

该函数的时间和空间复杂度都均为O(N). 该函数一共执行的次数为N/2 + 1次,这个很容易看出来. 比如对于奇数2K-1,那么将会被计算到的N = (2K-1) , (2K-3), ... 3, 1 而对于偶数2K,那么将会被计算到的N = 2K, (2K-2), ... 4, 2, 0 空间复杂度的话,就是递归过程中用于保存N的数量的栈空间. 因此同样为O(N)的.