块代码的运行时间

Question

有人可以向我解释为什么这段代码的运行时复杂度T（n）为2lgn + 2。我认为它应该是lgn + 2。

public static reduce(int n){ 
int result = 0; 
while (n >1){ 
    n = n/2; 
    result = result +1; 
} 
return result; 
} 

Answer 1

大概假定每行都需要1个单位时间（不包括n > 1检查）。

所以int result = 0;,n = n/2;,result = result +1;和return result;每个分类为取1个单位时间。

2来自int result = 0;和return result;，每个执行一次。

2日志Ñ来自n = n/2;和result = result +1;各自为执行日志 n次。

注：

n > 1也可分类为产生3日志 N + 2

n = n/2;和result = result +1;可以各自分类为采取的时间2个单位导致的时间单位（同上）5日志 n + 2.

这一切都很主观。

唯一的全面协议将c日志 n + d为某些c和d。