时间复杂度
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势
只关注循环执行次数最多的一段代码
大 O 这种复杂度表示方法只是表示一种变化趋势。
- 我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。
所以，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了
// 比如下面这段代码，总的时间复杂度就是 O(n)int cal(int n) {int sum = 0;int i = 1;for (; i <= n; ++i) {sum = sum + i;}return sum;}
加法法则：总复杂度等于量级最大的那段代码的复杂度
总的时间复杂度就等于量级最大的那段代码的时间复杂度。
- 那我们将这个规律抽象成公式就是：
● 如果 T1(n)=O(f(n))，T2(n)=O(g(n))；● 那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
```javascript 如果 T1(n)=O(f(n))，T2(n)=O(g(n))；
那么 T(n)=T1(n)T2(n) = O(f(n))O(g(n)) = O(f(n)*g(n)).
也就是说，假设 T1(n) = O(n)，T2(n) = O(n2)，则 T1(n) * T2(n) = O(n3)。落实到具体的代码上，我们可以把乘法法则看成是嵌套循环，比如```javascriptint cal(int n) {int ret = 0;int i = 1;for (; i < n; ++i) {ret = ret + f(i);}}int f(int n) {int sum = 0;int i = 1;for (; i < n; ++i) {sum = sum + i;}return sum;}
我们单独看 cal() 函数。假设 f() 只是一个普通的操作，那第 4～6 行的时间复杂度就是，T1(n) = O(n)。但 f() 函数本身不是一个简单的操作，它的时间复杂度是 T2(n) = O(n)，所以，整个 cal() 函数的时间复杂度就是，T(n) = T1(n) T2(n) = O(nn) = O(n2)。
几种常见时间复杂度实例分析
<br />对于罗列的复杂度量级，我们可以粗略地分为两类，
- 多项式量级和非多项式量级。
- 其中，非多项式量级只有两个：O(2n) 和 O(n!)。
[ ] 我们把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。
O(1)
O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。
int i = 8;int j = 6;int sum = i + j;
只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)
O(logn) & O(nlogn)
换底公式
<br /> 
i=1;while (i <= n) {i = i * 2;}
[ ] O(logn)
比如这段代码执行多少次呢？
每次循环i都变成之前的2 倍
通过 2^x=n 求解 x , x=log2n，所以，这段代码的时间复杂度就是 O(log2n)。
- O(nlogn)
根据乘法法则
如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是O(nlogn)。
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)。
注意和加法法则不同，加法法则代表的是同一个 数据规模
空间复杂度
- 表示算法的存储空间与数据规模之间的增长关系
第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。void print(int n) {int i = 0;int[] a = new int[n];for (i; i <n; ++i) {a[i] = i * i;}}
总结
复杂度趋势图
若有收获，就点个赞吧
0 人点赞
