复杂性算法递归关系
问题描述：
int function(int n){
if (n<=1)
return 1;
else
return (2*function(n/2));
}
什么是运行时间的递归关系T（n），为什么？复杂性算法递归关系
答
该算法的复杂功能是
T(n) = T(n/2) + 1
T(1) = 1
运用master-theorem，我们会得到
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已经正确地指出，这可以通过使用解决了很多更容易一个线性函数。
答
您可以直接计算：它是最接近的2^n，最大或相等。
您计算L = LOG2（n），并且你把2^L，或2 ^（L + 1）
复杂度为O（LOG2 N）：LOG2个运算。
@cstac这是使用主定理时出现的解决方案（除非我在计算中犯了任何错误 - 我会仔细检查它）。可能他期待确切的解决方案？应该有一些关于什么是错的笔记。或者干脆问他 – Paul
我也用解决方案 – cstac
@cstac通过精确求解解决了递推关系。主定理只适用于你想找到复现的复杂性顺序。 – Paul