解2022年408考研真题第1题
2022年408考研真题第1题,考察了时间复杂度的计算方法。题目内容如下:
下列程序段的时间复杂度是( )。
sum = 0;for (i = 1; i < n; i *= 2) for (j = 0; j < i; j++) sum++;
A.
B.
C.
D.
对于这个题目,一种比较简单的解法是设
为
的倍数,即找一个特例,如令
,则
。从而确定基本语句 sum++ 的频度。
这种求解方法,能够得到正确答案,但仅仅停留在解决本题的应试技巧上,如果题目的条件更换了,外层循环不再是 i *= 2 ,就不能以
的倍数特例了。更何况,我认为,在复习阶段,应该尽可能掌握最基本的方法,而不是将重点放在某些技巧上,因为技巧都是针对特殊现象的,只有基本方法才具有普遍适用性。掌握了基本方法,就不用担心试题的变化了;掌握了基本方法,试题再变化,也是“万变不离其宗”。
那么,针对这个题目,从基本方法角度出发,应该如何求解?
在网上,也能搜索到试图通过基本方法求解的文章(例如某乎网站),很可惜,该文章求解过程的计算有错误,且阐述语焉不详,思路跳跃。
下面,本文尝试给出一种方法,请大家欣赏,如果其中有误,敬请指正。
根据分析时间复杂度的方法,解题步骤如下:
第一步:基本语句是 sum++ 。
第二步:基本语句处于嵌套循环中,内层循环与外层循环的变量相关,用下表列出外层循环和内层循环变量及基本语句循环次数(即内层循环次数)
外层循环(第 r 次)变量 i 的值变量 j 的值基本语句循环次数1
2
3
4
r
因为 i < n , 即
,所以
。
又因为
是非负整数,所以
(向下取整)。
第三步:基本语句频度。由上表可知,基本语句频度为:
又因为
,所以:
第四步:得到时间复杂度:
本题答案:B
本文由 mdnice 多平台发布
参考阅读
发表评论