以下代码的时间复杂度如何为O（n）？ [英] How the time complexity of the following code is O(n)?

问题描述

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

I was solving a time-complexity question on Interview Bit, which is given below in the image.

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

The correct answer to this question is O(N). But according to me, the answer should be O(NlogN). Since the complexity for the first "for loop" should be O(logN) because the variable i is divided by 2 in each iteration and I have studied that whenever the loop variables are either multiplied or divided by 2, then the time complexity is O(logN). Now, for the second "for loop", the complexity should be O(N), therefore, the final complexity should be O(N*logN).

任何人都可以请解释我哪里错了？

Can anyone please explain where I am wrong?

推荐答案

进行实际的数学计算：

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

这是比率为 1/2 的几何级数，所以总和等于：

This is a geometric series with ratio 1/2, so the sum is equal to:

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）。

这篇关于以下代码的时间复杂度如何为O（n）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！