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

小编典典

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

algorithm

我正在解决有关采访位的时间复杂性问题，该问题在下面的图片中给出。

这个问题的正确答案是O（N）。但是据我说，答案应该是O（NlogN）。由于第一个“
for循环”的复杂度应为O（logN），因为变量i在每次迭代中均被2除，并且我研究了每当循环变量乘以或除以2时，时间复杂度为O
（登录N）。现在，对于第二个“ for循环”，复杂度应为O（N），因此，最终复杂度应为O（N * logN）。

谁能解释我错了吗？

阅读 374

2020-07-28

共1个答案

小编典典

做实际的数学运算：

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

这是一个具有ratio的几何级数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)。

2020-07-28