4. 算法与分析 (1)
本节主要讲了算法分析和算法度量标准（时间复杂度）。
本文部分ppt、视频截图来自：[青岛大学-王卓老师的个人空间-王卓老师个人主页-哔哩哔哩视频]
1. 算法
1.1 算法定义
算法是对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。
1.2 算法描述
- 自然语言：英语、中文
中文描述：复杂
- 流程图：传统流程图、NS流程图
传统流程图描述：还是比较复杂，占篇幅
NS流程图：比较简介，更适合结构化算法描述
- 伪代码：类语言，类C语言 （本专栏使用的算法描述语言）
- 程序代码：C语言程序，JAVA语言程序…
1.3 算法与程序的关系
- 算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出一个问题可以有多种算法。
- 程序是用某种程序设计语言对算法的具体实现。
1.4 算法特性
1.5 算法设计要求
- 正确性(Correctness)
- 可读性(Readability)
- 健壮性(Robustness) or 鲁棒性
- 高效性(Efficiency)
2. 算法分析
算法分析的目的就是看算法实际是否可行，并在同一问题存在多算法时，进行性能上的比较，以便从中挑选出比较优的算法。
2.1 算法衡量标准
- 一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。
- 算法效率以下两个方面来考虑：
1.时间效率：指的是算法所耗费的时间。
2.空间效率：指的是算法执行过程中所耗费的存储空间。- 但是算法的时间效率和空间效率有时候是矛盾的，需要结合计算机的性能和实际问题数据量的大小综合平衡考虑。
2.2 算法效率度量
1. 算法时间效率的度量
算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。
两种度量方法
- 事后统计：将算法实现，测算其时间和空间开销。（要花费时间和精力实现算法，并且实验结果依赖于软硬件等环境因素，掩盖算法本身优劣）
- 事前分析：对算法所消耗资源的一种估算方法。（☆☆☆因此更多采用事前分析的方法）
- 事前分析方法：
也可以表示为：
如：两个n×n矩阵相乘的算法可以描述为：
上述算法所消耗的时间定义为该算法中每条语句的频度之和，则上述算法的时间消耗T(n)为：
- 算法时间复杂度的渐进表示法
为了方便比较不同算法的时间效率，可以仅比较它们的数量级：
- 算法时间复杂度定义
（1）一般情况下，不必计算所有操作的执行次数，而只考虑算法中基本操作的执行次数（最高次项），它是问题规模n的某个函数，用T（n）表示。
（2）什么是“基本语句”？
- 算法中重复执行次数和算法的执行时间成正比的语句。
- 对算法运行时间贡献最大。
- 执行次数最多。
（3）“问题规模n”表示什么？
n表示待处理问题数据量的多少，越大算法的执行时间越长
- 排序：n为记录数
- 矩阵：n为矩阵的阶数
- 多项式：n为多项式的项数
- 集合：n为元素个数
- 树：n为树的结点个数
- 图：n为图的顶点数或边数