大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
一、概述
先放百科上的说法：
算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。
时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
例如，如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3).
二、时间频度
要理解时间复杂度，需要先理解时间频度，而时间频度简单的说，就是算法中语句的执行次数。
举个例子：
要计算1+2+…+100，现在有两种算法
public int fun1(int n){
int total;
for(int i = 0; i <= n; i++){
total+=i;
}
return total;
}
public int fun2(int n){
int total = (1 + n)*n/2;
return total;
}
我们可以看见，对于fun1()这个方法，不管n多大，永远需要执行n+1次，也就是说他的时间频度是T(n)=n+1,
而对与fun2()来说，不管n多大都只需要执行1次，所以他的时间频度T(n)=1。
当n趋向无穷大时，有三个忽略：
1.忽略常数项
比如T(n)=2n+1，当n趋向无穷大时，可以忽略常数项1；
参见下图：
- 2n+20 和 2n 随着n 变大，执行曲线无限接近, 20可以忽略
- 3n+10 和 3n 随着n 变大，执行曲线无限接近, 10可以忽略
![解惑3：时间频度，算法时间复杂度[通俗易懂]](http://qn.javajgs.com/20220816/b552af4a-c514-49c0-995a-35a022d819a820220816199afaa4-7a3f-4be2-8fd2-d660d385a70d1.jpg)
![解惑3：时间频度，算法时间复杂度[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
2.忽略低次项
比如T(n)=2n+3n^8，当n趋向无穷大时，可以忽略低次项及其系数2n；
参见下图：
- 2n^2+3n+10 和 2n^2 随着n 变大, 执行曲线无限接近, 可以忽略 3n+10
- n^2+5n+20 和 n^2 随着n 变大,执行曲线无限接近, 可以忽略 5n+20
![解惑3：时间频度，算法时间复杂度[通俗易懂]](http://qn.javajgs.com/20220816/8c50f37c-32f4-4dd2-b490-93503300c68c20220816c4bae2d2-09b9-4519-beb0-62fcceb5953d1.jpg)
3.忽略系数
比如T(n)=2n^8，当n趋向无穷大时，可以忽略系数2。
参见下图：
- 随着n值变大，5n^2+7n 和 3n^2 + 2n ，执行曲线重合, 说明 这种情况下, 5和3可以忽略。
- 而n^3+5n 和 6n^3+4n ，执行曲线分离，说明多少次方式关键
![解惑3：时间频度，算法时间复杂度[通俗易懂]](http://qn.javajgs.com/20220816/c15bad8e-b20d-4aeb-a7d4-5c8e67cf3a112022081683331166-f740-4922-badd-f43abaf4822d1.jpg)
三、时间复杂度
我们现在理解了时间频度的T(n)的含义，假设当有一个辅助函数f(n)，使得当n趋近无穷大时，T(n)/f(n)的极限值为不等于0的常数，就叫f(n)为T(n)的同量级函数，记作T(n)=O(f(n))，
称O(f(n))为算法的时间渐进复杂度，也就是时间复杂度。
又根据时间频度T(n)的“三个忽略”原则，我们可以知道时间复杂度是这样得到的：
- 忽略所有常数
- 只保留函数中的最高阶项
- 去掉最高阶项的系数
举个例子：
某算法T(n)=2n^3+4n-5，按步骤走：
- T(n)=2n^3+4n
- T(n)=2n^3
- T(n)=n^3
即可得该算法时间复杂度为O(n^3)
四、常见时间复杂度
这里按复杂度从低到高列举常见的时间复杂度：
-
常数阶O(1)
// 无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1) 。 public void fun(int n){ n+=1; } -
对数阶O(log2n)
// 根据公式有 n = 2^x，也就是 x = log2n，x即为循环代码执行次数，所以时间复杂度为O(log2n) public void fun(int n){ int i = 1; while(i < n){ i = i *2 } } -
线性阶O(n)
// 一般来说，只要代码里只有一个循环结构，即输入规模和执行次数呈线性相关，那这个代码的时间复杂度就都是O(n) 。 public void fun(int n){ for(int i = 0; i < n; i++){ n+=i; } } -
线性对数阶O(nlogn)
// 可以简单理解为对数阶的程序被放入了循环结构中，也就是n*O(logn)，下面的代码的复杂度就是O(nlog2n) public void fun(int n){ int j = 1; for(int i = 0; i < n; i++){ while(i < n){ j = j *2 } } } -
平方阶O(n²)，立方阶O(n3)，K次方阶O(nk)
// 平方阶可以简单理解为线性阶中嵌套一个线性阶，也就是O(logn)*O(logn)，下面的代码复杂度就是O(n^2) // 立方阶同理，就是三个线性阶的嵌套，K次方阶同理 public void fun(int n){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; i++){ i=i+j; } } }
五、复杂度的四个概念
- 最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。
- 最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
- 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示
- 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
举个例子：
长度为n的数组查找一个给定元素k
public void fun(int[] arr,int k){
for(int i = 0; i < arr.length; i++){
if(arr[i] == k){
//找到了
}
}
}
上面这个方法，最好的情况下元素k就在数组第一位，复杂度为O(1)，但是最坏的情况下，元素k在数组最后一位，复杂度为O(n)。
同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，我们引入这4个概念，当然，在大多数时候我们是不用特意区分这四种情况的。
六、总结
总结一下如何快速判断程序的时间复杂度：
- 只关注循环最多的那部分代码
- 总复杂度等于量级最大的那段代码的复杂度
- 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/170812.html原文链接：https://javaforall.net
