软件设计师时间复杂度与空间复杂度考点

　　软件设计师时间复杂度与空间复杂度考点有哪些?为了方便考生及时有效的备考，课课家小编为大家精心整理了软考中级软件设计师时间复杂度与空间复杂度考试知识点，供大家参考和学习。如想获取更多计算机软件水平考试的模拟题及备考资料，请关注课课家网站的更新。

　　【考法分析】

　　1、本知识点的考查形式主要有：根据题干描述的情景，根据排序方法、算法逻辑或相关代码，计算其时间复杂度或空间复杂度;根据递归式，计算其时间复杂度;下午题也会考查根据题干说明和代码，指出时间复杂度。

　　【要点分析】

　　1、时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模n的某个函数T(n)。由于许多情况下要精确计算T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定义如下：

　　如果存在两个常数c和m，对于所有的n，当n≥m时有f(n)≤cg(n)，则有f(n)=O(g(n))。也就是说，随着n的增大，f(n)渐进地不大于g(n)。例如，一个程序的实际执行时间为T(n)=3n3+2n2+n，则T(n)=O(n3)。

　　常见的对算法执行所需时间的度量：

　　O(1)<o(log2n)<o(n)<o(nlog2n)<o(n2)<o(n3)<o(2n)< p="">

　　2、常见排序方法的时间复杂度和空间复杂度见考点60介绍;

　　3、常见算法逻辑的时间复杂度：

　　(1)单个语句，或程序无循环和复杂函数调用：O(1)

　　(2)单层循环：O(n);双层嵌套循环：O(n2);三层嵌套循环：O(n3)。

　　(3)树形结构、二分法、构建堆过程：O(log2n)。

　　(4)堆排序、归并排序：O(nlog2n)。

　　(5)所有不同可能的排列组合：O(2n)。

　　4、主定理求固定形式递归式的时间复杂度：

　　【备考点拨】

　　1、掌握常见排序算法的时间复杂度和空间复杂度;

　　2、掌握常见排序算法、常见算法逻辑(如循环)的时间复杂度;

　　3、了解主定理求取递归式的时间复杂度。

      课课家教育专注软考培训10年以上，一直坚持自主研发，将丰富的软考培训经验有效融入教程研发过程，自成体系的软考视频教程、软考培训教材和软考在线题库，使考生的学习更具系统性，辅导更具针对性。想要报考2020年软考的考生现在就可以开始备考了，报名课课家软考各科目考试赠送：辅导教材、历年真题、考前冲剌资料、在线模拟测试题库、老师专属答疑指导等，以保障学员顺利通过考试。

　　>>>>>>点击进入软考报名专题

　　相关推荐：2020年软件设计师考点整理