为什么要复杂度分析？
- 不依赖测试环境
- 不受数据量影响
大 O 复杂度表示法
算法执行效率
算法代码执行时间
复杂度公式 T(n)=O(f(n))
解释：
- T(n) 表示代码执行时间，n 表示数据规模大小
- f(n) 表示每行代码执行的次数总和
- O 表示代码的执行时间 T(n) 和 f(n) 表达式成正比
大 O 时间复杂度实际上并不代表代码真正的执行时间而是表示代码执行时间随数据规模增长的变化趋势，所以也叫 渐进时间复杂度，简称 时间复杂度
时间复杂度分析
- 只关注循环执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的时间复杂度
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
O(1)
- 是常量级时间复杂度的一种表达方法，不是只执行了一行代码
- 只要算法中不存在循环语句、递归语句，即使有成千上万行代码，时间复杂度也是 O(1)
int i = 8;
int j = 6;
int sum = i + j;
O(logn)、O(nlogn)
i=1;
while (i <= n) {
i = i * 2;
}
变量 i 的值从1开始，每循环一次就乘以2。当大于 n 时，循环结束。
所以 i 的值是
image.png
image.png
日常用语：n以2为低的对数是x，意思是 2的x次方等于n
O(m+n)、O(m*n)
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
- m,n 是表示两个数据规模，无法事先评估 m 和 n 谁的量级大所以在表示复杂度的时候就不能利用加法法则省略一个了所以是O(m+n)
- 如果是两个数据规模的嵌套循环，那么时间复杂度就是 O(m*n)
空间复杂度分析
- 空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系
- 常见空间复杂度 O(1)、O(n)、O(n^2)
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。
越高阶复杂度的算法，执行效率越低
从低阶到高阶：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)
image.png
最好、最坏情况时间复杂度
- 最好情况时间复杂度：最理想的情况下，执行代码的时间复杂度（比如，在循环中，第一个就是你要查找的元素）
- 最坏情况时间复杂度：最糟糕的情况下，执行代码的时间复杂度（比如，在循环中，没有你要查找的元素）
-
平均情况时间复杂度：我们要查找的元素在数组中的位置有 n+1 中情况，在数组的 0～n-1 位置中和不在数组中，把每种情况下，查找需要遍历的元素个数累加起来，然后除以 n+1，就可以得到需要遍历的元素个数平均值image.png
用大 O 标记法，省略掉系数、低价、常量，所以得到平均复杂度为 O(n)
- 均摊情况时间复杂度：
只有在特殊情况下,我们才需要分析一段代码的三种复杂度. 这种特殊情况就是: 同一个代码块在不同的情况下,时间复杂度有量级的差距. 这个时候我们才会采用 最好时间复杂度, 最坏时间复杂度,平均时间复杂度来 表示该段代码的时间复杂度.
image
