本文首发公众号：架构精进，请移步，排版比较清晰。

经常有同学在 LeetCode 的题解中问解法的复杂度是多少。作为一个懒人，我一直在「逃避」这个问题，毕竟这东西听起来就这么「复杂」。

但本着对题解认真负责的态度（心虚），我想趁此机会做一个总结。下面我将通过一些较为经典的算法题聊一聊几种常见的时间复杂度。

什么是时间复杂度？

算法的时间复杂度（Time complexity）是一个函数，用于定性描述算法的运行时间。

提出时间复杂度的目的是：分析与比较完成同一个任务而设计的不同算法。

分析算法的结果意味着算法需要的资源，虽然有时我们关心像内存，通信带宽或者计算机硬件这类资源，但是通常我们想要度量的是计算时间。一般来说，通过分析求解某个问题的几种候选算法，我们可以选出一种最有效的算法。这种分析可能指出不止一个可行的候选算法，但是在这个过程中，我们往往可以抛弃几个较差的算法。 ——《算法导论》

大 O 符号

时间复杂度通常用 大 O 符号（Big O notation）表示。大 O 符号 又被称为渐近符号，是用于描述函数 渐近行为。

举个例子，假设我们解决一个规模为 n 的问题要花费的时间为 T(n)T(n)：

T(n)=4n2−2n+2T(n)=4n2−2n+2

当 n 不断增大时，n2n2 开始占据主导地位，而其他各项可以被忽略，写作 T(n)=O(n2)T(n)=O(n2)。因此时间复杂度可被称为是 渐近 的。

常见复杂度比较

 

 

 

常见时间复杂度比较

常数时间

若算法 T(n)T(n) 的上界与输入大小无关，则称它具有常数时间，记作 T(n)=O(1)T(n)=O(1)。

常见的例子有：

• 访问数组中的单个元素
• 哈希表

别被循环所迷惑

例如这道题 有效的数独，需要在 9x9 的格子中判断数独是否有效。

思路：把行、列和小正方形区域出现的数字用哈希表记录下来，在遍历过程中只要判断数字是否在这三个范围出现过就行了，如果出现过就返回 False。

题解如下：

 

 

 

我们可以看到，虽然题解中用到了如下循环：

 

但由于复杂度始终是 O(9×9)O(9×9)，加上使用哈希表来判断元素是否存在，所以算法的复杂度始为 O(1)O(1)。

对数时间

若 T(n)=O(logn)T(n)=O(logn)，则称其具有对数时间。

常见例子：

• 二叉树相关操作
• 二分查找

为什么是 logn？

什么是对数？

首先，我们复习一下 对数。

对数 是幂运算的逆运算。假如 x=βyx=βy，那么就有 y=logβxy=logβx。其中：

• ββ 是对数的底（基底）
• yy 就是 xx（对于底数 ββ）的对数

那我们说一个算法的复杂度是 O(logn)O(logn)，那么 lognlogn 这个对数的底数去哪了？

换底公式

二分查找

 

线性时间

如果一个算法的时间复杂度为 O(n)O(n)，则称这个算法具有线性时间。随着样本数量的增加，复杂度也随之线性增加。常表现为单层循环。

来看一到例题 求众数。这里我们用了摩尔投票法，时间复杂度为 O(n)O(n)。

 

 

 

线性对数（准线性）时间

若算法复杂度为 T(n)=O(nlogn)T(n)=O(nlogn)，则称这个算法具有线性对数时间。可以理解为执行了 n 次对数时间复杂度的操作。

有几种排序算法的平均时间复杂度都是线性对数时间，例如：

• 堆排序：前 K 个高频元素
• 快速排序：颜色分类
• 归并排序

二次时间

若算法复杂度为 T(n)=O(n2)T(n)=O(n2)，则称这个算法具有二次时间，即时间复杂度随着样本数量的增加呈平方数增长。常表现为双层循环。

常见的算法中有一写比较慢的排序算法，例如：

• 冒泡排序
• 选择排序
• 插入排序

由于涉及的排序算法很多，若一一讲解的话就偏离这篇文章的侧重点了。如果大家对各类算法感兴趣可以参考：维基百科：排序算法。

算法是生活中的大智慧，而我们都是智慧的受益者。