数据结构基础算法复杂度分析（一）概念篇

我会带着你远行 2022-08-03 05:26 183阅读 0赞

**为什么要进行算法分析？**

*  预测算法所需的资源

1.   *  计算时间（CPU 消耗）
     *  内存空间（RAM 消耗）
     *  通信时间（带宽消耗）

*  预测算法的运行时间

1.   *  在给定输入规模时，所执行的基本操作数量，或者称为算法复杂度（Algorithm Complexity）

**如何衡量算法复杂度？**

*  内存（Memory）
 *  时间（Time）
 *  指令的数量（Number of Steps）
 *  特定操作的数量

1.   *  磁盘访问数量
     *  网络包数量

*  渐进复杂度（Asymptotic Complexity）

**算法的运行时间与什么相关？**

*  取决于输入的数据。（例如：如果数据已经是排好序的，时间消耗可能会减少。）
 *  取决于输入数据的规模。（例如：6 和 6 \* 109）
 *  取决于运行时间的上限。（因为运行时间的上限是对使用者的承诺。）

**算法分析的种类**

*  最坏情况（Worst Case）：任意输入规模的最大运行时间。（Usually）
 *  平均情况（Average Case）：任意输入规模的期待运行时间。（Sometimes）
 *  最佳情况（Best Case）：通常最佳情况不会出现。（Bogus）

**例**

在一个长度为 n 的列表中顺序搜索指定的值，则

最坏情况：n 次比较；  
平均情况：n/2 次比较；  
最佳情况：1 次比较；  
而实际中，我们一般仅考量算法在最坏情况下的运行情况，也就是对于规模为 n 的任何输入，算法的最长运行时间。这样做的理由是：

*  一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界（Upper Bound）。
 *  对于某些算法，最坏情况出现的较为频繁。
 *  大体上看，平均情况通常与最坏情况一样差。

**算法分析要保持大局观（Big Idea），其基本思路**

*  忽略掉那些依赖于机器的常量。
 *  关注运行时间的增长趋势。

比如：T(n) = 73n3 + 29n3 + 8888 的趋势就相当于 T(n) = Θ(n3)。  
**渐近记号（Asymptotic Notation）**通常有 O、 Θ 和 Ω 记号法。Θ 记号渐进地给出了一个函数的上界和下界，当只有渐近上界时使用 O 记号，当只有渐近下界时使用 Ω 记号。尽管技术上 Θ 记号较为准确，但通常仍然使用 O 记号表示。  
  
使用 O 记号法（Big O Notation）表示最坏运行情况的上界。例如，线性复杂度 O(n) 表示每个元素都要被处理一次；平方复杂度 O(n^2) 表示每个元素都要被处理 n 次。

例如：  
T(n) = O(n3) 等同于 T(n) ∈ O(n3)  
T(n) = Θ(n3) 等同于 T(n) ∈ Θ(n3).  
相当于：  
T(n) 的渐近增长不快于 n3。  
T(n) 的渐近增长与 n3 一样快。

![20150802195015871][]

*  注1：快速的数学回忆，loga(b) = y 其实就是 a^y = b。所以，log2^4 = 2，因为 2^2 = 4。同样 log2(8) = 3，因为 2^3 = 8。我们说，log2(n) 的增长速度要慢于 n，因为当 n = 8 时，log2(n) = 3。
 *  注2：通常将以 10 为底的对数叫做常用对数。为了简便，N 的常用对数 log10(N) 简写做 lg N，例如 log10(5) 记做 lg 5。
 *  注3：通常将以无理数 e 为底的对数叫做自然对数。为了方便，N 的自然对数 loge(N) 简写做 ln N，例如 loge(3) 记做 ln 3。
 *  **注4：在算法导论中，采用记号 lg n = log2(n) ，也就是以 2 为底的对数。改变一个对数的底只是把对数的值改变了一个常数倍，所以当不在意这些常数因子时，我们将经常采用 "lg n"记号，就像使用 O 记号一样。计算机工作者常常认为对数的底取 2 最自然，因为很多算法和数据结构都涉及到对问题进行二分。**

**而通常时间复杂度与运行时间有一些常见的比例关系**

![20150802195621773][]

**计算代码块的渐进运行时间的方法有如下步骤**

*  确定决定算法运行时间的组成步骤。
 *  找到执行该步骤的代码，标记为 1。
 *  查看标记为 1 的代码的下一行代码。如果下一行代码是一个循环，则将标记 1 修改为 1 倍于循环的次数 1 \* n。如果包含多个嵌套的循环，则将继续计算倍数，例如 1 \* n \* m。
 *  找到标记到的最大的值，就是运行时间的最大值，即算法复杂度描述的上界。

[20150802195015871]: /images/20220731/1e25cb646efa41cd9acae30aa2b28cc9.png
[20150802195621773]: /images/20220731/f087f183820c489c873959d5c59fd9a9.png