此for循环的时间复杂度:for(i = 2; i <N; i = i * i)? [英] Time complexity of this for loop: for (i = 2; i &lt; N; i = i * i)?

问题描述

我们正在学习有关时间复杂度的信息，在这个示例中我遇到了很多麻烦.

We're learning about time complexity right now and I'm having a ton of trouble with this one example.

for (i = 2; i < n; i = i * i)
{
     ... do something ...
}

教授说这是O(sqrt(N))，但我不确定我是否相信.毕竟，如果N = 16，它只会运行2次，而不是4次?

The prof said that it was O(sqrt(N)), but I'm not sure that I'm convinced. After all, if N=16, it only runs 2 times, not 4 right?

我的解决方法: 2 ^(2k)= N，其中k是循环运行的次数. 除去常数因子，k运行log(N)次. 我在哪里错了?感谢您对此事的任何建议.

My approach to solution: 2^(2k) = N, where k is the number of times the loop runs. Removing the constant factors, k runs log(N) times. Where am I going wrong here? Thanks for any advice on the matter.

推荐答案

您是正确的，您的讲师是错误的(至少他们的界限并不严格)，我喜欢您所做的分析，但我认为在最后一步中您得出了错误的结论.

You are correct that your instructor is wrong (at least, their bound isn't tight), and I like the analysis you've done, but I think that you've come to the wrong conclusion in the final step.

很高兴您在研究过程中了解了所有中间价值.您是正确的，j的取值顺序为2、4、16、256，等等.如果将事物重写为2的幂，请注意，该顺序取值

It's great that you looked at all the intermediary values along the way. You're correct that the sequence of values that j takes is 2, 4, 16, 256, etc. If we rewrite things as powers of two, notice that the sequence takes on the values

2 ¹ ，2 ² ，2 ⁴ ，2 ⁸ ，...

2¹, 2², 2⁴, 2⁸, ...

通常，在循环执行k次迭代之后，j的值为2 ^{2 k} (与2 ^2k 相对，您最初写的).这意味着要确定循环迭代次数，您需要确定何时

More generally, after k iterations of the loop, the value of j is 2^2k (as opposed to 2^2k, as you initially wrote). This means that to determine the number of loop iterations, you want to determine when

2 ^{2 k} = n.

2^2k = n.

在这里，您必须采用两个对数来解决这个问题:

Here, you have to take two logarithms to solve this:

2 ^{2 k} = n

2^2k = n

2 ^k = lg n

2^k = lg n

k = lg lg n

k = lg lg n

因此循环的迭代次数为 O(log log n)，低于老师给您的O(√ n)和您的O(log n)想到了.

So the number of iterations of the loop is O(log log n), lower than both the O(√n) that your teacher gave you and the O(log n) that you came up with.

对于它的价值，您经常重复取数字的平方根时，可以看到O(log log n)的行为(可以将数字求平方O(log log n)的平方根，然后再降为常数)，因此不是令人惊讶的是，如果以相反的方式运行它并继续平方一个会显示O(log log n)的值.

For what it's worth, you often see O(log log n) behavior when you repeatedly take square roots of a number (you can take the square root of a number O(log log n) times before it drops to a constant), and so it's not super surprising that if you run this in reverse and keep squaring a value that you'd see O(log log n) show up.

这篇关于此for循环的时间复杂度:for(i = 2; i <N; i = i * i)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！