复杂度分析复习笔记
复杂度分析犹如浩瀚的算法宇宙中的时空向导。 它带领我们在时间与空间这两个维度上深入探索，寻找更优雅的解决方案。
算法效率评估
在算法设计中，我们先后追求以下两个层面的目标。
- 找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。
- 寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。
也就是说，在能够解决问题的前提下，算法效率已成为衡量算法优劣的主要评价指标，它包括以下两个维度。
- 时间效率：算法运行时间的长短。
- 空间效率：算法占用内存空间的大小。
简而言之，我们的目标是设计“既快又省”的数据结构与算法。而有效地评估算法效率至关重要，因为只有这样，我们才能将各种算法进行对比，进而指导算法设计与优化过程。
效率评估方法主要分为两种：实际测试、理论估算。
实际测试
缺点:
难以排除测试环境的干扰因素
展开完整测试非常消耗资源
理论估算
复杂度分析描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。
迭代与递归
迭代
迭代（iteration）是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某段代码，直到这个条件不再满足。
常见代码迭代形式:
| 迭代形式 | 适用范围 |
|---|---|
| for循环 | 适合在预先知道迭代次数时使用 |
| while 循环 | while与 for 循环类似， 循环比 for 循环的自由度更高 |
| 嵌套循环 | 时间复杂度可能会随嵌套升幂 |
递归
递归（recursion）是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段。
- 递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
- 归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。
而从实现的角度看，递归代码主要包含三个要素。
- 终止条件：用于决定什么时候由“递”转“归”。
- 递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
- 返回结果：对应“归”，将当前递归层级的结果返回至上一层。
对比
虽然从计算角度看，迭代与递归可以得到相同的结果，但它们代表了两种完全不同的思考和解决问题的范式。
- 迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。
- 递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。
以求和为例，f(n)=\sum n
迭代：在循环中模拟求和过程，从1遍历到n，每轮执行求和操作,1+2 -> 1+2+3 ->… ->1+2+…+n
递归：将问题分解为子问题,既f(n)=n+f(n-1),f(n-1)=n-1+f(n-2)..直至基本情况f(1)=1，再依次计算f(1)、f(2)…最终得到f(n)
| 迭代 | 递归 | |
|---|---|---|
| 实现方式 | 循环结构 | 函数调用自身 |
| 时间效率 | 效率通常较高，无函数调用开销 | 每次函数调用都会产生开销 |
| 内存使用 | 通常使用固定大小的内存空间 | 累积函数调用可能使用大量的栈帧空间 |
| 适用问题 | 适用于简单循环任务，代码直观、可读性好 | 适用于子问题分解，如树、图、分治、回溯等，代码结构简洁、清晰 |
时间复杂度
常见类型
设输入数据大小为n，常见的时间复杂度类型如图所示（按照从低到高的顺序排列）
空间复杂度
算法在运行过程中使用的内存空间主要包括以下几种。
- 输入空间：用于存储算法的输入数据。
- 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据。
- 输出空间：用于存储算法的输出数据。
一般情况下，空间复杂度的统计范围是“暂存空间”加上“输出空间”。
暂存空间可以进一步划分为三个部分。
- 暂存数据：用于保存算法运行过程中的各种常量、变量、对象等。
- 栈帧空间：用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。
- 指令空间：用于保存编译后的程序指令，在实际统计中通常忽略不计。
设输入数据大小为n ，常见的空间复杂度类型（从低到高排列）:
降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然。
Q & A
Q：尾递归的空间复杂度是O(1)吗？
理论上，尾递归函数的空间复杂度可以优化至 O(1)。不过绝大多数编程语言（例如 Java、Python、C++、Go、C# 等）不支持自动优化尾递归，因此通常认为空间复杂度是O(n) 。
Q：函数和方法这两个术语的区别是什么？
函数（function）可以被独立执行，所有参数都以显式传递。方法（method）与一个对象关联，被隐式传递给调用它的对象，能够对类的实例中包含的数据进行操作。
下面以几种常见的编程语言为例来说明。
- C 语言是过程式编程语言，没有面向对象的概念，所以只有函数。但我们可以通过创建结构体（struct）来模拟面向对象编程，与结构体相关联的函数就相当于其他编程语言中的方法。
- Java 和 C# 是面向对象的编程语言，代码块（方法）通常作为某个类的一部分。静态方法的行为类似于函数，因为它被绑定在类上，不能访问特定的实例变量。
- C++ 和 Python 既支持过程式编程（函数），也支持面向对象编程（方法）。
Q：图解“常见的空间复杂度类型”反映的是否是占用空间的绝对大小？
不是，该图展示的是空间复杂度，其反映的是增长趋势，而不是占用空间的绝对大小。