下面代码的时间复杂度是多少O(n)？
How the time complexity of the following code is O(n)?
我正在解决 Interview Bit 上的时间复杂度问题，如下图所示。
这道题的正确答案是O(N)。但根据我的说法，答案应该是 O(NlogN)。由于第一个“for 循环”的复杂度应该是 O(logN)，因为变量 i 在每次迭代中都被除以 2，而且我研究过每当循环变量乘以或除以 2 时，时间复杂度为 O （logN）。现在，对于第二个“for 循环”，复杂度应该是 O(N)，因此，最终的复杂度应该是 O(N*logN)。
谁能解释一下我哪里错了？
做实际的数学运算：
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)。
我正在解决 Interview Bit 上的时间复杂度问题，如下图所示。
这道题的正确答案是O(N)。但根据我的说法，答案应该是 O(NlogN)。由于第一个“for 循环”的复杂度应该是 O(logN)，因为变量 i 在每次迭代中都被除以 2，而且我研究过每当循环变量乘以或除以 2 时，时间复杂度为 O （logN）。现在，对于第二个“for 循环”，复杂度应该是 O(N)，因此，最终的复杂度应该是 O(N*logN)。
谁能解释一下我哪里错了？
做实际的数学运算：
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)。