algorithm - 这个算法的运行时间是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)。
希望这会有所帮助。