1. 如何分析、统计算法的执行效率和资源消耗

前言：数据结构和算法本身解决的是“快”和“省”的问题，所以，执行效率是算法一个非常重要的考量指标。如何衡量编写的算法代码的执行效率，主要内容就是：时间、空间复杂度分析。

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半（仅供参考）。

1.1 为什么需要复杂度分析

1. 测试结果非常依赖测试环境
2. 测试结果受数据规模

结论：我们需要一个不用具体的测试数据来测试，就能粗略地估计算法地执行效率地方法。

1.2 大 O 复杂度表示法

定义：所有代码的执行时间T(n)与每行代码的执行次数n成正比。

公式：T(n) = O(f(n))

说明：T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和，因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

示例：T(n) = O(2n+2)、 T(n) = O(2n2+2n+3)，这就是大 O 时间复杂度表示法（2n2代表2乘以n的平方）。当n很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，我们只需记录一个最大量级即可：T(n) = O(n)； T(n) = O(n2)。

名称：大 O 时间复杂度表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称：时间复杂度。

1.3 时间复杂度分析

1. 只关注循环中执行次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度。抽象为公式为：如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。抽象为公式为：如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))

1.4 常见时间复杂度实例分析

上述时间复杂度