前言
一个算法的优劣好坏, 会决定一个程序运行的时间, 空间. 也许当小数据量的时候, 这种影响并不明显, 但是当有巨量数据的时候, 算法的好坏带来的性能差异就会出天差地别. 可以说直接影响了一个产品的高度和广度. 每个程序员都想用最优的算法解决问题, 我们期待自己写出的代码是简洁, 高效的. 但是如何评判一个算法的好坏呢? 时间复杂度和空间复杂度就是一个很好的标准.
1. 时间复杂度
1.1 概念
执行算法所需要的计算工作量
1.2 基本执行次数 T(n)
根据计算, 得出的该算法在输入数据量为 n 时的, 实际执行次数
1.3 时间复杂度
根据基本执行次数, 去除系数, 常数项等得到的渐进时间复杂度. 用大 O 表示法. 也就是说, 随着数据量的剧增, 不同常数项和系数, 已经大致不能够影响该算法的基本执行次数. 常数项和系数对于计算时间复杂度无意义
1.4 举例说明
T(n) = 2: 该函数总共执行两条语句, 所以基本执行次数为 2;
时间复杂度为 O(1): 该函数的基本执行次数只有常数项, 所以时间复杂度为 O(1)
- void test(int n)
- {
- int a;
- a = 10;
- }
T(n) = 2n: 该函数共循环 n 次, 每次执行 2 条语句, 所以基本执行次数为 2n. 时间复杂度舍弃系数, 为 O(n)
- void test(int n)
- {
- int cnt;
- for (cnt = 0; cnt < n; cnt++) {
- int a;
- a= 10;
- }
- }
- T(n) = 2 * (1 + 2 + 3 + 4 + ... + n) + 1 =
2 * (1 + n) * n / 2 + 1 = n^2 + n + 1. 因为共执行 (1 + 2 + 3 + 4 + ... + n) 次循环, 每次循环执行 2 条语句, 所有循环结束后, 最后又执行了 1 条语句, 所以执行次数如上; 时间复杂度为 O(n^2), 因为 n 和常数项 1 忽略, 它们在数据量剧增的时候, 对于执行次数曲线几乎没有影响了
- void test(int n)
- {
- int cnt1, cnt2;
- for (cnt1 = 0; cnt1 < n; cnt1++) {
- for (cnt2 = cnt1; cnt2 < n; cnt2++) {
- int a;
- a = 10;
- }
- }
- a = 11;
- }
T(n) = 2 * logn 因为每次循环执行 2 条语句, 共执行 logn 次循环; 时间复杂度为 O(logn), 忽略掉系数 2
- void test(int n)
- {
- int cnt;
- for (cnt = 1; cnt < n; cnt *= 2) {
- int a;
- a = 10;
- }
- }
T(n) = n * logn * 2 因为每次循环 2 条语句, 共执行 n * logn 次循环; 时间复杂度为 O(nlogn), 忽略掉系数 2
- void test(int n)
- {
- int cnt1, cnt2;
- for (cnt1 = 0; cnt1 < n; cnt1++) {
- for (cnt2 = 1; cnt2 < n; cnt2 *= 2) {
- int a;
- a = 10;
- }
- }
- }
T(n) = 2 * n^3 因为每次循环 2 条语句, 共执行 n^3 次循环; 时间复杂度为 O(n^3), 忽略掉系数 2
- void test(int n)
- {
- int cnt1, cnt2, cnt3;
- for (cnt1 = 0; cnt1 < n; cnt1++) {
- for (cnt2 = 0; cnt2 < n; cnt2++) {
- for (cnt3 = 0; cnt3 < n; cnt3++) {
- int a;
- a = 10;
- }
- }
- }
- }
斐波那契数列的递归实现, 每次调用该函数都会分解, 然后要再调用 2 次该函数. 所以时间复杂度为 O(2^n)
- int test(int n)
- {
- if (n == 0 || n == 1) {
- return 1;
- }
- return (test(n-1) + test(n-2));
- }
1.5 时间复杂度比较
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
2. 空间复杂度
2.1 概念
一个算法所占用的存储空间主要包括:
程序本身所占用的空间
输入输出变量所占用的空间
动态分配的临时空间, 通常指辅助变量
输入数据所占空间只取决于问题本身, 和算法无关. 我们所说的空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度, 即第三项. 通常来说, 只要算法不涉及到动态分配的空间以及递归, 栈所需的空间, 空间复杂度通常为 0(1).
2.2 举例说明
S(n) = O(1). 空间复杂度为 O(1), 因为只有 a, b, c, cnt 四个临时变量. 且临时变量个数和输入数据规模无关.
- int test(int n)
- {
- int a, b, c;
- int cnt;
- for (cnt = 0; cnt < n; cnt++) {
- a += cnt;
- b += a;
- c += b;
- }
- }
S(n) = O(n). 空间复杂度为 O(n), 因为每次递归都会创建一个新的临时变量 a. 且共递归 n 次.
- int test(int n)
- {
- int a = 1;
- if (n == 0) {
- return 1;
- }
- n -= a;
- return test(n);
- }
3. 参考文献
[1] 李灵晖. 数据结构与算法 - 函数的渐近增长 [DB/OL]., 2015
[2]soledad. 时间复杂度和空间复杂度 [DB/OL]. https://segmentfault.com/a/1190000016168727 , 2018
[3]raymondCaptain.(数据结构) 十分钟搞定时间复杂度 (算法的时间复杂度)[DB/OL]. https://www.jianshu.com/p/f4cca5ce055a , 2017
[4]Java 资讯库. 最详细的解说 - 时间和空间复杂度 [DB/OL]. https://www.jianshu.com/p/1ac6ad4069f8 , 2018
[5] 大魔王老 Z. 空间复杂度 (Space Complexity). https://www.cnblogs.com/zang1998/p/11552931.html , 2019
4. 后记
感谢大家的阅读, 大家喜欢的请帮忙点下推荐. 后面会继续出精彩的内容, 敬请期待!
敬告:
本文原创, 欢迎大家学习转载_
转载请在显著位置注明:
博主 ID:CrazyCatJack
原始博文链接地址: https://www.cnblogs.com/CrazyCatJack/p/12652242.html
CrazyCatJack
来源: http://www.bubuko.com/infodetail-3496099.html