算法基础概念
学习具体的算法之前，有必要将算法的基础概念理解清楚,对基础概念有了初步认识，再进行进阶学习和实践巩固，也许效果会更好。
算法复杂度
当我们谈论算法复杂度时，主要有两个层面的目标
- 问题的解法：正确解法。
- 最优解法：最高效的算法。
如何衡量：即从空间和时间的维度去看。
- 时间效率：算法运行速度的快慢。
- 空间效率：算法占用内存空间的大小
我们主要关注两种类型：时间复杂度和空间复杂度。这两种复杂度帮助我们评估算法的效率，从而确定算法对资源的消耗。
时间复杂度
时间复杂度是指执行算法所需要的计算工作量。它通常以输入大小的函数来表示，帮助我们理解算法随着输入大小增加的运行时间增长速度。常见的时间复杂度包括：
| 时间复杂度 | 描述 | 典型算法 |
|---|---|---|
| O(1) | 常数时间，执行时间不随输入大小变化 | 直接访问数组元素 |
| O(log n) | 对数时间，执行时间随输入大小呈对数增长 | 二分查找 |
| O(n) | 线性时间，执行时间与输入大小成正比 | 线性搜索 |
| O(n log n) | 线性对数时间，执行时间随输入大小呈线性对数增长 | 快速排序、归并排序 |
| O(n^2) | 二次时间，执行时间与输入大小的平方成正比 | 冒泡排序、选择排序、插入排序 |
| O(n^3) | 立方时间，执行时间与输入大小的立方成正比 | 简单的矩阵乘法 |
| O(2^n) | 指数时间，执行时间以指数方式增加 | 某些递归问题解决方案 |
| O(n!) | 阶乘时间，执行时间随输入大小的阶乘增加 | 旅行商问题的暴力解法 |
其中
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < o(2^n) < O(n!)
算法的时间效率往往不是固定的，而是与输入数据的分布有关。从而分为最差、最佳、平均时间复杂度
- 最差：最差时间复杂度是指在所有可能的输入情况中，算法运行时间的上界。换句话说，它代表了算法在最不利情况下的执行时间。
- 最佳：最佳时间复杂度是指在所有可能的输入情况中，算法运行时间的下界。它描述了算法在最理想情况下的执行时间。
- 平均： 平均时间复杂度考虑了所有可能的输入并计算算法的平均运行时间。理解平均时间复杂度可能需要统计和概率知识，因为它通常基于假设所有输入都同样可能出现。
空间复杂度
算法在运行过程中使用的内存空间主要包括以下几种。
- 输入空间：用于存储算法的输入数据。
- 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据。
- 输出空间：用于存储算法的输出数据。
一般我们计算暂存空间和输出空间。
空间复杂度是指执行算法所需要的最大内存空间。它同样以输入大小的函数来表示，帮助我们理解算法随着输入大小增加的内存消耗。例如，一个简单的线性搜索算法可能具有 O(1)的空间复杂度，因为它只需要存储一个元素即可进行比较；而归并排序具有 O(n)的空间复杂度，因为它在排序过程中需要与原数组相同大小的辅助空间。
| 空间复杂度 | 描述 | 典型算法 |
|---|---|---|
| O(1) | 常数空间，所需额外内存不随输入大小变化 | 简单变量的操作 |
| O(log n) | 对数空间，需要的额外空间随输入大小呈对数增长 | 递归算法在递归栈上的空间需求 |
| O(n) | 线性空间，所需额外内存与输入大小成正比 | 动态数组、哈希表 |
| O(n^2) | 二次空间，所需额外内存与输入大小的平方成正比 | 邻接矩阵表示的图 |
O(1) < O(log n) < O(n) < O(n^2) < O(2^n)
我们如此看重空间复杂度和时间复杂度，是为了让我们根据空间，时间的效率，以及目前我们的资源，来做算法的取舍。