时间复杂度的问题

i=1; while(i<=n) i=i*3;答案:O(log3n)谁能帮我详细解释下么?
2024-12-01 05:08:07
推荐回答(1个)
回答(1):

设若进行了t次循环,
则i=3^t,可知3^t=n,因为i<=n,再大就跳出循环了。
于是等式两边取log,变为log(3^t)=log(n),再化为t*log3=log(n)。
[log(n)/log3)=log(3)(n)]
再来就知道了吧,得t=log3n。
t就是时间复杂度。
(^代表乘方,*代表乘)