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

我正在解决Interview Bit上的一个时间复杂问题，它在图像中给出。以下代码的时间复杂度如何为O（n）？

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

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

来源

2017-02-14 DG4

请注意，O（NlogN）实际上并不是_wrong_，因为O（）是一个上限。它只比O（N）的信息量少。 – Gassa

出错的地方在于，当外部循环输入O（log N）次时，提供可能整个算法确实需要O（？* log N）的想法，内部循环不执行cN次的平均值一些常量c，用于外部循环的每次执行。正如IVlad的答案所述，你需要做数学导致几何系列。 – moreON

做实际的数学：

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

来源

2017-02-14 10:20:38 IVlad

@IVIad，我明白你是如何计算T（n）= O（n）的。但我认为你已经计算了仅用于外循环。但是我们应该为内循环做些什么？ – DG4

@ DG4不，它适用于整个程序。当'i = N'时，内部执行'N'次。当'i = N/2'时，内部执行'N/2'次，依此类推。所以总和考虑了一切。 – IVlad

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

回答

相关问题