2016年考研核心考点——数据结构

for循环,当i=1时,内层循环执行n次,当i=2时内层循环执行n-1次…, 分析可知,总共执行了近?? 2/2次,故而时间复杂度为O(?? 2)。要特别注意,在分析时间复杂度时,我们通常采用抓取大端的办法,进行粗略估计, 不会进行详细计算。【参考答案】B 3.(原书第5题)下面程序段的时间复杂度是( )。 for(i=0;i<m;i++) for(j=0;j<n;j++) a[i][j]=i*j; A. O(m 2) B. O(n 2) C. O(m*n) D. O(m+n) 2016年考研核心考点命题思路解密数据结构梦享团队组编本资料供给考生免费使用,任何机构不得商业目的,违者必究!| 第一章绪论 10 本资料为原书上少部分题目,完整版请参考原书! 【解析】本题考查给定循环语句的时间复杂度分析方法。题中的程序有两层for循环, 外层循环执行m次,而每执行一次外层循环,内层循环需要执行n次,故而总共执行mn 次,算法的时间复杂度为O(mn)。【参考答案】C 二.综合应用题部分 1. (原书第1题)下面程序段的时间复杂度是。 s =0; for( i=0; i<n; i++) for(j=0;j<n;j++) s +=B[i][j]; sum = s ; 【考查内容】给定循环语句的时间复杂度分析方法。【解析】由算法可以看出,存在两层循环,外层循环执行了n次,而每执行一次外层循环,内层循环需要执行n次,总共执行了?? 2次,故而时间复杂度为O(?? 2)。本章到此就结束了,请问您有什么疑问吗?任何问题,欢迎您与我们作者进行交流! shareOurDreams weCSdream 梦享论坛团队梦享团队微信号梦享团队官方微信公众号梦享团队新浪微博