时间复杂度详解(5大时间复杂度计算公式)

时间复杂度定义

时间复杂度是一个函数，它定性描述该算法的运行时间，时间复杂度常用大O符号表述。

大O时间复杂度并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势。

所以，也叫作渐进时间复杂度，简称时间复杂度。

 

常见的时间复杂度？

常见的时间复杂度，如下所示：

1. 常数阶O(1)；
2. 线性阶O(n)；
3. 平方阶O(n²)；
4. 对数阶O(logn)；
5. 线性对数阶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年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注「mikechen」公众号，获取更多技术干货！

后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》