返回主页
[数据结构 P2066] 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
未通过
设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
x = 2;
while (x < n / 2)
x = 2 * x;
A. O(logn)
B. O(n)
C. O(nlogn)
D. O(n^2)
上面问题的答案是：
加入错题本
个人笔记
解答：
方法一：逐步分析法
...用户登录可进行刷题及查看答案
解答：
方法一：逐步分析法
该过程主要代价为while循环，其中 x=2*x 的代价为 O(1) ，需要计算while循环的迭代次数。
初始时有 x=2=2^1 ；
while循环第 1 次迭代后有 x=2⋅2=2^(1+1) ；
归纳得while循环第 i 次迭代后有 x=2^(i+1) ；
假设第 k 次迭代后，恰有
，此时跳出循环时，解得 
。
while循环迭代
次，所以该过程时间复杂度为 
。
本题选A。
方法二：综合分析法
本题为单层循环类型题， x 呈指数增长，上限一定，对应循环次数为对数。
本题选A。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案
暂无评论，来抢沙发