一、时间复杂度
1. 什么是时间复杂度
- 记为大O，是衡量算法运行效率的重要指标，描述了算法运行所需时间是如何随着输入规模（通常用n来表示）变化的（一般）。也可以说用来表示算法语句总的执行次数随n的增长趋势。
2. 常见时间复杂度的分类
| 时间复杂度 | 描述 | 例子 |
|---|---|---|
| O(1) | 常数时间：与输入大小无关 | 访问数组中的某元素 |
| O(log n) | 对数时间：规模缩小一半 | 二分查找 |
| O(n) | 线性时间：与输入成正比 | 遍历数组 |
| O(n log n) | 线性对数时间 | 快速排序、归并排序 |
| O(n^2) | 二次方时间：嵌套循环 | 冒泡排序、插入排序 |
| O(2^n) | 指数时间 | 未优化递归解决斐波那契数列 |
| O(n!) | 阶乘时间 | 解决全排列问题 |
3. 时间复杂度的分析方法
- 确定基本操作的时间复杂度
- 分析循环结构或递归共识
- 省略低阶项和常数，仅保留增长最快的项
二、空间复杂度
1. 什么是空间复杂度
- 同样使用大O来表示，用来衡量算法在运行过程中所需的存储空间随输入规模(n)的变化。
2. 空间复杂度的分类
| 空间复杂度 | 描述 | 示例算法 |
|---|---|---|
| O(1) | 常数空间：不需要额外空间 | 原地排序算法（如冒泡排序） |
| O(log n) | 对数空间：递归深度相关 | 二分查找递归实现 |
| O(n) | 线性空间：与输入大小相关 | 动态规划、哈希表 |
| O(n^2) | 二次空间：二维矩阵相关 | 矩阵操作、图的存储 |
3. 空间复杂度的分析方法
- 统计变量：分析算法中引入了多少额外变量。
- 普通变量占用 O(1) 空间。
- 数组或列表根据其大小占用 O(n) 空间。
- 递归深度：递归算法会消耗额外的栈空间，其大小由递归深度决定。
- 递归调用栈的深度为 ( d )，每次调用需要固定大小的空间，则总空间复杂度为 O(d) 。
- 动态数据结构：动态创建的结构（如链表、树、哈希表）占用的空间与输入规模相关。
4. 时间复杂度和空间复杂度的权衡：
- 有些算法可以通过增加空间来换取时间效率（如动态规划的备忘录法）。
- 也可以通过减少空间来牺牲时间（如递归转循环）。
三、排序算法的比较
1. 基于比较的排序
- 依赖元素之间的比较操作。
- 包括冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序等。
2. 非比较排序
- 不直接比较元素大小，而是利用元素的特性。
- 包括计数排序、桶排序和基数排序。
3. 各排序算法的比较
| 排序算法 | 时间复杂度（最坏/平均/最好） | 空间复杂度 | 稳定性 | 特点与适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) / O(n^2) / O(n) | O(1) | 稳定 | 简单实现，适合小规模数据或数据接近有序的场景 |
| 选择排序 | O(n^2) | O(1) | 不稳定 | 简单但效率低，不适合大数据 |
| 插入排序 | O(n^2) / O(n^2) / O(n) | O(1) | 稳定 | 适合少量数据或几乎有序的数组 |
| 归并排序 | O(n log n) | O(n) | 稳定 | 适合大数据、需要稳定性的场景 |
| 快速排序 | O(n^2) / O(n log n) / O(n log n) | O( log n) | 不稳定 | 高效通用的排序算法，适合大规模数据 |
| 堆排序 | O(n log n) | O(1) | 不稳定 | 用于堆结构的场景，内存使用较少 |
| 计数排序 | O(n + k) | O(n + k) | 稳定 | 适用于数据范围较小且整数数据的场景 |
| 桶排序 | O(n + k) | O(n + k) | 稳定 | 适合数据均匀分布的场景 |
| 基数排序 | O(n * k) | O(n + k) | 稳定 | 适合多位数值或字符串的排序 |
- 稳定性：当值相等时，排序后是否保持原顺序。
四、各算法介绍
1. 冒泡排序
- 原理：两两比较相邻元素，将较大的元素逐步“冒泡”到数组末尾。
- 特点：简单易懂，但性能较低。
- 适用场景：小数据量或数据接近有序时。
2. 选择排序
- 原理：每次从未排序部分选择最小（或最大）的元素，放到已排序部分末尾。
- 特点：实现简单，但多次交换导致效率低。
- 适用场景：数据量小，稳定性不要求高。
3. 插入排序
- 原理：将未排序元素逐一插入到已排序部分的适当位置。
- 特点：对几乎有序的数据效果较好。
- 适用场景：小规模数据、接近有序数据。
4. 快速排序
- 原理：选定一个基准值，将数组划分为小于和大于基准值的两部分，递归排序。
- 特点：平均性能优越，但最坏情况下效率低（如有序数组）。
- 适用场景：大规模数据，效率高要求。
5. 归并排序
- 原理：将数组递归分成两部分，分别排序后合并。
- 特点：稳定且效率高，但需要额外空间。
- 适用场景：需要稳定性，且内存足够的场景。
总结与选择建议
-
数据量小或几乎有序：
- 使用 插入排序 或 冒泡排序。
-
大数据量，追求效率：
- 快速排序：时间效率高，适用范围广。
- 归并排序：稳定，适合外部排序。
-
内存有限：
- 堆排序：占用空间小，但不稳定。
-
整数或范围较小数据（外部排序）：
- 计数排序、桶排序、基数排序。
-
不稳定的排序：
- 选择排序、快速排序、堆排序
-
时间复杂度稳定为O( n log n )的排序
- 归并排序、堆排序
-
速记方法：
- 平均时间复杂度O(n^2)，较为低效，但空间复杂度为O(1)的排序算法：
- 冒泡：稳定
- 选择：不稳定
- 插入：稳定
- 平均时间复杂度O(n log n)，较为高效的算法：
- 归并：稳定，空间复杂度为O(n)
- 快速：不稳定，空间复杂度为O(log n)，时间复杂度最坏时为O(n^2)
- 堆：不稳定，空间复杂度为O(1)
- 平均时间复杂度O(n^2)，较为低效，但空间复杂度为O(1)的排序算法：
