c - 寻找简单算法的大 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

嗯，这个有点奇怪。

让我们先假设每个算术运算都需要相同的时间。在这种情况下，看看这段代码做了什么:

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) 次。因此，这部分代码的运行时间为 O(i)，假设所有算术运算花费相同的时间。

外循环将运行 n 次，因此此处所做的工作将与 1 + 2 + 3 + 4 + ... + n = Θ(n²) 成正比。

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