2.5 复杂度分析小结：把执行次数、存活状态与工程选择连起来

先把第 2 章连起来：执行了多少，同时保留了多少

这一篇接着 2.4 空间复杂度，对应原书 2.5 小结。我们把 2.1 的效率评估、2.2 的迭代与递归、2.3 的时间和 2.4 的空间放进同一套分析过程，再回答尾递归、函数与方法、增长曲线和资源取舍四类问题。

下文是基于本章主题的原创复盘与示例。数学计数属于推导，代码输出属于实际运行证据；几个成功样例不能替代对所有允许输入的正确性说明。

01 · 拿到一段代码，先问这六个问题

下面默认 n 为非负整数或输入长度，列表索引、固定大小数值比较和算术视作常数成本。这是便于分析的模型；Python 大整数、长字符串比较、对象方法和 I/O 的真实成本需要另外计入。

02 · 同一个查找函数：结果、比较次数、空间分别算

约定：在列表中返回目标第一次出现的位置；不存在时返回 None。第二个返回值仅用于展示实际比较次数。

示例输出：

10 (0, 1)
30 (2, 3)
99 (None, 4)
empty (None, 0)

def find_first(values, target):
    comparisons = 0
    for index, value in enumerate(values):
        comparisons += 1
        if value == target:
            return index, comparisons
    return None, comparisons

values = [10, 20, 30, 40]
for target in (10, 30, 99):
    print(target, find_first(values, target))
print('empty', find_first([], 10))

03 · O、Θ 与最好／最坏，是两组不同的问题

对上例、n≥1：首项命中只比较一次，最好情况 Θ(1)；末项命中或不存在要比较 n 次，最坏情况 Θ(n)。不计输入的辅助状态只保持当前元素引用、下标与计数，按固定大小数值模型为 Θ(1)；并没有把 n 个比较结果保存起来。

平均情况要有分布。若保证目标存在、且唯一匹配的位置在 0 到 n−1 之间等概率出现，期望比较次数为 (1+2+…+n)/n=(n+1)/2。如果一半请求根本不存在，或者目标总在开头，就应换用实际分布重新计算。

因此 O 不等于“最坏”，Ω 也不等于“最好”。原书常用 O 描述最坏情况，是常用表达组合，不是符号定义。比如最坏比较数 n 既属于 O(n)，也属于 O(n²)，而 Θ(n) 更精确。这里的增长不代表任何固定秒数。

04 · 两层循环先数真实次数，一层循环也可能只有对数轮

三个函数只用于计数：fixed_inner 的内层每轮固定三次；triangle 的内层随 i 增长；doubling 的状态每轮翻倍。

所以前两者分别为 Θ(n) 与 Θ(n²)。第三者在 n≥1 时恰有 ⌈log₂n⌉ 轮，n=0 时为 0 轮；渐近为 Θ(log n)。若把三个过程顺序执行，成本相加后由平方项主导，而不是把三个次数相乘。

示例输出：

0 0 0 0
1 3 0 0
4 12 6 2
8 24 28 3
9 27 36 4

def fixed_inner(n):
    count = 0
    for _ in range(n):
        for _ in range(3):
            count += 1
    return count

def triangle(n):
    count = 0
    for i in range(n):
        for _ in range(i):
            count += 1
    return count

def doubling(n):
    count = 0
    i = 1
    while i < n:
        count += 1
        i *= 2
    return count

for n in (0, 1, 4, 8, 9):
    print(n, fixed_inner(n), triangle(n), doubling(n))

05 · 累计创建 n² 个位置，峰值也一定是 n² 吗？

两个版本都创建 n 个长度为 n 的列表。区别是第一版每轮结束就解除当前列表引用，第二版用 rows 保留所有列表。

下列 peak_slots 是按程序状态计算的内层列表元素槽位数量，不是内存测量器；不包括外层列表的 n 个引用、对象头和解释器开销。列表里的 None 引用可共享，不代表创建 n² 个 None 对象。

创建槽位的累计工作均为 Θ(n²)。第一版的算法活跃数据峰值为 Θ(n)，第二版为 Θ(n²)。del row 解除引用，不承诺操作系统立即回收对应物理内存；进程 RSS、分配器保留空间与算法活跃数据是不同口径。

示例输出：

release (9, 3)
retain (9, 9)
empty (0, 0) (0, 0)

def release_each(n):
    created_slots = 0
    peak_slots = 0
    for _ in range(n):
        row = [None] * n
        created_slots += len(row)
        peak_slots = max(peak_slots, len(row))
        del row
    return created_slots, peak_slots

def keep_all(n):
    rows = []
    created_slots = 0
    live_slots = 0
    peak_slots = 0
    for _ in range(n):
        row = [None] * n
        rows.append(row)
        created_slots += len(row)
        live_slots += len(row)
        peak_slots = max(peak_slots, live_slots)
    return created_slots, peak_slots

print('release', release_each(3))
print('retain', keep_all(3))
print('empty', release_each(0), keep_all(0))

06 · 普通递归、尾递归、循环：答案相同，保留状态不同

三种实现都计算 1 到 n 的和；n=0 返回 0；负数与非整数被明确拒绝。普通递归返回时还要相加；尾递归在调用前更新 total；循环在同一次调用中更新变量。

到达 n=0 的瞬间，这条链上有 4 个尚未结束的调用。尾递归参数会依次成为 (3,0) → (2,3) → (1,5) → (0,6)，但在 CPython 中这些调用仍会保留；尾递归的写法不会自动得到常数帧空间。Python 3.14 官方文档明确区分解释器内部的尾调用与 Python 函数尾调用优化。

示例输出：

0 0 0 0
1 1 1 1
3 6 6 6
10 55 55 55

def check_n(n):
    if type(n) is not int:
        raise TypeError('n must be an integer')
    if n < 0:
        raise ValueError('n must be non-negative')

def sum_recursive(n):
    check_n(n)
    if n == 0:
        return 0
    return n + sum_recursive(n - 1)

def sum_tail(n, total=0):
    check_n(n)
    if n == 0:
        return total
    return sum_tail(n - 1, total + n)

def sum_loop(n):
    check_n(n)
    total = 0
    for value in range(1, n + 1):
        total += value
    return total

for n in (0, 1, 3, 10):
    print(n, sum_recursive(n), sum_tail(n), sum_loop(n))

07 · 总调用数、峰值深度、每帧数据，三项要分开

表中把整数当作固定大小的值。若严格统计 Python 任意精度整数的位数，求和结果需要 Θ(log n) 位，循环的整数状态也随位数增长；因此这里的 Θ(1) 不应理解为任意大的 n 都只占固定字节。递归也会受解释器深度限制，上例只验证有限的小输入，不建议用提高递归上限替代算法选择。

对于分支递归，调用树可能有指数数量的节点，但一次顺序执行时只保留当前调用链等活跃状态。例如朴素 Fibonacci 的总工作呈指数增长，最大深度仍为 O(n)。反过来，即使深度只有 n，如果每帧都保留长度递减的切片，活跃容器可能累计为 n+(n−1)+…+1，即 Θ(n²)。详见 递归树 与 空间统计。

08 · 用内存减少重复比较：两种查重方式

具体问题：输入一个固定大小整数序列，判断是否存在重复元素，不修改输入。第一版拿每一对元素比较；第二版记住已经出现过的值。

以 [7, 2, 7] 为例，集合状态依次为：空集合 → {7} → {2, 7}；第三个值 7 已经存在，立即返回 True。循环进入每轮前，seen 恰好包含先前访问过的值；这就是判断成立的依据。

集合时间结论依赖哈希与比较成本及冲突条件，不能宣称每次查询最坏都 O(1)。集合要求元素可哈希；列表之类的可变容器不能直接作为集合元素。两两比较版本可以比较嵌套列表，但这时每次比较也可能不再是常数成本。因此比较两个方案前，先对齐输入契约。

示例输出：

[] False False
[7] False False
[7, 2, 7] True True
[7, 2, 9] False False

def has_duplicate_pairs(values):
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] == values[j]:
                return True
    return False

def has_duplicate_set(values):
    seen = set()
    for value in values:
        if value in seen:
            return True
        seen.add(value)
    return False

for values in ([], [7], [7, 2, 7], [7, 2, 9]):
    print(values, has_duplicate_pairs(values), has_duplicate_set(values))

09 · 增长曲线不能直接当作秒数，也不能只看阶数选方案

考虑两个假设的工作量模型 A(n)=1000n，B(n)=n²。它们不是本次实测结果，基本操作成本也是假定相同的。

A 的增长阶更低，但小规模时未必更便宜；两者同为 Θ(n) 时，也不能从阶数看出常数差异。常见增长关系为 1、log n、n、n log n、n²、2ⁿ、n!，描述的是规模充分增大后的趋势，不给出某次执行的绝对耗时或字节数。

实测与分析互补。在 SDET 场景下，可以把查重理解为测试结果 ID 去重：分别选无重复、早期重复和晚期重复输入；固定相同数据、解释器与计时范围；先校验结果，再重复测量并保存每轮数据。若生产路径包含建立集合，计时不能故意排除建表成本。timeit 的 setup 不计入测试段，repeat 会返回多轮结果；其默认临时关闭 GC 也可能影响所测场景。

环境波动、缓存、输入分布和延迟预算仍需要工程判断。单次跑得快不是复杂度证明，理论阶数低也不是生产性能验收。计时设计和已实测数据见 2.1 算法效率评估。

10 · 原书问答：函数与方法，为什么 self 看起来没传？

普通函数 scale(value, factor) 显式接收两个参数。Measurement.scale 定义在类中；通过实例 reading 取得 reading.scale 时，得到绑定这个实例的方法。调用 reading.scale(2)，Python 将 reading 作为第一个参数传给函数。

在这个普通实例方法例子里，reading.scale(2) 等价于 Measurement.scale(reading, 2)。self 是参数名的约定，不是新建对象，也不是复制整个实例；方法用它访问原对象的 value。

示例输出：

24
24
24
12

def scale(value, factor):
    return value * factor

class Measurement:
    def __init__(self, value):
        self.value = value

    def scale(self, factor):
        return self.value * factor

reading = Measurement(12)
print(scale(12, 2))
print(reading.scale(2))
print(Measurement.scale(reading, 2))
print(reading.value)

11 · “属于类”不意味着所有调用都自动传实例

上节解释的是普通绑定实例方法。staticmethod 不自动传入实例，classmethod 则绑定类；不能把“所有方法都会隐式传对象实例”当成普遍规则。Python 还允许把函数存入变量、作为参数传递，或从函数中返回。

对复杂度而言，应看函数／方法体具体执行的工作，以及访问和创建的数据。把同一段循环放进类里，不会仅因为名字变成“方法”就从 Θ(n) 变成 Θ(1)。固定的调用开销与随输入增长的工作量应分别看待。

12 · 六个常见误区，用反例纠正

原书的小结用简化语言回顾关键主题；这里补充了渐近符号、Python 实现和计量范围的边界。没有把关于其他语言的尾递归优化情况一概照搬到 Python。

13 · 复盘：先自己追踪，再展开答案

以下 10 题是本篇建议练习，不是用户已提出、已完成或已掌握的记录。第 2.6 节会继续安排独立练习，本节先检查是否能把概念连起来。

1. find_first([2, 2], 2) 的位置和比较次数是什么？
2. 最坏比较数为 n，写 O(n²) 是否错误？为什么仍优先写 Θ(n)？
3. n=5 时，固定三次内层、三角循环和翻倍循环分别执行多少次？
4. 把一个 Θ(n) 段与一个 Θ(n²) 段顺序执行，总体怎样增长？
5. 同样创建 n 个长度 n 的列表，为什么峰值可以不同？
6. sum_recursive(3) 到达基本情况时，有几个未结束的求和调用？
7. sum_tail(3) 在 CPython 中为什么不会自动复用一个调用帧？
8. 把 seen 集合放到计时开始前，会对一次性查重的测量产生什么影响？
9. reading.scale(2) 隐式补入哪个实参？原对象是否被复制？
10. 若每个整数都越来越大，“只有几个整数变量”还能代表严格的固定字节吗？

接下来：2.6 练习

本章主线：2.1 效率评估 → 2.2 迭代与递归 → 2.3 时间复杂度 → 2.4 空间复杂度 → 本篇 2.5 小结。下一节为 2.6 练习（待编写），完成后进入 3.1 数据结构分类。

查看 全书覆盖表 与 学习地图。发布与个人复盘分别记录；读过或发布过都不等于已经掌握。

来源、改写说明与验证边界

本篇以 krahets《Hello 算法》2.5 小结为主题依据（2026-10-18 核对）。没有照搬原文段落或图表；重新组织为统一分析流程，加入原创 Python 示例、执行表、边界与复盘答案。与原书相关的改编文字采用 CC BY-NC-SA 4.0，保留署名、来源、非商业和相同方式共享要求；不改变网站其他内容和源码许可。

Python 机制来源：CPython 不实现 Python 函数尾调用优化；实例方法绑定；timeit 的计时范围、重复测量和 GC 行为；集合与可哈希元素。

文中 6 段代码均独立运行并核对输出；另验证查找边界、循环次数、列表槽位、求和输入契约、查重与方法绑定。槽位数量是状态计数，增长表是假设模型；本篇没有把它们冒充 RSS、耗时实测或跨平台性能结论。