Hello 算法：计算复杂度章节练习精讲——迭代与递归的空间开销、复杂度排序与斐波那契循环解法

本文围绕《Hello 算法》计算复杂度章节的练习文档 exercises.md 展开，覆盖知识巩固与编程练习两大板块：通过逐步执行迭代/递归求和函数分析时间与空间复杂度、对线性/平方/对数三段代码按复杂度排序、比较两种数组反转做法的空间开销，并给出斐波那契数列的循环实现思路。读完后你将掌握"按执行过程推导 Big-O"的完整分析方法，并能结合仓库中多语言可运行的源码（Python、C、C++、Go、Java 等 14 种语言版本）动手验证每个结论。

练习总览与代码出处

本章练习分为两部分：知识巩固（3 道分析题）与编程练习（1 道斐波那契实现题）。知识巩固题所引用的代码片段均来自仓库中同名多语言文件 complexity_exercises，例如 Python 版本 complexity_exercises.py、C 版本 complexity_exercises.c、Rust 版本 complexity_exercises.rs。每个版本文件尾部都带有 assert 断言，直接运行即可验证答案；Go 版本还配有独立测试文件 complexity_exercises_test.go。以下以 Python 源码为准逐题讲解。

知识巩固一：迭代与递归的时间和空间

题目给出两段都计算 $1 + 2 + \dots + n$（$n \ge 1$）的代码，要求把 n 设为 4，按程序实际执行顺序比较两种写法的效率。对应仓库源码：

def sum_iter(n: int) -> int:
    """迭代求和"""
    res = 0
    for i in range(1, n + 1):
        res += i
    return res

def sum_recur(n: int) -> int:
    """递归求和"""
    if n == 1:
        return 1
    return n + sum_recur(n - 1)

（见 complexity_exercises.py，C 语言中对应 sumIter/sumRecur，见 complexity_exercises.c。）

原题给出三个递进小问：

1. 输入 n = 4 执行迭代函数时，每轮循环结束后累加变量 res 的值分别是多少？
2. 输入 n = 4 执行递归函数时，参数 n 会依次取哪些值？从最深的一层开始返回时，结果怎样得到？
3. 两种写法的时间复杂度和空间复杂度分别是多少？结合前两问的执行过程说明理由。

参考答案与逐层分析

第 1 问：循环变量 i 依次为 1、2、3、4，每轮结束后 res 依次变为 1、3、6、10，因此迭代函数返回 10。

第 2 问：参数 n 依次为 4 → 3 → 2 → 1。最深一层返回 1，随后各层依次得到 2 + 1 = 3、3 + 3 = 6、4 + 6 = 10。关键在于：在最深处，4 次函数调用都尚未结束——每一层的表达式 n + sum_recur(n - 1) 中，sum_recur(n - 1) 尚未求值，当前调用帧必须保留在栈上等待。

第 3 问：

• 时间复杂度：两段代码都进行了与 $n$ 成正比的循环或调用（迭代版循环 $n$ 次，递归版调用 $n$ 次），因此时间复杂度均为 $O(n)$。
• 空间复杂度：迭代版只使用常数个变量（res 与 i），为 $O(1)$；递归版在到达终止条件前，前面的函数调用都要等待返回结果，调用栈中最多同时保存 $n$ 次调用，空间复杂度为 $O(n)$。

这里体现了空间复杂度分析的一条重要原则，原文档特别强调：分析空间复杂度时，除代码中显式声明的变量外，还要考虑递归调用占用的栈空间。这一结论与本章 空间复杂度 一节中"递归调用会引入栈空间"的论述一致——从源码结构看，sum_recur 与 sum_iter 函数体几乎等价（同样只有常数个局部变量），但递归版因调用链而产生了 $O(n)$ 的隐藏开销，这正是"空间复杂度不能只看声明变量"的典型反例。

知识巩固二：三段代码的时间复杂度排序

题目给出三个输入均为正整数 $n$ 的代码片段，要求按时间复杂度从低到高排序并写出各自复杂度。仓库源码：

def linear_loop(n: int) -> int:
    """线性阶循环"""
    res = 0
    for i in range(n):
        res += i
    return res

def quadratic_loop(n: int) -> int:
    """平方阶循环"""
    res = 0
    for i in range(n):
        for j in range(i, n):
            res += j
    return res

def logarithmic_loop(n: int) -> int:
    """对数阶循环"""
    while n > 1:
        n //= 2
    return n

（见 complexity_exercises.py，函数命名直接标明了复杂度类别：线性阶、平方阶、对数阶。）

参考答案与推导

从低到高排序为：片段三 $O(\log n)$ → 片段一 $O(n)$ → 片段二 $O(n^2)$。

• 片段三（对数阶）：while n > 1: n //= 2 每轮把 $n$ 缩小为原来的一半，约循环 $\log_2 n$ 次。可以推断出当 $n \le 2$ 时循环体一次都不执行，直接返回原值。
• 片段一（线性阶）：单层循环恰好执行 $n$ 次，即 $O(n)$。
• 片段二（平方阶）：外层第 $i$ 轮的内层循环从 j = i 执行到 n - 1，共 $n - i$ 次，因此内层循环次数依次为 $n, n-1, \dots, 1$，总次数为 $n(n+1)/2 \in O(n^2)$。

用断言验证：仓库各语言版本均内置了针对这些片段的数值断言，例如 Python 版 complexity_exercises.py 中：

assert linear_loop(4) == 6        # 0+1+2+3
assert quadratic_loop(4) == 20    # 0..3 + 1..3 + 2..3 + 3..3
assert logarithmic_loop(4) == logarithmic_loop(5) == 1

可以直接 python codes/python/chapter_computational_complexity/complexity_exercises.py 运行验证；Go 版则通过 go test 运行 complexity_exercises_test.go 中的 TestComplexityExercises，检查 linearLoop(4) == 6、quadraticLoop(4) == 20、logarithmicLoop(4) == logarithmicLoop(5) == 1 等断言。注意 logarithmic_loop(4) 与 logarithmic_loop(5) 返回相同结果，这正呼应了对数阶的"缩放不变性"：$n$ 取 4 或 5 时循环次数分别为 $\lceil \log_2 4\rceil = 2$ 与 $\lceil \log_2 5\rceil = 3$ 次缩放，最终都收敛到 1。

知识巩固三：哪种数组反转更节省空间

题目：要将数组 nums 中的元素全部反转，有两种做法——

1. 新建一个等长数组 res，倒序复制后返回；
2. 用两个索引 i 和 j 分别从首、尾向中间移动，逐对交换 nums[i] 与 nums[j]。

参考答案

• 做法 1：需要与输入等长的辅助数组，空间复杂度 $O(n)$。
• 做法 2：只使用两个索引变量，空间复杂度 $O(1)$，属于原地（in-place）操作。

原文档补充了一个重要的工程取舍提示：原地反转会修改输入数组，仅在允许修改输入时才应优先选用；若需保留原数组，做法 1 的复制开销不可避免。判断"是否原地"的标准是：辅助空间是否与输入规模成正比——做法 1 的辅助数组随 $n$ 线性增长，做法 2 的 i、j 两个变量与 $n$ 无关，因此只有做法 2 是原地算法。

编程练习：斐波那契数（循环解法）

题目给出斐波那契数列定义：$F(0)=0$、$F(1)=1$，且当 $n \ge 2$ 时 $F(n) = F(n-1) + F(n-2)$。要求给定非负整数 n，使用循环（不使用递归）计算并返回 $F(n)$。

原题解题提示

1. 先单独处理 n 为 0 和 1 的情况；
2. 计算下一项时只需要前两项，无须保存整个数列；
3. 更新两个变量时，注意不要过早覆盖仍会用到的旧值。

结合这三条提示，一个符合要求的循环解法如下：

def fib(n: int) -> int:
    """斐波那契数：循环解法，时间 O(n)，空间 O(1)"""
    if n < 2:
        return n            # 提示 1：单独处理 0 和 1
    prev, cur = 0, 1        # 提示 2：只保存前两项
    for _ in range(2, n + 1):
        prev, cur = cur, prev + cur   # 提示 3：同时更新，避免覆盖旧值
    return cur

这段代码恰好是本节练习知识点的综合运用：

• 时间复杂度 $O(n)$：单次循环 $n - 1$ 轮，与练习二中 linear_loop 同属线性阶；
• 空间复杂度 $O(1)$：仅用 prev、cur 两个滚动变量，与迭代求和 sum_iter 一样是常数空间，也避免了递归斐波那契（调用树呈指数分叉）的开销；
• 提示 3 的陷阱：若写成 prev = cur; cur = prev + cur，第一次赋值后 prev 的旧值已丢失，cur 的计算就会出错。Python 的 prev, cur = cur, prev + cur 是右值整体求值后同时赋值的写法；在其他语言中则需引入临时变量，如 C 语言：

int tmp = cur;
cur = prev + cur;
prev = tmp;

该题目即 LeetCode 509 "Fibonacci Number"，原文档附有题目链接与解析链接供延伸阅读。需要说明的是，斐波那契的循环解法也构成 动态规划章节 中"记忆化/滚动数组"思想的入门铺垫——提示 2"无须保存整个数列"正是后续滚动数组优化 DP 表格的雏形。

练习文件的多语言分布与运行方式

从仓库结构看，complexity_exercises 的练习代码在 14 种语言下各有一份对应实现，位于 codes/<语言>/chapter_computational_complexity/ 目录，例如：

• Python：文件尾用 assert 自测，直接运行脚本；
• C：main 中用 <assert.h> 断言，编译后运行；
• Rust：main 中用 assert_eq! 断言，cargo run 执行；
• Go：唯一配有独立 _test.go 的练习文件，用 go test 执行；
• Java、C++、C#、JavaScript、TypeScript、Kotlin、Ruby、Swift、Dart 等版本命名风格各自遵循语言惯例（如 Java 版 linearLoop/quadraticLoop，C# 版 Algorithm/SumIter），断言逻辑一致。

各语言断言的数值基准完全相同：sum_iter(4) == sum_recur(4) == 10、linear_loop(4) == 6、quadratic_loop(4) == 20、logarithmic_loop(4) == logarithmic_loop(5) == 1，可以直接作为你复算各题答案时的对照标准。

小结

本章练习的核心训练目标是三条：

1. 会"走格子"：像调试器一样逐轮跟踪 res 与调用栈的变化（n = 4 时 res 依次 1 → 3 → 6 → 10；递归参数 4 → 3 → 2 → 1），从执行过程而非背诵结论出发推导 Big-O；
2. 分清时间与空间：迭代版 $O(n)$ 时间 / $O(1)$ 空间，递归版 $O(n)$ 时间 / $O(n)$ 栈空间——时间相同而空间不同，根源在于"调用帧等待返回"这一隐式开销；
3. 会做工程取舍：复杂度排序（对数 < 线性 < 平方）、原地与非原地反转的适用前提、滚动变量实现斐波那契时的覆盖陷阱，都是写代码前必须先想清楚的问题。

完成本节练习后，建议继续阅读 时间复杂度、空间复杂度 与 迭代和递归，将练习中反复出现的 $O(\log n)$、$O(n)$、$O(n^2)$ 分类体系与章节正文的系统化推导相互印证。