8.5 KiB
二分查找（已排序好的数据）（分而治之的重要算法思想） 插入排序（处理小型数据集非常高效） 贪心（当前看来最好的选择） 数据结构设计是一个充满权衡的过程 数据结构是算法的基石，数据结构为算法提供了结构化存储的数据，以及操作数据的方法 算法为数据结构注入生命力，数据结构本身仅存储数据信息，结合算法才能解决特定问题 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键
复杂度分析
在设计算法中，我们先后追求以下两个层面的目标：
- 找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解
- 寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法
评价算法的主要指标：
- 时间效率：算法运行时间的长短
- 空间效率：算法占用内存空间的大小
设计“即快又省”的数据结构与算法 效率评估方式：实际测试、理论估算 迭代和递归，迭代是一种重复执行某个任务的控制结构，递归是一种算法车旅，通过函数调用自身来结局问题，主要包括两个阶段：
- 递：不断调用自身，通常传入更小或更简化的参数，直到达到“终止条件”
- 归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果
递归主要包含三个要素：
- 终止条件：用于决定什么时候由“递”转“归”
- 递归调用：函数调用自身，通常输入更小或更简化的参数
- 返回结果：对应“归”，将当前递归层级的结果返回至上一层
while 比 for 自由度更高
while 用于循环次数未知的情况
for 用于循环次数已知的情况
迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复和累加这些步骤，直到任务完成
递归：“自上而下”地解决问题，将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式，接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）
递归通常比迭代更加耗费内存空间，递归通常比循环的时间效率更低 尾递归：如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当
- 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文
- 尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文
Tip
递归不适合数据量过大的操作，经过测试（JAVA）当递归次数
n超过20000时就会栈溢出
- 普通递归：求和操作是在“归”的过程中执行的，每层返回后都要再执行一次求和操作
- 尾递归：求和操作是在“递”的过程中执行的，“归”的过程只需层层返回
用递归求斐波那契数列的效率不是很高，当位数较多时递归层数会急剧增加，导致后面的求值会越来越慢，所以要用其它的算法
当处理“分治”相关的算法问题时，递归往往比迭代的思路更加直观，代码更加易读
| 迭代 | 递归 | |
|---|---|---|
| 实现方式 | 循环结构 | 函数调用自身 |
| 时间效率 | 效率通常较高，无函数调用开销 | 每次函数调用都会产生开销 |
| 内存使用 | 通常使用固定大小的内存空间 | 累计函数调用可能使用大量的栈帧空间 |
| 适用问题 | 适用于简单循环任务，代码直观，可读性好 | 适用于子问题分解，如树、图、分治、回溯等，代码结构简洁、清晰 |
选择迭代还是递归取决于特定问题的性质
时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势
设输入数据大小为 n，常用的时间复杂度类型如下
O(1)<O(\log n)<O(n)<O(n \log n)<O\left(n^{2}\right)<O\left(2^{n}\right)<O(n!)
\text { 常数阶 }<\text { 对数阶 }<\text { 线性阶 }<\text { 线性对数阶 }<\text { 平方阶 }<\text { 指数阶 }<\text { 阶乘阶 }
!
在实际算法中，指数阶常出现于递归函数中，指数阶增长非常迅速，在穷举法（暴力搜索，回溯等）中比较常见，对于数据规模较大的问题，指数阶是不可接受的，通常需要使用动态规划或贪心算法等来解决
与指数阶类似，对数阶也常出现于递归函数中，常出现于基于分治策略的算法中，体现了“一分为多”和“化繁为简”的算法思想，它增长缓慢，是仅次于常数阶的理想的时间复杂度
线性对数阶常出现于嵌套循环中，两层循环的时间复杂度分别为 O(\log n) 和 O(n)
主流排序算法的时间复杂度通常为 $O(n\log n)$，如快速排序、归并排序、堆排序等。
阶乘通常使用递归实现
算法的时间效率往往不是固定的，而是与输入数据的分布有关，假设输入一个长度为 n 的数组 nums，其中 nums 由 1 至 n 的数字组成，每个数字只出现一次，但元素顺序是随机打乱的，任务目标是返回元素 1 的索引，可以得到以下结论：
- 当
nums=[?,?,...,1]，即当末尾元素是 1 时，需要完整遍历数组，达到最差时间复杂度 - 当
nums=[1,?,?,...]，即当首个元素为 1 时，无论数组多长都不需要继续遍历，达到最佳时间复杂度\Omega (1)
“最差时间复杂度”对应函数渐近上界，使用大 O 记号表示，相应的，“最佳时间复杂度”对应函数渐近下界，用 \Omega 记号表示
较少使用最佳时间复杂度，而最差时间复杂度更为实用，因为它给出了一个效率安全值
算法在运行过程中使用的内存空间主要包括以下几种
- 输入空间：用于存储算法的输入数据
- 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据
- 输出空间：用于存储算法的输出数据
一般情况下，空间复杂度的统计范围是“暂存空间”+“输出空间”
暂存空间可以进一步划分为三个部分：
- 暂存数据：用于保存算法运行过程中的各种常量、变量、对象等
- 栈帧空间；用于保存调用函数的上下文数据，系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放
- 指令空间：用于保存编译后的程序指令，在实际统计中通常忽略不计
在分析一段程序的空间复杂度时，我们通常统计暂存数据、栈帧空间和输出数据三部分
!
我们通常只关注最差空间复杂度：
- 以最差输入数据为准
- 以算法运行中的峰值内存为准
在递归函数中，需要注意统计栈帧空间
常见空间复杂度类型
O(1)<O(\log n)<O(n)<O\left(n^{2}\right)<O\left(2^{n}\right)
\text { 常数阶 }<\text { 对数阶 }<\text { 线性阶 }<\text { 平方阶 }<\text { 指数阶 }
!
常数阶常见于数量与输入数据大小 n 无关的常量、变量、对象 线性阶常见于元素数量与 n 成正比的数组、链表、栈、队列等 平方阶常用于矩阵和图，元素数量与 n 成平方关系 指数阶常用于二叉树 对数阶常用于分治算法
要在时间和空间之间取舍，降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然，要么以“空间换时间”，要么以“时间换空间”，大多数情况下都是以“空间换时间”，在数据量很大的情况下，控制空间复杂度也非常重要