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))。