文章目录
- 一、什么是复杂度？
- 二、大O表示法
- 三、时间复杂度计算
- 四、常见复杂度的比较
- 五、算法优化的核心方法论
- 六、常见算法复杂度
- 五、总结
一、什么是复杂度？
复杂度是衡量代码运行效率的重要的度量因素。 而复杂度主要就是指时间复杂度和空间复杂度。
首先，时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。当我们面前有多个算法时，我们可以通过计算时间复杂度，判断出哪一个算法在具体执行时花费时间最多和最少。
空间复杂度则是对一个算法在运行过程中临时占用电脑存储空间大小的量度。
在过去，由于计算机性能低下，系统存储空间很小，这种情况下，降低空间的损耗就极其重要了！所以，在这种情况下，程序员要考虑的就是尽可能的降低空间复杂度。
但是，时间复杂度和空间复杂度往往是相对的。降低空间消耗的代价就是增加时间。
而现在，硬件技术发展迅速，在强大的硬件支持下，存储空间已经不是困扰人们的问题了。这种情况下，人们要求的是更快的运行速率。再加上现在大数据盛行。牺牲廉价的空间来换取宝贵的时间就很有必要了！
所以，我们现在研究的是：如何用算法有效的降低时间复杂度！
好，现在我们已经了解了复杂度的作用，那应该如何去计算复杂度呢？
二、大O表示法
复杂度是一个关于输入数据量 n 的函数。
假设你的代码复杂度是 f(n)，那么就用个大写字母 O 和括号，把 f(n) 括起来就可以了，即 O(f(n))。例如，O(n) 表示的是，复杂度与计算实例的个数 n 线性相关；O(logn) 表示的是，复杂度与计算实例的个数 n 对数相关。
通常，复杂度的计算方法遵循以下几个原则：
- 首先，复杂度与具体的常系数无关，例如 O(n) 和 O(2n) 表示的是同样的复杂度。我们详细分析下，O(2n) 等于O(n+n)，也等于 O(n) + O(n)。也就是说，一段 O(n) 复杂度的代码只是先后执行两遍 O(n)，其复杂度是一致的。
- 其次，多项式级的复杂度相加的时候，选择高者作为结果，例如 O(n²)+O(n) 和 O(n²)表示的是同样的复杂度。具体分析一下就是，O(n²)+O(n) = O(n²+n)。随着 n越来越大，二阶多项式的变化率是要比一阶多项式更大的。因此，只需要通过更大变化率的二阶多项式来表征复杂度就可以了。
值得一提的是，O(1) 也是表示一个特殊复杂度，含义为某个任务通过有限可数的资源即可完成。此处有限可数的具体意义是，与输入数据量 n 无关。
三、时间复杂度计算
- 常数阶
int i;
for (i = 0; i < 100; i++){
/ * * /
}
这里只循环100次。不随着输入数据量 n 增加而增长，所以，此类算法的时间复杂度是O(1)。
- 线性阶
int i;
for (i = 0; i < n; i++){
/ * * /
}
它是一个 for 循环，时间复杂度为 O(n) ， 因为循环体中的代码须要执行n次。
- 对数阶
int count = 1;
while (count < n){
count = count * 2;
/* */
}
由于每次 count 乘以 2 之后，就距离 n 更近了一分。 也就是说，有多少个 2 相乘后大于 n ，则会退出循环。由 2^x=n 得到x=log2(n) 。 所以这个循环的时间复杂度为O(log(n)) 。
- 平方阶
int i , j ;
for (i = 0; i < n; i++){
for ( j = 0 ; j < n ; j++ ){
/* */
}
}
而对于外层的循环，不过是内部这个时间复杂度为 O(n)的语句，再循环 n 次 。 所以这段代码的时间复杂度为 O(n^2)。
如果外循环的循环次数改为了m， 时间复杂度就变为 O(m×n)。
int i , j ;
for (i = 0; i < m; i++){
for ( j = 0 ; j < n ; j++ ){
/* */
}
}
所以我们可以总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
四、常见复杂度的比较
常见的时间复杂度有：
常数阶O(1),
对数阶O(log2 n),
线性阶O(n),
线性对数阶O(n log2 n),
平方阶O(n^2)，
立方阶O(n^3)
k次方阶O(n^K),
指数阶O(2^n)。
随着n的不断增大，时间复杂度不断增大，算法花费时间越多。
为了更好理解，我们来看一些数据。假设某个计算任务需要处理 10万 条数据。你编写的代码：
- 如果是 O(n²) 的时间复杂度，那么计算的次数就大概是 100 亿次左右。
- 如果是 O(n)，那么计算的次数就是 10万 次左右。
- 如果这个工程师再厉害一些，能在 O(log n) 的复杂度下完成任务，那么计算的次数就是 17 次左右（log 100000 =16.61，计算机通常是二分法，这里的对数可以以 2 为底去估计）。
- 而O（1）是固定次数的计算，如：计算任务需要处理 10万 条数据，它是计算100次； 计算任务需要处理 10 条数据，它是还计算100次； 所以并不能和其他O(log n)， O(n)，O(n²) 混为一谈！
五、算法优化的核心方法论
- 第一步，暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。
- 第二步，无效操作处理。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。
- 第三步，时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移。
第一步的暴力解法没有太多的套路，只要围绕你面临的问题出发，大胆发挥想象去尝试解决即可。
第二步的无效操作处理中，你需要学会并掌握递归、二分法、排序、动态规划等常用的算法思维。通过各种算法将代码中的无效计算（冗余时间）、无效存储（冗余空间）剔除，降低时间或空间复杂度。
第三步的时空转换，你需要对数据的操作进行细分，全面掌握常见数据结构的基础知识。再围绕问题，有针对性的设计数据结构、采用合理的算法思维，去不断完成时空转移，用空间换取时间，降低时间复杂度。
六、常见算法复杂度
| 算法/排序 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 线性查找（Linear Search） | 最好情况 O(1)，平均情况 O(n)，最坏情况 O(n) | O(1) |
| 二分查找（Binary Search） | 最好情况 O(1)，平均情况 O(log n)，最坏情况 O(log n) | O(1) |
| 冒泡排序（Bubble Sort） | 最好情况 O(n)，平均情况 O(n^2)，最坏情况 O(n^2) | O(1) |
| 快速排序（Quick Sort） | 最好情况 O(n log n)，平均情况 O(n log n)，最坏情况 O(n^2) | 最好情况 O(log n)，平均情况 O(log n)，最坏情况 O(n) |
| 堆排序（Heap Sort） | 最好情况 O(n log n)，平均情况 O(n log n)，最坏情况 O(n log n) | O(1) |
| 插入排序（Insertion Sort） | 最好情况 O(n)，平均情况 O(n^2)，最坏情况 O(n^2) | O(1) |
| 选择排序（Selection Sort） | 最好情况 O(n^2)，平均情况 O(n^2)，最坏情况 O(n^2) | O(1) |
| 归并排序（Merge Sort） | 最好情况 O(n log n)，平均情况 O(n log n)，最坏情况 O(n log n) | O(n) |
| 希尔排序（Shell Sort） | 最好情况取决于增量序列，平均情况取决于增量序列，最坏情况取决于增量序列 | O(1) |
| 布隆过滤器（Bloom Filter） | 插入和查询都是 O(k)，其中 k 是哈希函数的数量 | 取决于哈希函数数量和位数组大小 |
| 动态规划（Dynamic Programming） | 根据问题而定，通常在 O(n^2) 到 O(n^3) 之间 | 根据问题而定，通常在 O(n) 到 O(n^2) 之间 |
| KMP 算法（Knuth-Morris-Pratt Algorithm） | O(m + n)，其中 m 是模式串长度，n 是文本串长度 | O(m)，其中 m 是模式串长度 |
| Prim 算法（Minimum Spanning Tree） | O(V^2) 或 O(E log V)，V 是顶点数，E 是边数 | O(V) 或 O(E)，取决于具体实现方式 |
| Kruskal 算法（Minimum Spanning Tree） | O(E log E)，E 是边数 | O(E) |
| 贪心算法（Greedy Algorithm） | 根据问题而定，通常在 O(n log n) 到 O(n^2) 之间 | O(1) 或 O(n)，取决于具体实现方式 |
| 拓扑排序算法（Topological Sorting） | O(V + E)，其中 V 是顶点数，E 是边数 | O(V) |
| Dijkstra 算法（Shortest Path） | O(V^2) 或 O(E log V)，V 是顶点数，E 是边数 | O(V^2) 或 O(VE)，取决于具体实现方式 |
| Bellman-Ford 算法（Shortest Path） | O(VE)，V 是顶点数，E 是边数 | O(VE) |
| Floyd-Warshall 算法（Shortest Path） | O(V^3)，V 是顶点数 | O(V^2) |
| Boyer-Moore 算法（String Matching） | 最坏情况下 O(mn)，其中 m 是模式串长度，n 是文本串长度 | O(m)，其中 m 是模式串长度 |
| 哈希表（Hash Table） | 插入、查找、删除操作平均情况下为 O(1)，最坏情况下为 O(n) | 取决于哈希表大小和存储的元素数量 |
| 最大子序列和问题（Maximum Subarray Problem） | O(n)，其中 n 是数组的长度 | O(1) |
| 括号匹配问题（Parentheses Matching Problem） | O(n)，其中 n 是字符串的长度 | O(n) |
| 深度学习算法（Deep Learning Algorithms） | 取决于神经网络的结构和训练数据量 | 取决于神经网络的参数数量和层数 |
| 布隆过滤器（Bloom Filter） | 插入和查询操作都是 O(k)，其中 k 是哈希函数的数量 | 取决于哈希函数数量和位数组大小 |
| Rabin-Karp 字符串匹配算法 | 平均情况下为 O(n + m)，最坏情况下为 O(nm) | O(1) |
| RSA 公钥加密算法 | 取决于素数的大小和加密数据的长度 | O(1) |
| 哈夫曼编码（Huffman Coding） | O(n log n)，其中 n 是字符集的大小 | 取决于字符集的大小和编码长度 |
| 最长公共子序列（Longest Common Subsequence） | O(mn)，其中 m 和 n 分别是两个字符串的长度 | O(mn) |
| 最大流算法（Max Flow Algorithm） | O(V * E^2)，其中 V 是顶点数，E 是边数 | O(V^2) |
| 最大子数组问题（Maximum Subarray Problem） | O(n)，其中 n 是数组的长度 | O(1) |
| 拓扑排序算法（Topological Sorting） | O(V + E)，其中 V 是顶点数，E 是边数 | O(V) |
| 最短路径算法（Shortest Path Algorithms） | Dijkstra 算法：O(V^2) 或 O(E log V) Bellman-Ford 算法：O(VE) Floyd-Warshall 算法：O(V^3) | O(V^2) 或 O(VE) |
| 最小生成树算法（Minimum Spanning Tree Algorithms） | Prim 算法：O(V^2) 或 O(E log V) Kruskal 算法：O(E log E) | O(V) 或 O(E) |
| 贪心算法（Greedy Algorithm） | 根据问题而定，通常在 O(n log n) 到 O(n^2) 之间 | O(1) 或 O(n) |
五、总结
OK，今天的内容到这儿就结束了。相信你对复杂度的概念有了进一步的认识。总结一下:
程序优化、算法优化、时间复杂度和空间复杂度优化是提高程序性能和效率的关键。程序优化是指通过改进代码结构、算法、数据结构等方面来提高程序的运行速度和资源利用率。算法优化则是针对特定问题设计更高效的算法，以减少计算时间和资源消耗。时间复杂度是衡量算法执行时间的指标，通常用大O符号表示，优化算法可以降低时间复杂度。空间复杂度是衡量算法内存消耗的指标，优化算法可以降低空间复杂度。综上所述，通过程序优化、算法优化、时间复杂度和空间复杂度优化可以使程序更加高效和节约资源。
-
程序优化：
- 优化代码结构，消除冗余和重复代码，提高代码可读性和维护性。
- 使用高效的数据结构和算法，避免不必要的循环和操作。
- 减少内存分配和释放次数，避免内存泄漏和频繁的内存操作。
-
算法优化：
- 选择合适的算法来解决问题，比如排序、查找、图算法等。
- 优化算法的实现，减少不必要的计算和操作。
- 考虑特定问题的特点，设计针对性的算法来提高效率。
-
时间复杂度优化：
- 分析算法的时间复杂度，选择具有更低时间复杂度的算法。
- 避免嵌套循环和递归调用，优化算法的执行路径。
- 尽量减少不必要的计算和操作，提高算法的执行效率。
-
空间复杂度优化：
- 分析算法的空间复杂度，选择具有更低空间复杂度的算法。
- 使用合适的数据结构来减少内存消耗，比如使用数组代替链表。
- 及时释放不再需要的内存，避免内存泄漏和内存碎片化。
