寻找简单算法的大 O

Question

我得到了一个算法的伪代码：

1     for i=1 to n          //n times
2         j=2^i             //n times
3         while j>=2        //2+3+....? times
4               j=j/2       //1+2+....? times

其中 'to' 表示小于或等于，'^' 表示的幂。

我很确定前两行运行 n 次，但是我不太确定如何计算其他两行。

我知道第 3 行的前两个值是 2... 然后是 3，但我不确定接下来该做什么。

第 4 行也是如此，前两个值是 1.. 然后是 2，但我不知道如何继续。

有人告诉我答案是 O(n^2)，我必须将所有行相加才能得到实际结果。

有什么想法吗？

Answer 1

将其分解成更小的步骤

3         while j>=2        //2+3+....? times
4               j=j/2       //1+2+....? times

上面的一些 j=N 循环运行了 ~log(N) 次

由于 i 从 1 到 N，j 从 2^1 到 2^N。每个 while 循环现在执行 ~log(2^i) 次，等于 ~i 次

希望对您有所帮助

Answer 2

内部循环将运行 log2(j) 次，因为每次迭代将 j 减半。 j 是 2^i，然后是 log2(j) = i。 IE。内部循环运行ning i 次。正如i从1到n所做的那样，总迭代次数将是1+2+3+4+..+n，而它是一个简单的算术级数，其总和为(n+1)n/2，这如所述 O(n^2)。（备注：我可能在某处遗漏了一些 +/-1 常量，但这不会影响最终的复杂性）。

Answer 3

嗯，这个有点奇怪。

让我们先假设每个算术运算都需要相同的时间。案例的话，看看这段代码做了什么：

2         j=2^i             //n times
3         while j>=2        //2+3+....? times
4               j=j/2       //1+2+....? times

如果您考虑一下循环 (3) 的执行方式，它会在每次迭代中将 j 除以 2。如果您将 j 视为 2 的幂，它会在每次迭代中将指数减一。在 j 下降到 2 之前，这只能发生 O(i) 次。因此，假设所有算术运算花费相同的时间，这部分代码运行s 的时间为 O(i)。

外层循环会运行n次，所以这里做的功与1 + 2 + 3 + 4 + ... + n = Θ(n²).

问题在于所有算术运算花费相同时间的假设并不现实。数字 2ⁿ 增长得非常快，并且会很快溢出任何固定宽度的整数类型。此处时间范围的更现实假设是每个操作所花费的时间与数字中的位数成正比。我将忽略此案例，因为我怀疑这是针对 class 作业的，但值得牢记这一点。

寻找简单算法的大 O

Finding the Big O of a simple algorithm

c

algorithm

big-o

pseudocode

time-complexity