以下代码的时间复杂度如何为O(n)？

Question

这个问题的正确答案是O(N)。但根据我的说法，答案应该是O（NlogN）。因为第一个“for循环”的复杂度应该是O(logN)，因为在每次迭代中变量i被2除，而且我已经研究过，每当循环变量被2乘或除，那么时间复杂度就是O(logN)。现在，对于第二个“for循环”，复杂度应该是O(N)，因此，最后一个复杂度应该是O(N*logn)。

谁能解释一下我错在哪里吗？

Answer 1

做实际的数学运算：

T(N) = N + N/2 + N/4 + ... + 1 (log_2 N terms in the sum)

这是一个比率1/2的几何级数，因此和等于：

T(N) = N*[1 - (1/2)^(log_2 N)] / (1 - 1/2) =
     = [N - N/(2^log_2 N)] / 0.5 =
     2^log_2 N = N
     = (N - 1) / 0.5 

所以T(N)是O(N)。