2.3 时间复杂度¶
运行时间可以直观且准确地反映算法的效率。如果我们想准确预估一段代码的运行时间,应该如何操作呢?
- 确定运行平台,包括硬件配置、编程语言、系统环境等,这些因素都会影响代码的运行效率。
- 评估各种计算操作所需的运行时间,例如加法操作
+需要 1 ns ,乘法操作*需要 10 ns ,打印操作print()需要 5 ns 等。 - 统计代码中所有的计算操作,并将所有操作的执行时间求和,从而得到运行时间。
例如在以下代码中,输入数据大小为 \(n\) :
根据以上方法,可以得到算法的运行时间为 \((6n + 12)\) ns :
但实际上,统计算法的运行时间既不合理也不现实。首先,我们不希望将预估时间和运行平台绑定,因为算法需要在各种不同的平台上运行。其次,我们很难获知每种操作的运行时间,这给预估过程带来了极大的难度。
2.3.1 统计时间增长趋势¶
时间复杂度分析统计的不是算法运行时间,而是算法运行时间随着数据量变大时的增长趋势。
“时间增长趋势”这个概念比较抽象,我们通过一个例子来加以理解。假设输入数据大小为 \(n\) ,给定三个算法 A、B 和 C :
// 算法 A 的时间复杂度:常数阶
function algorithm_A(n: number): void {
console.log(0);
}
// 算法 B 的时间复杂度:线性阶
function algorithm_B(n: number): void {
for (let i = 0; i < n; i++) {
console.log(0);
}
}
// 算法 C 的时间复杂度:常数阶
function algorithm_C(n: number): void {
for (let i = 0; i < 1000000; i++) {
console.log(0);
}
}
图 2-7 展示了以上三个算法函数的时间复杂度。
- 算法
A只有 \(1\) 个打印操作,算法运行时间不随着 \(n\) 增大而增长。我们称此算法的时间复杂度为“常数阶”。 - 算法
B中的打印操作需要循环 \(n\) 次,算法运行时间随着 \(n\) 增大呈线性增长。此算法的时间复杂度被称为“线性阶”。 - 算法
C中的打印操作需要循环 \(1000000\) 次,虽然运行时间很长,但它与输入数据大小 \(n\) 无关。因此C的时间复杂度和A相同,仍为“常数阶”。
图 2-7 算法 A、B 和 C 的时间增长趋势
图解 2-7:算法 A、B 和 C:时间长短与增长趋势
图对比算法 A、B、C 的运行时间走势,区分实际耗时与增长趋势。
横轴为输入数据大小 n,刻度 0 至 9;纵轴为算法运行时间,可见刻度为 0、5、10、省略号和 1000000。纵轴压缩了 10 与 1000000 之间的跨度,线条垂直距离不是统一比例尺。
三种算法执行同一种打印操作。下表的打印次数取自正文代码,线条颜色和位置来自图中。
| 算法 | 打印次数 | 图中运行时间走势 |
|---|---|---|
| A | 1 | 绿色水平线,位于纵轴 0 与 5 之间 |
| B | n | 蓝色斜线,从原点出发,n = 1 时与 A 相交,n = 9 时接近纵轴刻度 10 |
| C | 1000000 | 橙色水平线,位于纵轴刻度 1000000 |
A 与 C 的次数都不随 n 改变,因此同属 O(1),尽管耗时相差很大;B 随 n 线性增长,为 O(n)。按打印次数外推,B 与 C 的交点在 n = 1000000 处,超出图示横轴范围。
相较于直接统计算法的运行时间,时间复杂度分析有哪些特点呢?
- 时间复杂度能够有效评估算法效率。例如,算法
B的运行时间呈线性增长,在 \(n > 1\) 时比算法A更慢,在 \(n > 1000000\) 时比算法C更慢。事实上,只要输入数据大小 \(n\) 足够大,复杂度为“常数阶”的算法一定优于“线性阶”的算法,这正是时间增长趋势的含义。 - 时间复杂度的推算方法更简便。显然,运行平台和计算操作类型都与算法运行时间的增长趋势无关。因此在时间复杂度分析中,我们可以简单地将所有计算操作的执行时间视为相同的“单位时间”,从而将“计算操作运行时间统计”简化为“计算操作数量统计”,这样一来估算难度就大大降低了。
- 时间复杂度也存在一定的局限性。例如,尽管算法
A和C的时间复杂度相同,但实际运行时间差别很大。同样,尽管算法B的时间复杂度比C高,但在输入数据大小 \(n\) 较小时,算法B明显优于算法C。对于此类情况,我们时常难以仅凭时间复杂度判断算法效率的高低。当然,尽管存在上述问题,复杂度分析仍然是评判算法效率最有效且常用的方法。
2.3.2 函数渐近上界¶
给定一个输入大小为 \(n\) 的函数:
设算法的操作数量是一个关于输入数据大小 \(n\) 的函数,记为 \(T(n)\) ,则以上函数的操作数量为:
\(T(n)\) 是一次函数,说明其运行时间的增长趋势是线性的,因此它的时间复杂度是线性阶。
我们将线性阶的时间复杂度记为 \(O(n)\) ,这个数学符号称为大 \(O\) 记号(big-\(O\) notation),表示函数 \(T(n)\) 的渐近上界(asymptotic upper bound)。
时间复杂度分析本质上是计算“操作数量 \(T(n)\)”的渐近上界,它具有明确的数学定义。
函数渐近上界
若存在正实数 \(c\) 和实数 \(n_0\) ,使得对于所有的 \(n > n_0\) ,均有 \(T(n) \leq c \cdot f(n)\) ,则可认为 \(f(n)\) 给出了 \(T(n)\) 的一个渐近上界,记为 \(T(n) = O(f(n))\) 。
如图 2-8 所示,计算渐近上界就是寻找一个函数 \(f(n)\) ,使得当 \(n\) 趋向于无穷大时,\(T(n)\) 和 \(f(n)\) 处于相同的增长级别,仅相差一个常数系数 \(c\)。
图 2-8 函数的渐近上界
图解 2-8:渐近上界:越过阈值后的大小关系
图用两条曲线说明:渐近上界关心越过阈值之后的大小关系。
横轴为输入数据大小 n,刻度 0 至 14;纵轴为函数值,没有可见数值刻度。蓝线是操作数量 T(n),橙线是候选函数 f(n) 乘以正常数 c 后的 c·f(n);图未给出具体函数公式。
绿色竖直虚线 n₀ 位于刻度 7 与 8 之间的两线交点。蓝线在刻度 1 至 7 之间有起伏,并高于橙线;越过 n₀ 后,橙线一直在蓝线上方,两线继续向上增长。
底部给出的条件是:存在正常数 c 和阈值 n₀,使所有 n > n₀ 都满足 T(n) ≤ c·f(n),于是记作 T(n) = O(f(n)),称 f(n) 为一个渐近上界。阈值之前 T(n) 曾超过 c·f(n) 不影响这一结论,也不要求两条曲线处处相等。
2.3.3 推算方法¶
渐近上界的数学味儿有点重,如果你感觉没有完全理解,也无须担心。我们可以先掌握推算方法,在不断的实践中,就可以逐渐领悟其数学意义。
根据定义,确定 \(f(n)\) 之后,我们便可得到时间复杂度 \(O(f(n))\) 。那么如何确定渐近上界 \(f(n)\) 呢?总体分为两步:首先统计操作数量,然后判断渐近上界。
1. 第一步:统计操作数量¶
针对代码,逐行从上到下计算即可。然而,由于上述 \(c \cdot f(n)\) 中的常数系数 \(c\) 可以取任意大小,因此操作数量 \(T(n)\) 中的各种系数、常数项都可以忽略。根据此原则,可以总结出以下计数简化技巧。
- 忽略 \(T(n)\) 中的常数。因为它们都与 \(n\) 无关,所以对时间复杂度不产生影响。
- 省略所有系数。例如,循环 \(2n\) 次、\(5n + 1\) 次等,都可以简化记为 \(n\) 次,因为 \(n\) 前面的系数对时间复杂度没有影响。
- 循环嵌套时使用乘法。总操作数量等于外层循环和内层循环操作数量之积,每一层循环依然可以分别套用第
1.点和第2.点的技巧。
给定一个函数,我们可以用上述技巧来统计操作数量:
以下公式展示了使用上述技巧前后的统计结果,两者推算出的时间复杂度都为 \(O(n^2)\) 。
2. 第二步:判断渐近上界¶
时间复杂度由 \(T(n)\) 中最高阶的项来决定。这是因为在 \(n\) 趋于无穷大时,最高阶的项将发挥主导作用,其他项的影响都可以忽略。
表 2-2 展示了一些例子,其中一些夸张的值是为了强调“系数无法撼动阶数”这一结论。当 \(n\) 趋于无穷大时,这些常数变得无足轻重。
表 2-2 不同操作数量对应的时间复杂度
| 操作数量 \(T(n)\) | 时间复杂度 \(O(f(n))\) |
|---|---|
| \(100000\) | \(O(1)\) |
| \(3n + 2\) | \(O(n)\) |
| \(2n^2 + 3n + 2\) | \(O(n^2)\) |
| \(n^3 + 10000n^2\) | \(O(n^3)\) |
| \(2^n + 10000n^{10000}\) | \(O(2^n)\) |
2.3.4 常见类型¶
设输入数据大小为 \(n\) ,常见的时间复杂度类型如图 2-9 所示(按照从低到高的顺序排列)。
图 2-9 常见的时间复杂度类型
图解 2-9:五种常见时间复杂度的增长趋势
比较五种时间复杂度随输入规模增大的增长趋势。
横轴是输入数据大小 n,刻度 1 至 14;纵轴是计算操作数量 T(n),没有可见数值刻度。曲线展示增长趋势,不是某段程序的实测次数或未缩放函数值。
下表按图右端从低到高排列,对应右侧向上箭头“从低至高、从优至差”。
| 复杂度(右端从低到高) | 图中形态 |
|---|---|
| 常数阶 O(1) | 绿色水平线,操作数不随 n 变化 |
| 对数阶 O(log n) | 青色曲线缓慢上升,斜率逐渐变小 |
| 线性阶 O(n) | 蓝色直线以固定斜率上升 |
| 平方阶 O(n²) | 橙色曲线向上弯曲,斜率越来越陡 |
| 指数阶 O(2ⁿ) | 红色曲线前段贴近底部,后段陡峭上升 |
前段有曲线相交,例如红色指数曲线起初低于蓝色线性线和橙色平方曲线,随后超过它们。这些交点只是示意,不能据此推算某个输入下的精确次数或效率切换阈值。图表达的是 n 足够大时,阶数越低,操作数量增长越慢。
1. 常数阶 \(O(1)\)¶
常数阶的操作数量与输入数据大小 \(n\) 无关,即不随着 \(n\) 的变化而变化。
在以下函数中,尽管操作数量 size 可能很大,但由于其与输入数据大小 \(n\) 无关,因此时间复杂度仍为 \(O(1)\) :
可视化运行
2. 线性阶 \(O(n)\)¶
线性阶的操作数量相对于输入数据大小 \(n\) 以线性级别增长。线性阶通常出现在单层循环中:
可视化运行
遍历数组和遍历链表等操作的时间复杂度均为 \(O(n)\) ,其中 \(n\) 为数组或链表的长度:
可视化运行
值得注意的是,输入数据大小 \(n\) 需根据输入数据的类型来具体确定。比如在第一个示例中,变量 \(n\) 为输入数据大小;在第二个示例中,数组长度 \(n\) 为数据大小。
3. 平方阶 \(O(n^2)\)¶
平方阶的操作数量相对于输入数据大小 \(n\) 以平方级别增长。平方阶通常出现在嵌套循环中,外层循环和内层循环的时间复杂度都为 \(O(n)\) ,因此总体的时间复杂度为 \(O(n^2)\) :
可视化运行
图 2-10 对比了常数阶、线性阶和平方阶三种时间复杂度。
图 2-10 常数阶、线性阶和平方阶的时间复杂度
图解 2-10:循环结构与操作次数
比较单次操作、单层循环和双层循环的工作量增长。
每个小方块代表 1 次基础操作,外围循环框表示重复执行的范围。
| 结构 | 基础操作次数 | 时间复杂度 |
|---|---|---|
| 无循环 | 1 | 常数阶 O(1) |
| 单层循环n次 | n | 线性阶 O(n) |
| 双层嵌套,各n次 | n×n=n² | 平方阶 O(n²) |
双层框表示嵌套:外层每执行 1 轮,内层都固定完整运行 n 次,所以次数相乘为 n × n,而不是两个循环先后执行时的相加。
以冒泡排序为例,外层循环执行 \(n - 1\) 次,内层循环执行 \(n-1\)、\(n-2\)、\(\dots\)、\(2\)、\(1\) 次,平均为 \(n / 2\) 次,因此时间复杂度为 \(O((n - 1) n / 2) = O(n^2)\) :
def bubble_sort(nums: list[int]) -> int:
"""平方阶(冒泡排序)"""
count = 0 # 计数器
# 外循环:未排序区间为 [0, i]
for i in range(len(nums) - 1, 0, -1):
# 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for j in range(i):
if nums[j] > nums[j + 1]:
# 交换 nums[j] 与 nums[j + 1]
tmp: int = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = tmp
count += 3 # 元素交换包含 3 个单元操作
return count
/* 平方阶(冒泡排序) */
int bubbleSort(vector<int> &nums) {
int count = 0; // 计数器
// 外循环:未排序区间为 [0, i]
for (int i = nums.size() - 1; i > 0; i--) {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
count += 3; // 元素交换包含 3 个单元操作
}
}
}
return count;
}
/* 平方阶(冒泡排序) */
int bubbleSort(int[] nums) {
int count = 0; // 计数器
// 外循环:未排序区间为 [0, i]
for (int i = nums.length - 1; i > 0; i--) {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
count += 3; // 元素交换包含 3 个单元操作
}
}
}
return count;
}
/* 平方阶(冒泡排序) */
int BubbleSort(int[] nums) {
int count = 0; // 计数器
// 外循环:未排序区间为 [0, i]
for (int i = nums.Length - 1; i > 0; i--) {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
(nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
count += 3; // 元素交换包含 3 个单元操作
}
}
}
return count;
}
/* 平方阶(冒泡排序) */
func bubbleSort(nums []int) int {
count := 0 // 计数器
// 外循环:未排序区间为 [0, i]
for i := len(nums) - 1; i > 0; i-- {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for j := 0; j < i; j++ {
if nums[j] > nums[j+1] {
// 交换 nums[j] 与 nums[j + 1]
tmp := nums[j]
nums[j] = nums[j+1]
nums[j+1] = tmp
count += 3 // 元素交换包含 3 个单元操作
}
}
}
return count
}
/* 平方阶(冒泡排序) */
func bubbleSort(nums: inout [Int]) -> Int {
var count = 0 // 计数器
// 外循环:未排序区间为 [0, i]
for i in nums.indices.dropFirst().reversed() {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for j in 0 ..< i {
if nums[j] > nums[j + 1] {
// 交换 nums[j] 与 nums[j + 1]
let tmp = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = tmp
count += 3 // 元素交换包含 3 个单元操作
}
}
}
return count
}
/* 平方阶(冒泡排序) */
function bubbleSort(nums) {
let count = 0; // 计数器
// 外循环:未排序区间为 [0, i]
for (let i = nums.length - 1; i > 0; i--) {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (let j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
let tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
count += 3; // 元素交换包含 3 个单元操作
}
}
}
return count;
}
/* 平方阶(冒泡排序) */
function bubbleSort(nums: number[]): number {
let count = 0; // 计数器
// 外循环:未排序区间为 [0, i]
for (let i = nums.length - 1; i > 0; i--) {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (let j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
let tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
count += 3; // 元素交换包含 3 个单元操作
}
}
}
return count;
}
/* 平方阶(冒泡排序) */
int bubbleSort(List<int> nums) {
int count = 0; // 计数器
// 外循环:未排序区间为 [0, i]
for (var i = nums.length - 1; i > 0; i--) {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (var j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
count += 3; // 元素交换包含 3 个单元操作
}
}
}
return count;
}
/* 平方阶(冒泡排序) */
fn bubble_sort(nums: &mut [i32]) -> i32 {
let mut count = 0; // 计数器
// 外循环:未排序区间为 [0, i]
for i in (1..nums.len()).rev() {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for j in 0..i {
if nums[j] > nums[j + 1] {
// 交换 nums[j] 与 nums[j + 1]
let tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
count += 3; // 元素交换包含 3 个单元操作
}
}
}
count
}
/* 平方阶(冒泡排序) */
int bubbleSort(int *nums, int n) {
int count = 0; // 计数器
// 外循环:未排序区间为 [0, i]
for (int i = n - 1; i > 0; i--) {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
count += 3; // 元素交换包含 3 个单元操作
}
}
}
return count;
}
/* 平方阶(冒泡排序) */
fun bubbleSort(nums: IntArray): Int {
var count = 0 // 计数器
// 外循环:未排序区间为 [0, i]
for (i in nums.size - 1 downTo 1) {
// 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (j in 0..<i) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
val temp = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = temp
count += 3 // 元素交换包含 3 个单元操作
}
}
}
return count
}
### 平方阶(冒泡排序)###
def bubble_sort(nums)
count = 0 # 计数器
# 外循环:未排序区间为 [0, i]
for i in (nums.length - 1).downto(0)
# 内循环:将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for j in 0...i
if nums[j] > nums[j + 1]
# 交换 nums[j] 与 nums[j + 1]
tmp = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = tmp
count += 3 # 元素交换包含 3 个单元操作
end
end
end
count
end
可视化运行
4. 指数阶 \(O(2^n)\)¶
生物学的“细胞分裂”是指数阶增长的典型例子:初始状态为 \(1\) 个细胞,分裂一轮后变为 \(2\) 个,分裂两轮后变为 \(4\) 个,以此类推,分裂 \(n\) 轮后有 \(2^n\) 个细胞。
图 2-11 和以下代码模拟了细胞分裂的过程,时间复杂度为 \(O(2^n)\) 。请注意,输入 \(n\) 表示分裂轮数,返回值 count 表示总分裂次数。
可视化运行
图 2-11 指数阶的时间复杂度
图解 2-11:每层一分为二的递归树
递归树每往下一层,节点数量翻倍;统计总工作量需要累加各层。
每个方块代表一个计算操作,根计为第 1 层。顶部标“递归树,每层一分为二”,右侧大括号标“共 n 层”;n 为正整数。
图画出前三层的 1、2、4 个节点,每个非末层节点连接两个子节点。第 3 层下方的 8 条箭头接省略号;末层画出 8 个由省略号间隔的方块,只作示意,并不表示末层固定有 8 个节点。右列用幂次标出各层数量,下表中的十进制值是计算补充。 n ≤ 3 时只取实际存在的层,表中 n 行与前面对应层重合。
| 层(根为第 1 层) | 节点数 |
|---|---|
| 1 | 2⁰ = 1 |
| 2 | 2¹ = 2 |
| 3 | 2² = 4 |
| n | 2ⁿ⁻¹,即 2 的 n−1 次方 |
底部将各层相加:2⁰ + 2¹ + … + 2ⁿ⁻¹ = 2ⁿ − 1,即 2 的 n 次方减 1,对应 O(2ⁿ)。对图前的细胞分裂循环,第 k 层表示第 k 轮各细胞发生的分裂动作:n 轮累计有 2ⁿ − 1 次分裂,完成后有 2ⁿ 个细胞,末态细胞并未作为下一层操作画出。对图后的 exp_recur(n),方块则对应调用:参数从 n 递减至 1,共 n 层,每次调用计 1,返回同样的累计数。
在实际算法中,指数阶常出现于递归函数中。例如在以下代码中,其递归地一分为二,经过 \(n\) 次分裂后停止:
可视化运行
指数阶增长非常迅速,在穷举法(暴力搜索、回溯等)中比较常见。对于数据规模较大的问题,指数阶是不可接受的,通常需要使用动态规划或贪心算法等来解决。
5. 对数阶 \(O(\log n)\)¶
与指数阶相反,对数阶反映了“每轮缩减到一半”的情况。设输入数据大小为 \(n\) ,由于每轮缩减到一半,因此循环次数是 \(\log_2 n\) ,即 \(2^n\) 的反函数。
图 2-12 和以下代码模拟了“每轮缩减到一半”的过程,时间复杂度为 \(O(\log_2 n)\) ,简记为 \(O(\log n)\) :
可视化运行
图 2-12 对数阶的时间复杂度
图解 2-12:每次保留一半的对数增长
每轮把剩余长度减半,图中将保留状态与每层的计算操作一一对应。
设 n 为 2 的非负整数次幂。图分左、中、右三列:“剩余数组长度”“输入数组长度为 n,每层删减一半”“每层包含 1 个计算操作”。深绿色格子及外框表示保留区间,浅灰色格子表示排除区间。
顶部省略号代表前面的减半过程,其下画出最后四层。右列每层有一个浅绿色操作方块,由向下箭头连接;最右大括号标“共 log₂n + 1 层”,底部也把图中操作总数写作 log₂n + 1,指向 O(log n)。
| 剩余长度 | 8 格数组中的保留区间 |
|---|---|
| 8 | 全部 8 格 |
| 4 | 最右 4 格 |
| 2 | 最右 2 格 |
| 1 | 最右 1 格 |
从 n 减半到 1 要做 log₂n 次减半,代码 while n > 1 返回的 count 正是这个次数;图还把长度 1 的末层计为 1 次操作,因此比代码 count 多 1。例如 8 → 4 → 2 → 1 有 3 次减半、4 个状态层。这个常数差不改变对数阶 O(log n)。图中的省略与四行是一般规模的示意,小输入只经过实际存在的层。
与指数阶类似,对数阶也常出现于递归函数中。以下代码形成了一棵高度为 \(\log_2 n\) 的递归树:
可视化运行
对数阶常出现于基于分治策略的算法中,体现了“一分为多”和“化繁为简”的算法思想。它增长缓慢,是仅次于常数阶的理想的时间复杂度。
\(O(\log n)\) 的底数是多少?
准确来说,“一分为 \(m\)”对应的时间复杂度是 \(O(\log_m n)\) 。而通过对数换底公式,我们可以得到具有不同底数、相等的时间复杂度:
也就是说,底数 \(m\) 可以在不影响复杂度的前提下转换。因此我们通常会省略底数 \(m\) ,将对数阶直接记为 \(O(\log n)\) 。
6. 线性对数阶 \(O(n \log n)\)¶
线性对数阶常出现于嵌套循环中,两层循环的时间复杂度分别为 \(O(\log n)\) 和 \(O(n)\) 。相关代码如下:
可视化运行
图 2-13 展示了线性对数阶的生成方式。二叉树的每一层的操作总数都为 \(n\) ,树共有 \(\log_2 n + 1\) 层,因此时间复杂度为 \(O(n \log n)\) 。
图 2-13 线性对数阶的时间复杂度
图解 2-13:分治树的分层工作量
子问题数量加倍、单个工作量减半,使每层总工作量保持相同。
设 n 为 2 的非负整数次幂。图中的方框代表子问题,每个节点的操作数等于当前规模;从根开始,子问题逐层一分为二。
右侧按层统计操作总数。最底层只画了 4 个由省略号间隔的方框,代表全部 n 个叶子。下表按一般规模列出各层;小 n 可能没有中间层,叶层也可能与前面的行重合,并非固定有 5 层。
| 层级 | 子问题数 | 单个子问题操作数 | 本层总数 |
|---|---|---|---|
| 根层 | 1 | n | n |
| 下一层 | 2 | n/2 | n |
| 再下一层 | 4 | n/4 | n |
| 中间层(若有) | 继续加倍 | 继续减半 | n |
| 叶层 | n | 1 | n |
根编号为第 0 层,第 d 层有 2^d 个子问题,各做 n/2^d 次操作,相乘恒为 n。叶层每个子问题规模为 1,即 2^d = n,所以 d = log₂n;从第 0 层到第 log₂n 层共 log₂n + 1 层。底部将每层的 n 与层数相乘,得 n(log₂n + 1) = n log₂n + n,对应 O(n log n)。
主流排序算法的时间复杂度通常为 \(O(n \log n)\) ,例如快速排序、归并排序、堆排序等。
7. 阶乘阶 \(O(n!)\)¶
阶乘阶对应数学上的“全排列”问题。给定 \(n\) 个互不重复的元素,求其所有可能的排列方案,方案数量为:
阶乘通常使用递归实现。如图 2-14 和以下代码所示,第一层分裂出 \(n\) 个,第二层分裂出 \(n - 1\) 个,以此类推,直至第 \(n\) 层时停止分裂:
可视化运行
图 2-14 阶乘阶的时间复杂度
图解 2-14:全排列的逐层选择与阶乘增长
全排列每多确定一个位置,可选元素就少一个;各层选择数连乘,得到排列总数。
n 个元素互不重复。最上方灰色根节点表示尚未选择,下面每个虚线框层确定下一个位置。右侧“共 n 层”的大括号只覆盖根下面的选择层,不含根。
图左列“各层的分裂数量”表示每个上一层节点有几个子分支,右列“各层的节点数量”表示本层节点总数。中间层用省略号表示;较小 n 只经过实际需要的选择层,表中末层可能与前面某一层重合。
| 选择层 | 每个上一层节点的分支数 | 本层节点总数 |
|---|---|---|
| 1 | n | n |
| 2 | n−1 | n(n−1) |
| 3 | n−2 | n(n−1)(n−2) |
| 中间层(若有) | 逐层减 1 | 继续累乘 |
| n,末层 | 1 | n! |
底部公式 n × (n−1) × … × 1 = n! 统计最底层绿色叶节点,每个叶节点对应一种完整排列,也对应 factorial_recur 返回值中的一个基例计数;n! 不是全树节点总数。计入根和全部中间层后,总节点数仍小于 n! 的 3 倍。代码中一次调用虽然含循环,但每次循环恰好产生一条到子调用的边,全树边数等于总节点数减 1,因此这些循环开销计入后仍为 O(n!)。这个结论按每条边做常数操作计,不包含复制完整排列的额外开销。
请注意,因为当 \(n \geq 4\) 时恒有 \(n! > 2^n\) ,所以阶乘阶比指数阶增长得更快,在 \(n\) 较大时也是不可接受的。
2.3.5 最差、最佳、平均时间复杂度¶
算法的时间效率往往不是固定的,而是与输入数据的分布有关。假设输入一个长度为 \(n\) 的数组 nums ,其中 nums 由从 \(1\) 至 \(n\) 的数字组成,每个数字只出现一次;但元素顺序是随机打乱的,任务目标是返回元素 \(1\) 的索引。我们可以得出以下结论。
- 当
nums = [?, ?, ..., 1],即当末尾元素是 \(1\) 时,需要完整遍历数组,达到最差时间复杂度 \(O(n)\) 。 - 当
nums = [1, ?, ?, ...],即当首个元素为 \(1\) 时,无论数组多长都不需要继续遍历,达到最佳时间复杂度 \(\Omega(1)\) 。
“最差时间复杂度”对应函数渐近上界,使用大 \(O\) 记号表示。相应地,“最佳时间复杂度”对应函数渐近下界,用 \(\Omega\) 记号表示:
def random_numbers(n: int) -> list[int]:
"""生成一个数组,元素为: 1, 2, ..., n ,顺序被打乱"""
# 生成数组 nums =: 1, 2, 3, ..., n
nums = [i for i in range(1, n + 1)]
# 随机打乱数组元素
random.shuffle(nums)
return nums
def find_one(nums: list[int]) -> int:
"""查找数组 nums 中数字 1 所在索引"""
for i in range(len(nums)):
# 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
# 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if nums[i] == 1:
return i
return -1
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
vector<int> randomNumbers(int n) {
vector<int> nums(n);
// 生成数组 nums = { 1, 2, 3, ..., n }
for (int i = 0; i < n; i++) {
nums[i] = i + 1;
}
// 使用系统时间生成随机种子
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
// 随机打乱数组元素
shuffle(nums.begin(), nums.end(), default_random_engine(seed));
return nums;
}
/* 查找数组 nums 中数字 1 所在索引 */
int findOne(vector<int> &nums) {
for (int i = 0; i < nums.size(); i++) {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if (nums[i] == 1)
return i;
}
return -1;
}
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
int[] randomNumbers(int n) {
Integer[] nums = new Integer[n];
// 生成数组 nums = { 1, 2, 3, ..., n }
for (int i = 0; i < n; i++) {
nums[i] = i + 1;
}
// 随机打乱数组元素
Collections.shuffle(Arrays.asList(nums));
// Integer[] -> int[]
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nums[i];
}
return res;
}
/* 查找数组 nums 中数字 1 所在索引 */
int findOne(int[] nums) {
for (int i = 0; i < nums.length; i++) {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if (nums[i] == 1)
return i;
}
return -1;
}
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
int[] RandomNumbers(int n) {
int[] nums = new int[n];
// 生成数组 nums = { 1, 2, 3, ..., n }
for (int i = 0; i < n; i++) {
nums[i] = i + 1;
}
// 随机打乱数组元素
for (int i = 0; i < nums.Length; i++) {
int index = new Random().Next(i, nums.Length);
(nums[i], nums[index]) = (nums[index], nums[i]);
}
return nums;
}
/* 查找数组 nums 中数字 1 所在索引 */
int FindOne(int[] nums) {
for (int i = 0; i < nums.Length; i++) {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if (nums[i] == 1)
return i;
}
return -1;
}
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
func randomNumbers(n int) []int {
nums := make([]int, n)
// 生成数组 nums = { 1, 2, 3, ..., n }
for i := 0; i < n; i++ {
nums[i] = i + 1
}
// 随机打乱数组元素
rand.Shuffle(len(nums), func(i, j int) {
nums[i], nums[j] = nums[j], nums[i]
})
return nums
}
/* 查找数组 nums 中数字 1 所在索引 */
func findOne(nums []int) int {
for i := 0; i < len(nums); i++ {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if nums[i] == 1 {
return i
}
}
return -1
}
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
func randomNumbers(n: Int) -> [Int] {
// 生成数组 nums = { 1, 2, 3, ..., n }
var nums = Array(1 ... n)
// 随机打乱数组元素
nums.shuffle()
return nums
}
/* 查找数组 nums 中数字 1 所在索引 */
func findOne(nums: [Int]) -> Int {
for i in nums.indices {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if nums[i] == 1 {
return i
}
}
return -1
}
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
function randomNumbers(n) {
const nums = Array(n);
// 生成数组 nums = { 1, 2, 3, ..., n }
for (let i = 0; i < n; i++) {
nums[i] = i + 1;
}
// 随机打乱数组元素
for (let i = 0; i < n; i++) {
const r = Math.floor(Math.random() * (i + 1));
const temp = nums[i];
nums[i] = nums[r];
nums[r] = temp;
}
return nums;
}
/* 查找数组 nums 中数字 1 所在索引 */
function findOne(nums) {
for (let i = 0; i < nums.length; i++) {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if (nums[i] === 1) {
return i;
}
}
return -1;
}
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
function randomNumbers(n: number): number[] {
const nums = Array(n);
// 生成数组 nums = { 1, 2, 3, ..., n }
for (let i = 0; i < n; i++) {
nums[i] = i + 1;
}
// 随机打乱数组元素
for (let i = 0; i < n; i++) {
const r = Math.floor(Math.random() * (i + 1));
const temp = nums[i];
nums[i] = nums[r];
nums[r] = temp;
}
return nums;
}
/* 查找数组 nums 中数字 1 所在索引 */
function findOne(nums: number[]): number {
for (let i = 0; i < nums.length; i++) {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if (nums[i] === 1) {
return i;
}
}
return -1;
}
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
List<int> randomNumbers(int n) {
final nums = List.filled(n, 0);
// 生成数组 nums = { 1, 2, 3, ..., n }
for (var i = 0; i < n; i++) {
nums[i] = i + 1;
}
// 随机打乱数组元素
nums.shuffle();
return nums;
}
/* 查找数组 nums 中数字 1 所在索引 */
int findOne(List<int> nums) {
for (var i = 0; i < nums.length; i++) {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if (nums[i] == 1) return i;
}
return -1;
}
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
fn random_numbers(n: i32) -> Vec<i32> {
// 生成数组 nums = { 1, 2, 3, ..., n }
let mut nums = (1..=n).collect::<Vec<i32>>();
// 随机打乱数组元素
nums.shuffle(&mut thread_rng());
nums
}
/* 查找数组 nums 中数字 1 所在索引 */
fn find_one(nums: &[i32]) -> Option<usize> {
for i in 0..nums.len() {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if nums[i] == 1 {
return Some(i);
}
}
None
}
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
int *randomNumbers(int n) {
// 分配堆区内存(创建一维可变长数组:数组中元素数量为 n ,元素类型为 int )
int *nums = (int *)malloc(n * sizeof(int));
// 生成数组 nums = { 1, 2, 3, ..., n }
for (int i = 0; i < n; i++) {
nums[i] = i + 1;
}
// 随机打乱数组元素
for (int i = n - 1; i > 0; i--) {
int j = rand() % (i + 1);
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
return nums;
}
/* 查找数组 nums 中数字 1 所在索引 */
int findOne(int *nums, int n) {
for (int i = 0; i < n; i++) {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if (nums[i] == 1)
return i;
}
return -1;
}
/* 生成一个数组,元素为 { 1, 2, ..., n },顺序被打乱 */
fun randomNumbers(n: Int): Array<Int?> {
val nums = IntArray(n)
// 生成数组 nums = { 1, 2, 3, ..., n }
for (i in 0..<n) {
nums[i] = i + 1
}
// 随机打乱数组元素
nums.shuffle()
val res = arrayOfNulls<Int>(n)
for (i in 0..<n) {
res[i] = nums[i]
}
return res
}
/* 查找数组 nums 中数字 1 所在索引 */
fun findOne(nums: Array<Int?>): Int {
for (i in nums.indices) {
// 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
// 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
if (nums[i] == 1)
return i
}
return -1
}
### 生成一个数组,元素为: 1, 2, ..., n ,顺序被打乱 ###
def random_numbers(n)
# 生成数组 nums =: 1, 2, 3, ..., n
nums = Array.new(n) { |i| i + 1 }
# 随机打乱数组元素
nums.shuffle!
end
### 查找数组 nums 中数字 1 所在索引 ###
def find_one(nums)
for i in 0...nums.length
# 当元素 1 在数组头部时,达到最佳时间复杂度 O(1)
# 当元素 1 在数组尾部时,达到最差时间复杂度 O(n)
return i if nums[i] == 1
end
-1
end
可视化运行
值得说明的是,我们在实际中很少使用最佳时间复杂度,因为通常只有在很小概率下才能达到,可能会带来一定的误导性。而最差时间复杂度更为实用,因为它给出了一个效率安全值,让我们可以放心地使用算法。
从上述示例可以看出,最差时间复杂度和最佳时间复杂度只出现于“特殊的数据分布”,这些情况的出现概率可能很小,并不能真实地反映算法运行效率。相比之下,平均时间复杂度可以体现算法在随机输入数据下的运行效率,用 \(\Theta\) 记号来表示。
对于部分算法,我们可以简单地推算出随机数据分布下的平均情况。比如上述示例,由于输入数组是被打乱的,因此元素 \(1\) 出现在任意索引的概率都是相等的,那么算法的平均循环次数就是数组长度的一半 \(n / 2\) ,平均时间复杂度为 \(\Theta(n / 2) = \Theta(n)\) 。
但对于较为复杂的算法,计算平均时间复杂度往往比较困难,因为很难分析出在数据分布下的整体数学期望。在这种情况下,我们通常使用最差时间复杂度作为算法效率的评判标准。
为什么很少看到 \(\Theta\) 符号?
可能由于 \(O\) 符号过于朗朗上口,因此我们常常使用它来表示平均时间复杂度。但从严格意义上讲,这种做法并不规范。在本书和其他资料中,若遇到类似“平均时间复杂度 \(O(n)\)”的表述,请将其直接理解为 \(\Theta(n)\) 。