时间复杂度定义
时间复杂度是一个函数，它定性描述该算法的运行时间，时间复杂度常用大O符号表述。
大O时间复杂度并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势。
所以，也叫作渐进时间复杂度，简称时间复杂度。
常见的时间复杂度？
常见的时间复杂度，如下所示：
- 常数阶O(1)；
- 线性阶O(n)；
- 平方阶O(n²)；
- 对数阶O(logn)；
- 线性对数阶O(nlogn)。
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
一般来讲，复杂度越小，则说明你的代码越好。
但是，我们在决定使用那些算法的时候 ，也不是时间复杂越低的越好，要考虑数据规模，如果数据规模很小 甚至可以用O(n^2)的算法比 O(n)的更合适。
复杂度的大小：
- 你可以看到，随着输入规模的增长，红色阴影区域中算法的运行时间急剧增长；
- 另一方面，在黄色和绿色阴影区域中的算法，当输入规模增长时，运行时间在变化不是很大，因此它们更高效，处理大量数据时更游刃有余。
上面我们了解了什么是时间复杂度，以及计算公式，下面一起来看几个时间复杂度的经典例子，就更清楚了，let’s go!
O(1)常数阶
这个最容易理解，只执行一次。
比如：
int sum = 0; /* 执行一次 */
只要程序中没有循环等复杂结构，那么这个程序的时间复杂度就为常量阶O(1)。
O(n)线性阶
因为要执行n次，时间复杂度为O(n)。
具体示例如下：
for (int i = 1; i <= n; i++) {
System.out.println(1);
}
for循环里面的代码会执行n遍，因此这类代码都可以用O(n)来表示它的时间复杂度。
O(n²)平方阶
平方阶O(n²) 很容易理解，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)。
具体示例如下：
int i,j;
for（i = 0; i < n; i++）
{
for（j = 0; j < n; j++）
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}
这段代码其实就是嵌套了2层n循环。
O(logn)对数阶
典型的对数阶复O(logn)杂度算法就是：二分搜索算法。
还是看一个例子，一看就懂，如下所示：
int i = 1;
while (i <= n){
i = i * 2;
}
在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。
也就是说有多少2相乘后会大于n，然后退出循环，2^x=n 得到x=log2n，时间复杂度为O(logn)。
O(nlogn)线性对数阶
线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。
具体如下所示：
for (int i = 1; i <= n; i++) {
int j = 1;
while (j<=n){
j = j * 2;
}
}
作者简介
陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
👇阅读更多mikechen架构文章👇
阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师
以上
关注作者「mikechen」公众号，获取更多技术干货！
后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》