2.6 复杂度分析练习：从执行轨迹到反转与斐波那契

01 · 先解题，再用运行证据检查推理

分析约定：n 是数值参数或列表长度；默认按教材的单位成本模型计算整数操作，空间默认排除调用者已提供的输入，但明确计入新建结果和递归状态。后文单独讨论 Python 大整数的位成本。所有打印仅用于观察，不将包含终端 I/O 的程序当作性能基准。

练习发布、你是否阅读、你是否完成复盘是三件事。本文没有替你设置已讨论、已掌握或已复盘记录。

02 · 每道题都交出四种证据

1. 契约：允许什么输入？返回什么？是否允许修改原对象？
2. 轨迹：用足够小的输入，列出每一步的变量或尚未结束的调用。
3. 成本：指定计数操作，先算真实次数，再归纳增长阶；空间找同一时刻的峰值。
4. 反例：空输入、基本情况、重复值、奇偶长度、2 的幂附近和错误类型，哪些会推翻原先结论？

“程序返回正确值”不能单独证明复杂度；“次数符合公式”也不能代替结果正确性。下面分别检查这两件事。

03 · 求和：同一个答案，两种等待方式

先试：输入 n=4，不执行程序，写出循环每步结束后的 total，以及递归的进入和返回顺序。这里保留原题 n≥1 的契约；检查器主动拒绝 0、负数和非 int，包括布尔值。类型注解本身不会完成这样的运行时检查。

递归先进入 4、3、2、1，再完成 1、2、3、4。到达 1 时，四个 visit 调用都未结束；外层 sum_recur 和固定的辅助调用只增加常数开销。迭代不会同时保留四轮的局部执行状态。

参考结论：循环做 n 次累加；递归有 n 次 visit，非基本情况加法 n−1 次，二者时间均为 Θ(n)。迭代辅助空间 Θ(1)，递归 Θ(n)；打印关闭时结论不变。检查器只运行一次，不影响增长阶。不要把两种程序的加法精确次数说成完全相等。

step 1 1
step 2 3
step 3 6
step 4 10
iter = 10
enter 4
enter 3
enter 2
enter 1
return 1 1
return 2 3
return 3 6
return 4 10
recur = 10

def require_positive(n):
    if type(n) is not int:
        raise TypeError("n must be an integer")
    if n < 1:
        raise ValueError("n must be positive")

def sum_iter(n, trace=False):
    require_positive(n)
    total = 0
    for value in range(1, n + 1):
        total += value
        if trace:
            print("step", value, total)
    return total

def sum_recur(n, trace=False):
    require_positive(n)
    def visit(value):
        if trace:
            print("enter", value)
        result = 1 if value == 1 else value + visit(value - 1)
        if trace:
            print("return", value, result)
        return result
    return visit(n)

print("iter =", sum_iter(4, trace=True))
print("recur =", sum_recur(4, trace=True))

04 · 为什么基本情况必须与输入域一致

若只写 if n == 1 却放入 n=0，递归参数会沿 0、−1、−2……继续减小，永远碰不到 1，最终通常以 RecursionError 结束。可选择明确拒绝 0，也可重新定义“0 项和为 0”，并把基本情况改为 0；两者都是合理契约，不能只改测试预期而不改实现。

数学上递归定义终止，不等于 Python 允许任意深度。解释器有递归深度限制，具体可用深度还受已有调用链等因素影响；不应把某台机器的“最大 n”写成通用常量。本节只用小输入追踪和验证，不提高递归上限。

回看 活跃调用帧：空间统计的是还在等待的状态，不是整个运行过程中调用次数的历史总和。

05 · 三种循环：数操作，不看缩进猜答案

以下是原题循环结构的计数版，返回次数而不是求和结果；只在 n 为非负整数的范围内使用。题目要求把线性、三角形和减半循环按增长速度排序。

从低到高：减半 → 线性 → 三角形。原书写 O 上界，这里补充 Θ 表示紧确界；不意味着原书的 O 写法错误。

最易混淆的是端点：本题内层 range(i, n) 有 n−i 次，包含 i 对应的位置；2.5 中 range(i) 的累计次数是 n(n−1)/2。二者都为平方阶，但 n=4 时分别为 10 和 6。精确次数不同，渐近阶可以相同。

减半经过 k 轮后状态为 ⌊n/2ᵏ⌋，直到不大于 1。n=7 两轮，n=8 三轮，n=9 仍三轮；不要套用“翻倍直到 ≥n”时的上取整公式。n=0 单独定义执行 0 轮，不对 log₂0 求值。

0 0 0 0
1 1 1 0
4 4 10 2
7 7 28 2
8 8 36 3
9 9 45 3

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

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

def count_halves(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

for n in (0, 1, 4, 7, 8, 9):
    print(n, count_linear(n), count_triangle(n), count_halves(n))

06 · 反转：先问是否允许改变输入

先试：想把 [10,20,30,40,50] 反过来，是否要求原列表保持不变？如果另一个变量也引用它，那个变量会看到什么？两个函数都面向普通 Python list，不能直接推广到任意序列或自定义容器。

双索引在 0 与 4 交换后，继续 1 与 3，最后两端都到 2，循环停止；交换次数为 ⌊n/2⌋。空列表初始 right=−1，条件直接不成立；单元素也不交换。循环不变量是：两端已处理位置已经处于最终位置，中间尚未处理区间逐步缩短。

复制版只建立新的外层列表，不递归复制内部对象。对嵌套列表，新结果和输入仍指向同一批内部列表。因此“返回新列表”不等于“之后任何修改都互不影响”。原地版通过原引用修改对象，alias 也会看到反转。

copy: [50, 40, 30, 20, 10] input: [10, 20, 30, 40, 50]
same outer: False
in place: [50, 40, 30, 20, 10] alias: [50, 40, 30, 20, 10] return: None
shallow: [[1], [2, 9]] [[2, 9], [1]]

def reverse_copy(values):
    return [values[i] for i in range(len(values) - 1, -1, -1)]

def reverse_in_place(values):
    left, right = 0, len(values) - 1
    while left < right:
        values[left], values[right] = values[right], values[left]
        left += 1
        right -= 1

values = [10, 20, 30, 40, 50]
alias = values
copied = reverse_copy(values)
print("copy:", copied, "input:", values)
print("same outer:", copied is values)
result = reverse_in_place(values)
print("in place:", values, "alias:", alias, "return:", result)
nested = [[1], [2]]
reversed_nested = reverse_copy(nested)
reversed_nested[0].append(9)
print("shallow:", nested, reversed_nested)

07 · 原地、惰性与输出空间不能混在一起

• values[::-1] 产生新的列表；短写法不会自动消除线性存储。
• values.reverse() 原地反转，返回 None；写 values = values.reverse() 会把变量重新绑定到 None，原对象仍已被修改。
• reversed(values) 对普通列表提供反向迭代器，不会立即生成完整结果；后续 list(reversed(values)) 仍需要新列表的线性空间。若底层列表会变化，不应把迭代器当作独立快照。
• 若题目特意排除返回结果，复制反转的输出空间仍为 Θ(n)，输出之外的工作状态可为 Θ(1)。这只是统计边界变化，实际分配不会因此消失。

工程选择取决于契约：需要保留原顺序、多个使用者共享输入或对外接口承诺不修改时，复制可能更合适；只有允许改变原对象时，原地优势才有意义。

08 · 循环求斐波那契：把相邻两项作为状态

定义 F(0)=0，F(1)=1，后续一项等于前两项相加。原书要求不用递归。本实现用一条统一循环覆盖 0 和 1，不必另写两次早返回。

关键不变量：完成 k 次循环后，previous=F(k)，current=F(k+1)。初始 k=0 成立；下一轮用旧 current 和旧 previous+current，恰好得到 F(k+1)、F(k+2)，所以继续成立。循环 n 次后返回 previous，就是 F(n)。这是对全部合法 n 的推理，测试只是补充证据。

注意变量表示的含义，而不要背 a、b 的名称。另一种写法在 n−1 轮后返回 current 也可能正确，但初始化、循环次数和返回变量必须一起匹配。n=0 能迅速暴露错误的偏移。

在单位成本模型下做 n 次更新，时间 Θ(n)，只保留固定数量的整数状态，辅助空间 Θ(1)。函数拒绝负数与错误类型，不依赖 Python 恰好允许 range(True) 来默默接受布尔输入。

0 0
1 1
2 1
3 2
4 3
8 21
10 55

def fibonacci(n):
    if type(n) is not int:
        raise TypeError("n must be an integer")
    if n < 0:
        raise ValueError("n must be non-negative")
    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current
    return previous

for n in (0, 1, 2, 3, 4, 8, 10):
    print(n, fibonacci(n))

09 · 一个会通过部分样例的错误：过早覆盖旧值

Python 先求赋值号右侧表达式，再按目标绑定。previous, current = current, previous + current 的右侧使用更新之前的两个值，然后才写回左侧；这不是多线程意义上的原子性保证。

拆成两行却不保存旧 previous，第二行会读到已更新的 previous。旧状态 (1,2) 本应变为 (2,3)，错误版变成 (2,4)。从初始 (0,1) 开始，错误结果可能碰巧通过 n=0、1 等样例；所以只看一两个“漂亮数字”不够。

若不想用并行赋值，可以先写 next_value = previous + current，再依次赋 previous = current 和 current = next_value。临时变量增加固定数量状态，不改变辅助空间的增长阶。下面的 broken_fibonacci 是故意展示的反例，仅用于非负整数演示，不是可复用的求解器。

tuple update: 2 3
sequential: 2 4
broken F(3), F(4): 4 8

def broken_fibonacci(n):
    previous, current = 0, 1
    for _ in range(n):
        previous = current
        current = previous + current
    return previous

previous, current = 1, 2
previous, current = current, previous + current
print("tuple update:", previous, current)
previous, current = 1, 2
previous = current
current = previous + current
print("sequential:", previous, current)
print("broken F(3), F(4):", broken_fibonacci(3), broken_fibonacci(4))

10 · 为什么“递归树很大”不等于“栈同样大”

以下仅用于小规模非负整数观察：同时统计结果、visit 总调用数和 visit 活跃深度。没有保存整个调用树，也不计外层包装器的固定层数。

朴素递归满足 C(0)=C(1)=1，C(n)=1+C(n−1)+C(n−2)，可推得 C(n)=2F(n+1)−1。F(5)=5，但需要 15 次 visit；F(10)=55，需要 177 次 visit。许多相同参数被重复计算，所以总工作指数增长。

同一时刻只沿正在求值的一条调用链活动。左分支计算完成后才进入右分支，不会把所有 177 个 visit 都压在栈里。n≥1 时这里统计的最大深度为 n，n=0 时为 1。因此在单位成本模型下，朴素版时间 Θ(φⁿ)，其中 φ=(1+√5)/2，通常也用较松的 O(2ⁿ) 上界；空间 Θ(n)。循环版只保留相邻两项，避免重复计算，也避免递归深度限制。

本节并不要求掌握动态规划；只要能从“哪些子结果被反复求出”解释为什么循环改写更省工作。已有的 重复子问题节点可用于后续延伸。

0 (0, 1, 1)
1 (1, 1, 1)
2 (1, 3, 2)
5 (5, 15, 5)
10 (55, 177, 10)

def recursive_stats(n):
    calls = 0
    peak_depth = 0
    def visit(k, depth):
        nonlocal calls, peak_depth
        calls += 1
        peak_depth = max(peak_depth, depth)
        if k < 2:
            return k
        return visit(k - 1, depth + 1) + visit(k - 2, depth + 1)
    value = visit(n, 1)
    return value, calls, peak_depth

for n in (0, 1, 2, 5, 10):
    print(n, recursive_stats(n))

11 · Python 补充：两个整数变量不等于固定字节数

教材分析把整数加法和整数状态视为单位成本，便于先比较算法结构。Python int 是任意精度整数，F(n) 的二进制位数随 n 线性增长；即使只有两个变量，真实整数对象也会增长。

若采用逐位加法的成本模型，第 k 步参与运算的整数有 Θ(k) 位，n 步合计 Θ(1+2+…+n)=Θ(n²) 位操作；循环状态占 Θ(n) 位。这个推导说明了成本模型改变会改变严格结论，不是声称某台机器的运行时间已经实测为平方曲线。

保存 F(0)…F(n) 全序列时，单位大小模型下需要 Θ(n) 个值，按整数位数累计则需 Θ(n²) 位；循环版仍有明显空间优势。若任务只要 F(n)，不必保存所有旧结果。n 的数值大小也不同于输入 n 的编码长度：用二进制输入时只有约 log₂n 位，不能把两种“规模”混用。

12 · 怎样自己验证，而不让一次输出替代证明

• 求和：对 1…100 分别与 Python sum(range(1,n+1)) 比较，再核对 0、负数、浮点、字符串、None 和布尔输入的拒绝行为。
• 循环：核对 n=0…128 的次数，三角形与组合数 C(n+1,2) 比较，减半与二进制位长减一比较；包含 7/8/9、15/16/17 等边界。
• 反转：穷举长度 0…6、元素取 0/1/2 的 1,093 组列表；检查内容、复制版不改输入、原地版返回 None、反转两次还原，以及嵌套对象共享。
• 斐波那契：对 0…200 用独立组合恒等式核对结果，不只用另一份同样的循环；对 0…15 的朴素版核对调用数公式和深度。故意错误版必须在反例上与正确答案不同。

这些是确定性程序，重复同一输入不会增加多少逻辑覆盖。更有价值的是独立预言、边界和不变量；本篇没有采用耗时阈值，也没有把计数实验描述成内存或耗时实测。

13 · 十道复盘题与可展开参考答案

这是作者建议的自测，不代表你已作答或复盘。先遮住答案说明依据，再运行对应示例检查。

14 · 完成本章后，进入数据结构分类

回到 全书目录与覆盖表，或用 学习地图沿调用栈、工作计数与状态更新复盘。本章小结和练习均纳入发布序列。下一节由同一选节器确定为 3.1 数据结构分类。

15 · 来源、改动说明与许可

主题与题目范围依据 krahets《Hello 算法》2.6 练习（2026-10-19 阅读核对）。本篇不是原书题面或答案的逐字转载：重新编写说明与 Python 实验，加入输入契约、调用/次数统计、循环不变量、共享对象反例、独立测试与位成本讨论。与原书相关的改编文字沿用 CC BY-NC-SA 4.0，保留作者署名、来源、非商业与相同方式共享要求；不改变站点其他内容与源码的许可。

Python 官方机制参考：赋值右侧求值与名称绑定、列表方法、原地反转和浅复制、解释器递归限制、任意精度整数。公式推导、状态表和测试设计为本篇补充。

文中六段代码分别独立执行并核对标准输出；测试读取文章中真正展示的代码，核对结果、次数、变更副作用和边界。代码验证不等于桌面或移动端浏览器视觉验收，发布结果另以实际部署状态确认。