理解算法中的时间复杂度，O(1)，O(n)，O(log2n)，O(n^2)

朱雀 2023-07-16 09:58 136阅读 0赞

算法复杂度分为**时间复杂度**和**空间复杂度**，二者也是衡量代码的好坏两个重要指标：

*  时间复杂度：指执行算法所需要的计算工作量；
 *  间复杂度：指执行这个算法所需要的内存空间。

算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。

### **1. 概念理解** ###

**1.1 基本执行次数：T(n)**

由于运行环境和输入规模的影响，代码的绝对执行时间是无法估计的，但我们可以估算出代码的基本执行次数。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用这个函数来表达相对时间，可以记作 T(n)。

**1.2 时间复杂度：O(n)**

因为执行规则具有不确定性（文章下面就列举4种可能）， 所以T(n) 不足以分析和比较一段代码的运行时间，就有了**渐进时间复杂度**（asymptotic time complexity）的概念，官方的定义如下：

> 若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称：时间复杂度。
> 
> 渐进时间复杂度用大写“O”来表示，所以也被称为大O表示法。

算法时间复杂度里有O(1), O(n), O(logn), O(nlogn), O(n^2)的概念，这是算法的时空复杂度的表示。

它不仅仅用于表示时间复杂度，也用于表示空间复杂度。

O后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。

**1.3 空间复杂度：S(n)**

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量，记作：S(n)=O(f(n)) 。

上面提到过，O(n)不仅仅用于表示时间复杂度，也用于表示空间复杂度。

### 2. 场景分析： ###

这是针对时间复杂度的场景分析，时间复杂度排序为：O（1）< O（log2n）< O（n）< O（n^2）

**场景1：**T（n） =  O（1）

表示算法的运行时间为常量，这是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。

哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI1OTcyMA_size_16_color_FFFFFF_t_70][]

**场景2：**T（n） =  O（log2n）

当数据增大n倍时，耗时增大log n倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。

二分查找就是O(log n)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI1OTcyMA_size_16_color_FFFFFF_t_70 1][]

**场景3：**T（n） =  O（n）

表示该算法是线性算法，数据量增大几倍，耗时也增大几倍。

比如常见的for循环遍历，要找到一个数组里面最大的一个数，你要把n个变量都扫描一遍，操作次数为n，那么算法复杂度是O(n)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI1OTcyMA_size_16_color_FFFFFF_t_70 2][]

**场景4：**T（n） =  O（n^2）

代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。

比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI1OTcyMA_size_16_color_FFFFFF_t_70 3][]

在编程的世界中有着各种各样的算法，除了上述的四个场景，还有许多不同形式的时间复杂度，我们按照时间复杂度，按数量级递增依次排列为：

常数阶 O（1） <  对数阶（log2n） < 线性阶 O（n）<  线性对数阶 O（nlog2n） < 平方阶 O（n^2） < 立方阶 O（n^3） < k次方阶 O（n^k） < 指数阶 O（2^n）……

### 3. 算法比较： ###

<table> 
 <thead> 
 <tr> 
 <th style="text-align:center;vertical-align:middle;"> 排序算法 </th> 
 <th style="text-align:center;vertical-align:middle;"> &nbsp;&nbsp;平均时间 </th> 
 <th style="text-align:center;vertical-align:middle;"> 最差情形 </th> 
 <th style="text-align:center;vertical-align:middle;"> 稳定度 </th> 
 <th style="text-align:center;vertical-align:middle;"> 额外空间 </th> 
 <th style="text-align:center;vertical-align:middle;"> 备注 </th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> 冒泡 </td> 
 <td> &nbsp;O(n&nbsp;2&nbsp;) </td> 
 <td> &nbsp;O(n&nbsp;2&nbsp;) </td> 
 <td> 稳定 </td> 
 <td> O(1) </td> 
 <td> n&nbsp;小时较好 </td> 
 </tr> 
 <tr> 
 <td> 交换 </td> 
 <td> &nbsp;&nbsp;O(n&nbsp;2&nbsp;) </td> 
 <td> &nbsp;&nbsp;O(n&nbsp;2&nbsp;) </td> 
 <td> 不稳定 </td> 
 <td> O(1) </td> 
 <td> n&nbsp;小时较好 </td> 
 </tr> 
 <tr> 
 <td> 选择 </td> 
 <td> &nbsp;O(n&nbsp;2&nbsp;) </td> 
 <td> &nbsp;O(n&nbsp;2&nbsp;) </td> 
 <td> 不稳定 </td> 
 <td> O(1) </td> 
 <td> n&nbsp;小时较好 </td> 
 </tr> 
 <tr> 
 <td> 插入 </td> 
 <td> &nbsp;O(n&nbsp;2&nbsp;) </td> 
 <td> &nbsp;O(n&nbsp;2&nbsp;) </td> 
 <td> 稳定 </td> 
 <td> O(1) </td> 
 <td> 大部分已排序时较好 </td> 
 </tr> 
 <tr> 
 <td> 基数 </td> 
 <td> O(log&nbsp;R&nbsp;B) </td> 
 <td> O(log&nbsp;R&nbsp;B) </td> 
 <td> 稳定 </td> 
 <td> O(n) </td> 
 <td> B&nbsp;是真数&nbsp;(0-9)&nbsp;， R&nbsp;是基数&nbsp;(&nbsp;个十百&nbsp;) </td> 
 </tr> 
 <tr> 
 <td> Shell </td> 
 <td> O(nlogn) </td> 
 <td> O(n&nbsp;s&nbsp;) 1&lt;s&lt;2 </td> 
 <td> 不稳定 </td> 
 <td> O(1) </td> 
 <td> s&nbsp;是所选分组 </td> 
 </tr> 
 <tr> 
 <td> 快速 </td> 
 <td> O(nlogn) </td> 
 <td> O(n&nbsp;2&nbsp;) </td> 
 <td> 不稳定 </td> 
 <td> O(nlogn) </td> 
 <td> n&nbsp;大时较好 </td> 
 </tr> 
 <tr> 
 <td> 归并 </td> 
 <td> O(nlogn) </td> 
 <td> O(nlogn) </td> 
 <td> 稳定 </td> 
 <td> O(1) </td> 
 <td> n&nbsp;大时较好 </td> 
 </tr> 
 <tr> 
 <td> 堆 </td> 
 <td> O(nlogn) </td> 
 <td> O(nlogn) </td> 
 <td> 不稳定 </td> 
 <td> O(1) </td> 
 <td> n&nbsp;大时较好 </td> 
 </tr> 
 </tbody> 
</table>

借鉴了一些官方统计，再加上自己的理解，整理了一篇比较全面的关于介绍时间复杂度的博客，内容涵盖了从概念延伸到原理，再到算法的总结，希望对大家有一定的帮助。

**少侠请留步 ... ヾ(◍°∇°◍)ﾉﾞ ... **  
**欢迎点赞、评论、加关注，让更多人看到学到赚到**  
**更多精彩，请关注我的"今日头条号"：Java云笔记**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI1OTcyMA_size_16_color_FFFFFF_t_70]: /images/20230528/a86180d9f71244389341f2b17e5757d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI1OTcyMA_size_16_color_FFFFFF_t_70 1]: /images/20230528/9b780093bc9343aa875dfff5b65e4f8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI1OTcyMA_size_16_color_FFFFFF_t_70 2]: /images/20230528/fce4668ed742481391e6e7471410d837.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI1OTcyMA_size_16_color_FFFFFF_t_70 3]: /images/20230528/4e405c8b5af142c08c414795060a54f4.png