2022下半年软件设计师知识点：时间复杂度与空间复杂度

为帮助考生备考软考软件设计师考试，希赛小编为大家整理了2022下半年软件设计师知识点：时间复杂度与空间复杂度，相信对大家备考会有帮助。

时间复杂度与空间复杂度（★★★★★）

【考法分析】

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)

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、了解主定理求取递归式的时间复杂度。