时间复杂度,如图,为何有2^T(n)<=n

2025-06-26 17:49:08
推荐回答(1个)
回答1:

因为每次循环后k 的值就乘了2,因此设t次循环后退出,此时k 的值为2^t,退出循环条件是k >= n,也就是2^t >=n,两边取以2为底的对数,得到t = log2n 以2为底的对数上取整,这样时间复杂度为O(log2n) 以2为底的对数