这个算法的运行时间是log n吗？

Question

我认为这个算法（或代码）运行了 log n 次，因为每次要评估的条件数量都会减少一个常数因子。我对么？如果不是，你能给我解释一下 运行 时间是多少吗？

g(x) (* x > 1 is a real number *)

while x > 1 do
   x := x/3

Answer 1

让这个循环运行k次，这将是算法的时间复杂度，
结束时:
第一次迭代：x= (x/3¹)
第二次迭代：x= (x/3²)
第 3 次迭代：x= (x/3³)
.
.
.
.
第 k 次迭代：x=(x/3^k) <=1（即终止条件）

解决这个问题：采用边界条件：
(x/3^k) =1
因此 k=Log₃x
因此时间复杂度为 O(LogN).
希望这有帮助。