algorithm - 下面代码的时间复杂度是多少O(n)？

Question

我正在解决 Interview Bit 上的一个时间复杂度问题，如下图所示。

这道题的正确答案是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)。