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

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

什么是时间复杂度?

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

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

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

大 O 符号

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

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

$$T(n) = 4n^2 - 2n + 2$$

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

常见复杂度比较

常见时间复杂度比较

常数时间

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

常见的例子有:

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

别被循环所迷惑

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

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

题解如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
row = [{} for _ in range(9)]
col = [{} for _ in range(9)]
area = [{} for _ in range(9)]

area_index_dict = {
0: {0: 0, 1: 1, 2: 2},
1: {0: 3, 1: 4, 2: 5},
2: {0: 6, 1: 7, 2: 8}
}

for i in range(9):
for j in range(9):
num = board[i][j]

if num == '.':
continue

# 行判断
if num in row[i]:
print 'row=', num
return False
else:
row[i][num] = 1

# 列判断
if num in col[j]:
print 'col=', num
return False
else:
col[j][num] = 1

# 小正方形的区域判断
area_index = area_index_dict[i//3][j//3]
if num in area[area_index]:
print 'area_index=', area_index
print 'area=', num
return False
else:
area[area_index][num] = 1

return True

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

1
2
3
for i in range(9):
for j in range(9):
# coding

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

对数时间

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

常见例子:

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

为什么是 logn?

什么是对数?

首先,我们复习一下 对数

对数 是幂运算的逆运算。假如 $x = β^y$,那么就有 $y = log_βx$。其中:

  • $β$ 是对数的底(基底)
  • $y$ 就是 $x$(对于底数 $β$)的对数

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

换底公式

来看一下 换底公式

$$log_ab = \frac{log_cb}{log_ca}$$

假设两个算法复杂度分别为 $O(log_an)$ 和 $O(log_bn)$,基于 换底公式 可以得到:

$$log_an = \frac{log_cn}{log_ca}$$

$$log_bn = \frac{log_cn}{log_cb}$$

对于 $O(log_an)$ 和 $O(log_bn)$ 来说,只有一个常数因子的不同。在大 O 记法中我们丢弃该因子(忽略常数),因此无论对数的底是多少,我们将对数时间都记作 $O(logn)$。

二分查找

对数时间最典型的算法应该就是二分查找了。例如这道题 搜索插入位置

二分查找的基本思想:将查找的键和子数组的中间键作比较:

  • 如果被查找的键小于中间键,就在左子数组继续查找
  • 如果大于中间键,就在右子数组中查找
  • 否则中间键就是要找的元素

因此,对于 n 个元素的情况:

  • 第 1 次二分剩下元素 $\frac{n}{2}$
  • 第 2 次二分剩下元素 $\frac{n}{4}$
  • ……
  • 第 m 次二分剩下元素:$\frac{n}{2^m}$

在最坏情况下,是在排除到只剩下最后一个值之后得到结果,即:

$$\frac{n}{2^m} = 1$$

由此可得:

$$2^m = n$$

进而求出复杂度为 $log_2(n)$。又因为我们在大 O 记法中忽略底数 2,因此复杂度就是 $O(logn)$ 啦~

线性时间

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
major = 0
count = 0

for n in nums:
if count == 0:
major = n

if n == major:
count = count + 1
else:
count = count - 1

return major

线性对数(准线性)时间

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

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

二次时间

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

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


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

参考资料及扩展阅读


现在类似哈希表的题目做多了,再想起高一时燕林段长讲的关于「早操散场分开走,空间换时间」的梗觉得相当有趣。当时还只在乎年级排名的我没有想过将来会步入互联网行业,会喜欢上这个光怪陆离的世界。

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