该算法的大O运行时间

Question

我发现很难分析算法的时间复杂度。以此算法为例，我如何在O表示法中找到运行时间？

loop(n) 
i = 1 
while i ≤ n 
    j = 1 
    while j ≤ i 
     j = 2 ∗ j 
    i = i + 1 

Answer 1

从你的文章我明白，你知道O符号的含义，但有一些应用它的问题。在这个简单的例子中，确定循环执行的次数（取决于您的输入大小）就足够了。为了获得最终的价值，你必须把它结合起来。

第一步：分析每个循环的执行次数。 （非环或递归语句具有O（1）。）

while(i<=n) 
... 
i=i+1 

被执行n次，从而为O（n）

内环 而（j < = I） 当J = J * 2

执行了i/2次，但我受外部循环限制了n。所以这是O（n）。

由于有在外环是内环与O（N）必须乘以asymptitics，即N * N =>为O（n^2）

Answer 2

当给这样的代码，它通常有助于从内到外的工作。你的内循环在这里给出：

j = 1 
While j <= i 
    j = 2 * j 

这个循环的工作原理是反复加倍j直到它大于i。在超过i之前，您可以加倍1的次数是Θ（log i），所以每次运行内循环时，它都会运行Θ（log i）。

外环从1计数至n，所做的工作是

日志1 +日志2 + ... +日志N

=日志（1 * 2 * .. * n）（使用对数属性）。

=的log（n！）

= Θ（N log n）的。

最后一步从Stirling's approximation开始。

因此总的来说，时间复杂度为Θ（n log n）。