简单的时间复杂度O（nlogn）

我在回顾一些面试的大O表示法，并且遇到了这个问题。简单的时间复杂度O（nlogn）

for i = 1 to n do: 
    j = i 
    while j < n do: 
    j = 2 * j

简单吧？外循环提供了n个步骤。并且这些步骤中的每一个我们执行分配j=i的单个步骤O（1），然后从j = i步进while循环的log（n-j）或log（n-i）。我认为时间复杂度是O（nlogn），但答案是O（n）。

这里是答案：

的运行时间大约是以下之和：Σ 1 + 日志（N/I），其中i从1到n，其是Θ（n）中。

现在它已经有一段时间了，所以我有点生疏。 log(n/i)从哪里来？我知道log(n) - log(i) = log(n/i)但是我认为我们记录（n-i）不是log（n） - log（i）。时间复杂度不是O（nlogn）？我相信我错过了一些简单的东西，但我现在已经盯着这个小时了，现在我开始失去理智了。

来源：这里是源这个问题Berkeley CS 170, Fall 2009, HW 1

编辑：经过考虑之后多一点是非常有意义的内部循环的时间复杂度是log（N/I）。导致每个内部循环运行n-i次，但是我将每个循环加倍。如果内部循环总是从0开始，我们有log（n），但是要考虑循环的数量，我们不必循环log（i）。 log（n） - log（i）是log（n/i）。

来源

2017-10-07 OLIVER.KOO

要添加到所提供的答案[见这里]（HTTPS：//数学。stackexchange.com/questions/74412/how-to-show-sum-limits-i-1n-log-left-fracni-right-thetan）这个数字如何是O（n） – RSon1234

谢谢@ RSon1234这正是我所知寻找！ –

我认为该日志（N/I）来自内环

通知j = i

如何，这意味着当i = 2（可以说N = 10）

内环

while j < n do: 
    j = 2 * j

将只运行从j=2到10其中j multilplies本身由2（因此日志）&曲所以内循环运行log base 2 n/i times

我通过代码&它看起来像线性时间，因为大多数时间内循环的只运行一次跑了简单的I = 10 ickly超支n=10

的值。

示例：当i的值变得如此时，如果将它乘以2，则得到大于或等于n，则不会多次运行内部循环。

所以如果n = 10你在内环一个执行从i=n/2 (if i=10/2=5)开始则j与J = 5开始，获得在一次循环与2 &内环条件while j < n do:失败乘以本身。

编辑：这将是O(n.log(n))如果j的值开始与J = 0，每次&内环跑从i到n

来源

2017-10-07 05:00:41

谢谢Sujal。我知道'j = i'和log（n/i）来自你在answer.h中提到的内部循环和行为数。如果每个内部循环运行n-i次，为什么它不应该是log（n-i）。即使我们有log（n/i），为什么运行时o（n）不是log（n/i） –

可以看到答案的最后部分，这段代码对于每个j只运行一次执行，/2的初始值，只需拿一支笔和一张纸写下n = 10的简单执行过程，你会发现执行的总步骤大约是16，这与n = 10或多或少类似，如果它是O（n。 log（n））它将是10 * 3或30次执行。 –

简单的时间复杂度O（nlogn）

回答

相关问题