以下代碼的運行時間是多少？

Question

是不是運行時間只是n-i，這只是O（n）？或者我在這種情況下沒有考慮過任何事情？

i <- c 
while i < n do 
i <- i*c 
end while 

Answer 1

難道不是以c爲底的對數？

你基本上是乘以我，直到它達到n的值。

Answer 2

該算法的運行時間爲O（log n）。它不會是n-i，因爲你不是通過增加或減少一個值來遞增循環計數器。而是你用c遞增循環計數器，所以你在每次迭代時都用c來擴展它。所以它可以去的最大迭代次數是log_c（n）。