Question

说明下列函数的时间复杂度和空间复杂度（包含过程）如题

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)的.