while循环的运行时间（数学）

Question

所以我需要一个数学表达式来处理下面的循环，但我似乎无法把握它。我假设我只是缺少一些简单的东西。

while a <= b 
    a = a + a 
end 

使用分析，这将是这个函数的运行时间？

Answer 1

运行时间取决于b的对数。换句话说，时间复杂度是O(log N)。

你可以看到这一点，如果你在1和b开始a在256通过每一次循环中，a加倍，以便有只有九个迭代（会为八个，如果条件是< b）。

每增加一倍b值将导致一次额外的迭代。

当然，这是复杂的分析，运行取决于其他因素的主机上，如（几乎可以肯定不是一个详尽的清单）：

• 你的机器有多快。
• 它还有什么其他的事情要做。
• 初始值为a：a == 0给出了无限运行时间，a == b + 1给出了恒定的运行时间。

Answer 2

您是否同意循环的每次迭代加倍a？如果是，那么让a的初始值为1.经过一次迭代后，a == 2。经过两次迭代a == 4。三之后，a == 8。四后，a == 16;等等。假设b == 64。在这种情况下，循环将运行七次迭代。注意到log_2(64) == 6。

假设b == 128。在这种情况下，循环将运行8次迭代。观察那log_2(128) == 7。

假设b == 256。在这种情况下，循环将运行9次迭代。注意到log_2(256) == 8。

因此，运行时间取决于b的对数。

Answer 3

由于您每次加倍a，您需要在循环退出前加上log(b/a)加倍。所以运行时间是Theta(log(b/a))。