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

Question

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

while a <= b
    a = a + a
end

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

Answer 1

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

如果从a1 和b256 开始，您可以看到这一点。每次通过循环时，a都加倍，因此只有九次迭代（如果条件为 ，则为八次< b）。

该值的每翻一番b将导致一次额外的迭代。

当然，这是复杂性分析，运行时间取决于许多其他因素，例如（几乎可以肯定不是详尽的列表）：

• 你的机器有多快。
• 它必须同时做哪些其他事情。
• 的初始值a：a == 0给出无限的运行时间，a == b + 1给你恒定的运行时间。

Answer 2

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

Answer 3

你同意循环的每次迭代都加倍a吗？如果是这样，那么让a初始值为 1。经过一次迭代，a == 2。经过两次迭代a == 4。三点后，a == 8。四后，a == 16; 等等。

假设b == 64. 在这种情况下，循环将运行七次迭代。观察那个log_2(64) == 6。

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

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

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