在算法竞赛中，程序必须在规定时间内运行完毕才能得分。USACO 对 C++ 提交的时限为 $2$ 秒，对 Java/Python 提交的时限为 $4$ 秒。保守估计，评测服务器每秒可以处理 $10^8$ 次操作； 如果常数因子较小，则可能接近 $5 \cdot 10^8$ 次。*

复杂度计算

我们希望根据输入规模 $n$ 计算每种算法运行所需的操作次数。幸运的是，利用 大 O 记号可以比较容易地做到这一点。 当 $n$ 任意增大时，大 O 记号把最坏情况下的时间复杂度表示为 $n$ 的函数。复杂度 给出了算法所需步骤数关于输入规模的上界。大 O 记号把函数的复杂度写作 $\mathcal{O}(f(n))$，通常会省略 $f(n)$ 中的常数因子和低阶项。下面来看一些示例。

下面的代码执行固定次数的操作，因此复杂度为 $\mathcal{O}(1)$。

Copy
a = 5
b = 7
c = 4
d = a + b + c + 153

输入和输出操作也假定为 $\mathcal{O}(1)$。在下面的示例中，我们假定循环体内代码 的复杂度为 $\mathcal{O}(1)$。

循环的时间复杂度取决于循环执行的迭代次数。例如，下面两段代码的复杂度都是 $\mathcal{O}(n)$。

Copy
for i in range(1, n + 1):
	pass  # constant time code here

Copy
i = 0
while i < n:
	# constant time code here
	i += 1

由于我们忽略常数因子和低阶项，下面的示例同样都是 $\mathcal{O}(n)$：

Copy
for i in range(5 * n + 17):
	pass  # constant time code here

for i in range(n + 457737):
	pass  # constant time code here

对于嵌套的多层循环，可以将每层循环的时间复杂度相乘。下面示例的复杂度为 $\mathcal{O}(nm)$，因为外层循环执行 $\mathcal{O}(n)$ 次，内层循环执行 $\mathcal{O}(m)$ 次。

Copy
for i in range(n):
	for j in range(m):
		pass  # constant time code here

在这个示例中，外层循环执行 $\mathcal{O}(n)$ 次，内层循环执行 $1$ 至 $n$ 次 （最多为 $n$ 次）。由于大 O 记号计算最坏情况下的时间复杂度，我们把内层循环 视作因子 $n$。*因此，这段代码 的复杂度为 $\mathcal{O}(n^2)$。

Copy
for i in range(n):
	for j in range(i, n):
		pass  # constant time code here

如果一个算法包含多个代码块，其时间复杂度取其中最大的复杂度。例如，下面代码的 复杂度为 $\mathcal{O}(n^2)$。

Copy
for i in range(n):
	for j in range(n):
		pass  # constant time code here

for i in range(n + 58834):
	pass  # more constant time code here

下面代码的复杂度为 $\mathcal{O}(n^2+m)$，因为它由复杂度分别为 $\mathcal{O}(n^2)$ 和 $\mathcal{O}(m)$ 的两个代码块组成，且二者相对于对方都不是 低阶函数。

Copy
for i in range(n):
	for j in range(n):
		pass  # constant time code here

for i in range(m):
	pass  # more constant time code here

常见复杂度与限制

一些常见算法和数据结构所产生的复杂度因子如下：

• 直接计算答案的数学公式：$\mathcal{O}(1)$
• 二分查找：$\mathcal{O}(\log n)$
• 有序集合/映射或优先队列：每次操作 $\mathcal{O}(\log n)$
• 对整数进行质因数分解，或朴素判断一个整数是质数还是合数： $\mathcal{O}(\sqrt{n})$
• 读入 $n$ 项数据：$\mathcal{O}(n)$
• 遍历含 $n$ 个元素的数组或列表：$\mathcal{O}(n)$
• 排序：默认排序算法（归并排序、Collections.sort、Arrays.sort）通常为 $\mathcal{O}(n\log n)$
• Java 对基本类型使用快速排序的 Arrays.sort：$\mathcal{O}(n^2)$

  • 详情请参阅数据结构简介。
• 遍历输入元素中所有大小为 $k$ 的子集：$\mathcal{O}(n^k)$。例如，遍历所有三元组 为 $\mathcal{O}(n^3)$。
• 遍历所有子集：$\mathcal{O}(2^n)$
• 遍历所有排列：$\mathcal{O}(n!)$

下面给出了各种时间复杂度所能处理的 $n$ 的保守上界。实际可处理的规模可能更大， 但这张表足以帮助你快速判断一种算法是否可行。

常数因子

常数因子是指：复杂度相同的不同操作，实际运行时间会略有不同。例如，三次加法 会比一次加法稍慢。又如，虽然在数组上进行二分查找和向有序集合插入元素的复杂度 都是 $\mathcal{O}(\log n)$，但二分查找明显更快。

大 O 记号完全忽略常数因子。大多数情况下这样没有问题，但如果时限特别紧， 即使复杂度符合预期也可能超时（TLE）。此时就必须考虑常数因子。例如，遍历所有 _有序_三元组的代码以 $\mathcal{O}(n^3)$ 运行；如果只需遍历所有_无序_三元组， 速度可能提高 $6$ 倍。

目前不必担心如何优化常数因子，只需知道它们的存在。

大 O 记号的形式化定义

设 $f$ 和 $g$ 是从 $\mathbb{R}_{\ge 0}$ 到 $\mathbb{R}_{\ge 0}$ 的非负函数。如果 存在正常数 $n_0$ 和 $c$，使得每当 $n\ge n_0$ 时都有 $f(n)\le c\cdot g(n)$，就称 $f(n)=\mathcal{O}(g(n))$。

因此，我们可以说复杂度为 $\mathcal{O}(n)$ 的线性函数同时也是 $\mathcal{O}(n/2)$、$\mathcal{O}(2n)$、$\mathcal{O}(n^2)$、$\mathcal{O}(2^n)$、 $\mathcal{O}(n^n)$ 等。不过，我们通常会在限制最紧的函数中写出最简单的一个； 对于上面的线性函数，就是 $\mathcal{O}(n)$。

小测验