任务三 算法分析和评价

知识点

子任务一 算法的时间复杂度

1.什么是算法的时间复杂度？

算法的时间复杂度是衡量算法执行时间随输入规模增长而变化的度量。它用来估计算法在最坏情况下所需的时间资源。

2.与算法执行时间相关的因素有哪些？

• 问题中数据存储的数据结构
• 算法采用的数据模型
• 算法设计的策略
• 问题的规模
• 实现算法的程序语言
• 编译算法产生的机器代码的质量
• 计算机执行指令的速度

3.什么是大O符号表示法？

时间复杂度通常使用大O符号（O）表示，表示算法执行时间与输入规模之间的关系。具体来说，时间复杂度描述了算法执行所需的基本操作数量，以及这些操作数如何随着输入规模的增加而变化。

时间复杂度仅考虑算法执行时间与输入规模之间的关系，而不考虑实际的执行时间。

4.常见的时间复杂度分类有哪些？

（1）常数时间复杂度 O(1)

无论输入规模的大小，算法的执行时间都保持不变。例如，访问数组中的特定元素或执行固定次数的简单操作。

（2）线性时间复杂度 O(n)

算法的执行时间与输入规模成线性关系。例如，对数组进行遍历或查找特定元素。

（3）对数时间复杂度 O(logn)

算法的执行时间随输入规模的增加而增加，但增长速度较慢。例如，二分查找算法。

（4）平方时间复杂度 O(n²)

算法的执行时间随输入规模的增加而呈平方级增长。例如，嵌套循环的冒泡排序算法。

（5）指数时间复杂度 O(2ⁿ)

算法的执行时间随输入规模的增加而呈指数级增长。例如，穷举搜索算法。

子任务二 算法的空间复杂度

5.什么是算法的空间复杂度？

空间复杂度（Space Complexity）是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括程序代码所占用的空间、输入数据所占用的空间和辅助变量所占用的空间这三个方面。

6.算法在存储器上占用的存储空间包括哪三个方面？

（1）存储算法本身所占用的存储空间

与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。

（2）算法的输入输出数据所占用的存储空间

由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。

（3）算法在运行过程中临时占用的存储空间

随算法的不同而异：

• 有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，称为就地进行的，是节省存储的算法
• 有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元（例如快速排序和归并排序算法就属于这种情况）

7.时间复杂度与空间复杂度之间的关系是什么？

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的：

• 当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间
• 反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间
• 另外，算法的所有性能之间都存在着或多或少的相互影响

因此，当设计一个算法（特别是大型算法）时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性、算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。

算法的时间复杂度和空间复杂度合称为算法的复杂度。