複雜性算法遞歸關係

Question

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

什麼是運行時間的遞歸關係T（n），爲什麼？

Answer 1

該算法的複雜功能是

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已經正確地指出，這可以通過使用解決了很多更容易一個線性函數。

Answer 2

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

您計算L = LOG2（n），並且你把2^L，或2 ^（L + 1）

複雜度爲O（LOG2 N）：LOG2個運算。