时间复杂度分析。 while循环与内循环 [英] Time complexity analysis. while loop with inner for loop

问题描述

我试图找到的时候，这code运行数量。在右边，我有我尝试在code。我是不知道的循环。这里是code：

I'm trying to find the number of times this code runs. On the right I have my attempt at the code. I'm am not sure about the loops. Here is the code:

                         times
sum = 0                    1
i = 1                      1 
while i ≤ n                log n + 1
 sum = sum + i             n log n
 i = 2i                    log n
return sum                  1

=> N日志N + 2日志N + 4

=> n log n + 2 log n + 4

和由此：为O（n log n）的

and thereby: O(n log n)

这是正确的？

推荐答案

没有，你的分析是不正确。需要注意的是内部循环的每次迭代确实O（1）的工作，所以总时间复杂性可以通过被O乘以循环迭代的次数可以找到（1）。

No, your analysis is incorrect. Note that each iteration of the inner loop does O(1) work, so the total time complexity can be found by multiplying the number of loop iterations by O(1).

在这种情况下，循环运行为O（log n）的迭代，因为我只能双O（log n）的，超过前N次。因此，总的时间复杂度是O（log n）的

In this case, the loop runs for O(log n) iterations, since i can only double O(log n) times before it exceeds n. Therefore, the total time complexity is O(log n).

希望这有助于！

这篇关于时间复杂度分析。 while循环与内循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！