runtime - 块代码的运行时间

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 log ₂ n 来自每个被执行 log n = n/2;2 _n次。result = result +1;

笔记：

n > 1也可以分类为时间单位，得到 3 log ₂ n + 2。

n = n/2;并且result = result +1;每个都可以归类为花费 2 个时间单位，导致（与上述）5 log ₂ n + 2。

这都是非常主观的。

对于某些 c 和 d ，唯一的全面协议是 c log ₂ n + d。