1、时间复杂度
1.1 时间复杂度的概念
在计算机科学中， 算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。 一个算法所花费的时间与其中语句的执行次数成正比例， 算法中的基本操作的执行次数，为算法 的时间复杂度。
ps：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。
// 请计算一下Func1中++count语句总共执行了多少次？ void Func1(int N) { int count = 0; for (int i = 0; i < N ; ++ i) { for (int j = 0; j < N ; ++ j) { ++count; } } for (int k = 0; k < 2 * N ; ++ k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); }
Func1 执行的基本操作次数 ：
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要 大概执行次数，那么这 里我们使用大 O 的渐进表示法。
1.2 大O的渐进表示法
大 O 符号（ Big O notation ）：是用于描述函数渐进行为的数学符号。
推导大 O 阶方法：
1 、用常数 1 取代运行时间中的所有加法常数。
2 、在修改后的运行次数函数中，只保留最高阶项。
3 、如果最高阶项存在且不是 1 ，则去除与这个项目相乘的常数。得到的结果就是大 O 阶。
使用大 O 的渐进表示法以后， Func1的时间复杂度为 O(N²)
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：（在一个长度为 N 数组中搜索一个数据 x）
最坏情况：任意输入规模的最大运行次数 ( 上界 )------->N次找到
平均情况：任意输入规模的期望运行次数---------->N/2次找到
最好情况：任意输入规模的最小运行次数 ( 下界 )----->1次找到
1.3常见时间复杂度计算举例
实例1：
// 计算Func2的时间复杂度？ void Func2(int N) { int count = 0; for (int k = 0; k < 2 * N ; ++ k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); }
运行次数为：2*n+10，时间复杂度为O(N)
实例2:
// 计算Func3的时间复杂度？ void Func3(int N, int M) { int count = 0; for (int k = 0; k < M; ++ k) { ++count; } for (int k = 0; k < N ; ++ k) { ++count; } printf("%d\n", count); }
运行次数为:N+M,时间复杂度为:O(N+M)
实例3:
// 计算Func4的时间复杂度？ void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d\n", count); }
运行次数为100,是常数次,时间复杂度:O(1).
实例4:
// 计算BubbleSort的时间复杂度？ void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }
运行次数为:(n-1)+(n-2)+(n-3)+…+1,就等于(n2-n)/2次.时间复杂度为O(N²)
实例5:
// 计算斐波那契递归Fib的时间复杂度？ long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
运行递归了2^N次，时间复杂度为O(2ⁿ )。
2.空间复杂度
2.1 空间复杂度的概念
空间复杂度也是一个数学表达式，是对一个算法在运行过程中 临时占用存储空间大小的量度 。
空间复杂度计算规则基本跟时间复杂度类似，也使用 大 O 渐进表示法 。
ps： 函数运行时所需要的栈空间 ( 存储参数、局部变量、一些寄存器信息等 ) 在编译期间已经确定好了，因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
2.2常见时间复杂度计算举例
实例1：
// 计算BubbleSort的空间复杂度？ void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }
使用了常数个额外空间，所以空间复杂度为 O(1)
实例2：
// 计算Fibonacci的空间复杂度？ // 返回斐波那契数列的前n项 long long* Fibonacci(size_t n) { if(n==0) return NULL; long long * fibArray = (long long *)malloc((n+1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n ; ++i) { fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; } return fibArray; }
动态开辟了N个空间，空间复杂度为 O(N)
实例3：
// 计算阶乘递归Fac的空间复杂度？ long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)
3. 常见复杂度对比
| 运行次数 | 复杂度 | 类别 |
| 5201314 | O(1) | 常数阶 |
| 3n+4 | O(N) | 线性阶 |
| 3n²+4n+5 | O(N²) | 平方阶 |
| 3log(2)n+4 | O(log₂N) | 对数阶 |
| 2n+3nlog(2)n+14 | O(N*log₂N) | NlogN阶 |
| n³+2n²+4n+6 | O(n³) | 立方阶 |
| 2ⁿ | O（2ⁿ） | 指数阶 |
常见的渐近时间复杂度为
0(1) < (O(log₂n)< O(n) < O(nlog₂n) < O(n²) < O(n³) < 0(2ⁿ) < 0(n!) < O(nⁿ)
❤️结语：
本次精彩内容已圆满结束！希望各位读者在阅读过程中能够收获满满。在此，特别感谢各位读者的支持与三连赞。如果文章中存在任何问题或不足之处，欢迎在评论区留言，蜗牛必定会认真对待并加以改进，以便为大家呈现更优质的文章。你们的支持与鼓励，将是博主不断前进的最大动力。再次感谢大家的陪伴与支持！
