algorithm - 复杂度算法递归关系

Question

int function(int n){
if (n<=1)
 return 1;
else 
 return (2*function(n/2));
}

运行时间的递推关系 T(n) 是什么，为什么？

Answer 1

可以直接计算：是最接近的2^n，最大或相等。

你计算 L=log2(n)，你取 2^L，或者 2^(L+1)

复杂度是 O(log2 N) : log2 N 操作。

Answer 2

该算法的复杂度函数为

T(n) = T(n / 2) + 1
T(1) = 1

应用主定理，我们会得到

a = 1
b = 2
c = 0 (1 = n^0)

log b(A) = log2(1) = 0 = 0 c, thus case 2
apply values and the result is O(log n).

正如@guillaume 已经正确指出的那样，通过使用线性函数可以更容易地解决这个问题。