算法复杂度分析基础:从代码计数到时间与空间复杂度

插画:原神官方
从代码判断效率,可以先数一个明确的基本操作,再看输入扩大时次数怎样增长。同时还要检查:运行时额外保存了多少数据?
本文使用Python循环、数组和递归建立时间与空间分析的方法。读者需要熟悉变量、列表、循环和函数。
上一篇:导论。下一篇:渐进符号与函数增长率。
1. 输入规模与基本操作
数组可用元素个数n作为规模;字符串问题可能有两个长度m、n;图问题常同时需要顶点数和边数。
整数N的数值与其编码长度不同。正整数N的二进制位数为 $\lfloor\log_2 N\rfloor+1$,所以循环N次与循环编码位数次的资源需求不同。
以下将一次比较、索引、交换或计数更新作为基本操作,采用单位代价模型;空间以同时存活的变量或元素槽位衡量。若计算大整数的实际位运算成本,还需按整数位数进一步分析。
1.1 寻找最大值
def maximum(values):
if not values:
raise ValueError("Expected a nonempty list")
best = values[0]
for i in range(1, len(values)):
value = values[i]
if value > best:
best = value
return best
当数组有5个元素时,比较4次;有100个元素时,比较99次。如果只统计 value > best 的执行次数,就有:
注意这里统计的是一种操作的次数,不是所有机器指令的精确总数。做复杂度分析前,要说清楚采用的模型和统计对象。
这段实现按下标读取数组,只保存下标、当前值和当前最大值,使用常数额外空间。
整个函数还执行索引和赋值,但这些操作也只随n线性增长。
1.2 怎样使用复杂度记号
O给出增长上界;Θ表示与某个函数同阶,即上下都能被该函数的固定倍数夹住。例如n−1次比较随n线性增长,总时间Θ(n),也可以给出上界O(n)。
本篇先从具体次数理解这些记号,严格的常数和量词定义见渐进符号篇。
2. 六种循环的代码计数
下面统计count += 1的次数,时间结论也计入循环控制和初始化,沿用单位代价模型。空间不计输入与返回标量。
2.1 单层循环
def single_count(n):
count = 0
for _ in range(n):
count += 1
return count
assert single_count(4) == 4
操作次数 $C(n)=n$,时间Θ(n),额外空间O(1)。
2.2 顺序执行的两个循环
def sequential_count(n):
count = 0
for _ in range(n):
count += 1
for _ in range(n):
count += 1
return count
assert sequential_count(4) == 8
操作次数 $C(n)=n+n=2n$,时间Θ(n),额外空间O(1)。顺序执行的工作量相加。
2.3 完全嵌套
def square_count(n):
count = 0
for _ in range(n):
for _ in range(n):
count += 1
return count
assert square_count(4) == 16
每轮内层n次,外层n轮:$C(n)=n^2$。时间Θ(n²),额外空间O(1)。执行n²次操作,并没有同时保存n²个元素。
2.4 三角形循环
def triangular_count(n):
count = 0
for i in range(1, n + 1):
for _ in range(i):
count += 1
return count
assert triangular_count(4) == 10
n=4时,四轮分别执行1、2、3、4次,共10次。
求和表示把每轮次数相加。时间Θ(n²),额外空间O(1)。
进阶阅读:求和式的归纳证明
n=1时成立。假设前k项之和为 $k(k+1)/2$,加上k+1得到:
$$ \frac{k(k+1)}2+(k+1)=\frac{(k+1)(k+2)}2 $$这正是下一规模的公式,因此等式对所有正整数成立。
2.5 i每轮翻倍
def doubling_count(n):
count = 0
i = 1
while i <= n:
count += 1
i *= 2
return count
assert doubling_count(16) == 5
assert doubling_count(0) == 0
访问1、2、4、8、16,共5次。第k次翻倍后为 $2^k$;要进入循环,需 $2^k\le n$。因此:
$$ C(n)=\lfloor\log_2n\rfloor+1\qquad(n\ge1) $$时间Θ(log n),额外空间O(1)。n=0直接返回。折半查找缩小候选区间的过程具有同样的对数结构,见查找文章。
2.6 外层线性、内层对数
def linear_log_count(n):
count = 0
for _ in range(n):
i = 1
while i <= n:
count += 1
i *= 2
return count
assert linear_log_count(4) == 12
每轮把i重置为1,操作次数 $n(\lfloor\log_2n\rfloor+1)$(n≥1),时间Θ(n log n),额外空间O(1)。
2.7 核对计数
for n in (1, 4, 16):
triangle = triangular_count(n)
doubling = doubling_count(n)
assert triangle == n * (n + 1) // 2
assert doubling == n.bit_length()
print(n, triangle, doubling)
输出:
1 1 1
4 10 3
16 136 5
3. 时间与空间是两个维度
3.1 三种空间口径
输入空间是调用前提供的数据;辅助空间是运行额外保存的变量、临时数组与调用栈;输出空间是返回结果所需的结构。
本文“额外空间”指输入之外的空间,并说明输出是否计入。分析的是同时存活数据的峰值。
3.2 对比三个实现
第1节maximum只保存几个变量,时间Θ(n),额外空间O(1)。
复制输入则要创建新列表:
def copy_values(values):
copied = []
for value in values:
copied.append(value)
return copied
assert copy_values([3, 1, 4]) == [3, 1, 4]
append在摊还意义下为常数时间,n次添加共Θ(n)时间。新列表保存n个引用;计入返回列表时额外空间Θ(n)。若只计辅助空间,则辅助O(1),输出Θ(n)。这是浅复制,元素对象本身没有逐个复制。
再创建长度n的临时数组:
def count_above_average(values):
n = len(values)
if n == 0:
return 0
average = sum(values) / n
flags = [0] * n
for i in range(n):
flags[i] = int(values[i] > average)
return sum(flags)
assert count_above_average([1, 2, 6]) == 1
两次求和、初始化与扫描均为线性,总时间Θ(n),辅助数组flags占Θ(n),输出是一个计数。
| 程序 | 时间 | 额外空间(含输出) | 原因 |
|---|---|---|---|
| maximum | Θ(n) | O(1) | 几个变量 |
| copy_values | Θ(n) | Θ(n) | 新列表是输出 |
| count_above_average | Θ(n) | Θ(n) | 临时标记数组 |
[0] * n只有一行,初始化n个槽位仍需Θ(n)时间和空间。循环是O(n),并不意味着空间也是O(n)。
4. 指数与阶乘:候选数量如何增长
4.1 O(1):固定数量的访问
def first_or_none(values):
return values[0] if values else None
assert first_or_none([8, 3]) == 8
对普通Python列表,只检查长度并访问第一项,时间、辅助空间均为O(1)。
4.2 O(2ⁿ):每项选或不选
每个元素有两种状态,n个元素有 $2^n$ 个子集。n为10、20、40时,数量依次为1,024、1,048,576、1,099,511,627,776。
代码训练:二叉递归的叶子数量
def subset_leaves(n):
if n < 0:
raise ValueError("Expected n >= 0")
if n == 0:
return 1
return subset_leaves(n - 1) + subset_leaves(n - 1)
assert subset_leaves(4) == 16
叶子共 $2^n$ 个,总调用数 $2^{n+1}-1$,时间Θ(2ⁿ)。两支依次执行,递归深度n,因此辅助空间O(n)。
若要复制每个长度n的选择向量,还需Θ(n2ⁿ)时间。候选数量与检查候选的成本要分别分析。
4.3 O(n!):排列
n个不同元素的排列有 $n!=n(n-1)\cdots1$ 个。
代码训练:原地交换统计排列
def permutation_leaves(n):
if n < 0:
raise ValueError("Expected n >= 0")
values = list(range(n))
count = 0
def visit(start):
nonlocal count
if start == n:
count += 1
return
for i in range(start, n):
values[start], values[i] = values[i], values[start]
visit(start + 1)
values[start], values[i] = values[i], values[start]
visit(0)
return count
assert permutation_leaves(4) == 24
assert permutation_leaves(0) == 1
深度k的调用有 $n!/(n-k)!$ 个。因为 $\sum_{j=0}^n1/j!<3$,总调用数介于n!与3n!之间,每条树边只作常数次交换,时间Θ(n!)。
列表与调用栈各占O(n),辅助空间O(n)。若把每个完整排列复制到输出,时间与输出空间变为Θ(nn!)。
4.4 常见复杂度对照
| 上界 | 对应代码 | 主要工作量 | 额外空间 |
|---|---|---|---|
| O(1) | first_or_none | 固定访问 | O(1) |
| O(log n) | doubling_count | 翻倍轮数 | O(1) |
| O(n) | maximum、single_count | 扫描n项 | O(1) |
| O(n log n) | linear_log_count | n轮对数循环 | O(1) |
| O(n²) | square_count、triangular_count | 二次求和 | O(1) |
| O(2ⁿ) | subset_leaves | 二叉树节点 | O(n)栈 |
| O(n!) | permutation_leaves | 排列树节点 | O(n) |
树的总节点数与同时存活的路径长度,分别影响时间与栈空间。
5. 最好、最坏与平均情况
def linear_search_count(values, target):
comparisons = 0
for i, value in enumerate(values):
comparisons += 1
if value == target:
return i, comparisons
return -1, comparisons
assert linear_search_count([7, 3, 9], 7) == (0, 1)
assert linear_search_count([7, 3, 9], 5) == (-1, 3)
固定非空数组长度n,最好情况是第一项命中,比较1次;最坏情况是最后命中或不存在,比较n次。
平均情况需要概率模型。假设目标一定存在、元素互异,每个位置命中的概率均为1/n,则期望次数为:
$$ \frac{1+2+\cdots+n}{n}=\frac{n+1}2 $$改变未找到的概率或各位置概率,平均值也会改变。这里首尾平均来自均匀分布。O(n)本身只给上界,既可以描述最坏函数,也可以描述平均函数。
6. 常数、低阶项与实际秒数
考虑两种工作量:
$$ A(n)=100n,\qquad B(n)=n\log_2 n $$当 $n=16$ 时,前者是1600,后者是64,B 更少。但当 $n>2^{100}$ 时,$\log_2 n>100$,A 反而更少。
所以渐进分析关注的是:当 n 足够大后,工作量以什么速度增长,而不是宣称在所有规模上某种算法都更快。常数在实际运行中仍然重要,只是在讨论增长阶时被统一吸收。
对照一下翻倍的效果:
| 工作量 | n 变成 2n 后,与原来的比值 |
|---|---|
| $n$ | 2 |
| $n^2$ | 4 |
| $n^3$ | 8 |
| $2^n$ | $2^n$,不是固定常数 |
更多增长比较见渐进符号篇。
$n^2+100n$ 与 $2n^2$ 都是二次阶;n>100时前者更小。舍去常数和低阶项,是在概括增长速度,不是把精确次数当作相等数值。7. 易错点
- 顺序循环次数相加,嵌套循环按每轮实际次数求和。
- 两层循环可以是n²、n log n或其他阶。
- 翻倍产生对数轮数,步长加2仍是线性。
- 代码行数不代表操作次数,库函数、切片和初始化也有成本。
- 时间统计全部工作,空间统计同时存活的数据。
- 实际秒数反映运行条件,复杂度反映规模增长。
8. 练习
前四题统计count += 1次数,n为非负整数;空间不计输入。
练习1:步长为2
def exercise_step(n):
count = 0
for _ in range(0, n, 2):
count += 1
return count
n=7时是多少?一般公式是什么?
练习2:顺序执行
def exercise_sequential(n):
count = 0
for _ in range(n):
count += 1
for _ in range(3 * n):
count += 1
return count
写出精确次数。
练习3:严格下三角
def exercise_triangle(n):
count = 0
for i in range(n):
for _ in range(i):
count += 1
return count
与第2.4节相比少几次?
练习4:严格小于n
def exercise_double(n):
count = 0
i = 1
while i < n:
count += 1
i *= 2
return count
n=1、8、9时各几次?给出n≥1的公式。
练习5:时间分析
先做n次操作再做n²次,与外层n次、内层n²次,各有多少次操作,属于什么时间阶?
练习6:线性对数
linear_log_count内层改为i < n,次数是多少?若外层不重置i,工作量如何变化?
练习7:复制列表
copy_values计入输出时的时间与额外空间是什么?只统计辅助空间时如何单列输出?
练习8:复用辅助数组
def exercise_scratch(n):
total = 0
scratch = [0] * n
for i in range(n):
for j in range(n):
scratch[j] = i + j
total += scratch[0] if n else 0
return total
分析时间和辅助空间,说明为什么不保存n²项数据。
9. 参考答案
- n=7时4次,一般 $\lceil n/2\rceil$,时间Θ(n),空间O(1)。
- $n+3n=4n$,时间Θ(n),空间O(1)。
- $n(n-1)/2$,少n次;时间Θ(n²),空间O(1)。
- 分别0、3、4次,n≥1时为 $\lceil\log_2n\rceil$。循环边界影响精确次数。
- 顺序执行 $n+n^2\in\Theta(n^2)$,嵌套执行 $n^3\in\Theta(n^3)$;只用计数器时空间均为O(1)。
- 次数为 $n\lceil\log_2n\rceil$。若i跨轮次延续,只在第一轮完成翻倍,但仍有n轮外层控制,总时间Θ(n+log n)=Θ(n)(n≥2)。
- 时间Θ(n);含输出时额外空间Θ(n),只计辅助则O(1)、输出Θ(n)。
- 初始化Θ(n),赋值n²次,总时间Θ(n²);scratch仅一份长度n的列表,空间Θ(n)。每轮覆盖旧值,没有保存此前所有轮次。
可以用AI助手逐题检查统计对象、次数公式和空间口径,再用小输入运行核对。
10. 后续学习与资料
下一篇:渐进符号与函数增长率给出严格定义和比较方法,之后在贪心算法中分析实际求解程序。
参考:《Design and Analysis of Algorithms》第二讲02Analysis,第2至13页的运行时间与规模,第15至26页的渐进语言,第42页的位运算模型。三角循环、翻倍计数和100n对比沿用原笔记,空间与代码训练在此展开。


