时间复杂度
什么是时间复杂度？
代码执行时间随数据规模增长的变化趋势，前面这句话可能有点难以理解，其实时间复杂度可以理解为，代码执行的次数
时间复杂度用什么来表示？
用大O表示法来表示时间复杂度
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。大O表示法：
T(n) = O(f(n))
1）T(n)：表示代码执行的时间
2）n：表示数据规模的大小
3）f(n)：表示每行代码执行次数的总和
时间复杂度分析：
1.关注循环次数最多的一段代码
2.加法法则：总复杂度等于量级最大的那段代码的复杂度
3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
时间复杂度用大O表示法来表示的话，大概有多少种表示情况？
1、常数阶：O(1)，所有括号内为已知的数字，都可以认为是常数阶O(1)
1 public class test { 2 3 public static void main(String[] args) { 4 5 int a = 0; //执行一次 6 7 int b = 0; //执行一次 8 9 System.out.println(a + b); //执行一次 10 11 } 12 13 }
上面有3行代码需要执行，每行代码执行一次，所以时间复杂度为O(3)，又因为括号里的是常数，所以我们可以认为时间复杂度为O(1)
注意：O(1)是种表示方法，一般情况下，只要算法中不存在循环或者递归语句，即使有几百上千的代码，时间复杂度都为O(1)
2、对数阶：O(logn)
int i = 1;
while(i <= n){
i = i * 2;
}
从上面可以知道，随着i的变化，2行的执行次数在减少，当i > n时，循环结束，在循环中的语句，每次循环都 * 2，根据高中学过的等比数列可以知道，2^0 + 2^1 + ... +2^x = n --> 在这里我们只要知道x值就好了，所以 2^x = n，x=log2 n，所以这段代码的复杂度为O(log2 n)
如果我们把代码改为：
int i = 1;
while(i <= n){
i = i * 5;
}
上面这一行的时间复杂度为O(log5 n)，跟上面的对比，O(log2 n)和O(log5 n)都可以看作为O(logn)，在采用大O表示法标记时间复杂度的时候，可以忽略系数
3、线性代数阶：O(nlogn)，可以根据上面的O(logn)去改造，把上面的代码再执行n遍，就可以得到了
4、线性阶：O(n)
for(int i = 0; i < n; i++){
System.out.println("O(n)");
}
上面的循环语句要执行n次，里面的输出语句也要输出n次，所以总执行次数为2n，即时间复杂度为O(2n)，可以记为O(n)，我的理解是，当到达无限大的时候，只要乘数是有限的数字，那么n前面的有限数字可以忽略不计，除非去乘无限的数字
5、平方阶：O(n^2)
6、阶乘阶：O(!n)
7、指数阶：O(2^n)
8、立方阶：O(n^3)
......
低阶到高阶排序：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)
时间复杂度的集中分析情况
1.最好的时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
2.最坏时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
例子：比如在有n个数字的数组中，寻找一个数字，幸运的话，第一个就找到了，可以认为是最好的时间复杂度；如果运气不好的话，要循环n遍才能找到，这可以认为是最坏的时间复杂度。
3.平均时间复杂度
4.均摊时间复杂度
原文：https://blog.csdn.net/weixin_41640994/article/details/88287520
