《Hello 算法》计算复杂度章节习题全解：掌握复杂度分析的三类核心练习与斐波那契迭代实现

2026-09-06 18:23:34作者：霍妲思

本篇指南以《Hello 算法》英文版 "Computational Complexity" 章节配套的 Exercises 练习页为骨架，逐题拆解"概念复习"中的迭代/递归求和时间与空间复杂度、多代码片段复杂度排序、数组反转的空间开销三组问题，并给出"编程练习"中斐波那契数列基于循环的参考实现。文中所有结论均与仓库内 complexity_exercises 多语言源码相互印证，读完你可以独立完成同类复杂度分析题，并理解如何用断言/单元测试验证算法实现。

一、习题总览：这一页练习在章节中的定位

在《Hello 算法》中，计算复杂度章节由迭代与递归、时间复杂度和空间复杂度三篇正文构成。配套的 exercises.md 是章节收口练习，共分为两部分：

概念复习（Concept Review）：三组围绕 n = 4 小规模输入、可"手算推演"的复杂度题，覆盖 迭代与递归的空间复杂度差异、O(log n) / O(n) / O(n²) 排序、原地（in-place）反转的空间开销；
编程练习（Programming Exercises）：一道要求"只用循环、禁用递归"的斐波那契数列题，附三条提示。

正文中的 {func} 引用块在渲染时会直接嵌入对应语言源码文件中的函数，例如 [file]{complexity_exercises}-[class]{}-[func]{sum_iter} 对应 Python 版 sum_iter、C 版 sumIter、C++ 版 sumIter 等。仓库同时提供 C/C++/C#/Dart/Go/Java/JavaScript/Kotlin/Python/Ruby/Rust/Swift/TypeScript 等十余种语言的同名实现，可通过章节源码目录逐语言对照查阅。

二、概念复习一：迭代求和与递归求和的时间/空间复杂度

两个函数都计算 $1 + 2 + \dots + n$ （约定 $n \ge 1$ ）。令 n = 4，按程序真实执行顺序回答问题，并比较两种方式的效率。仓库中的参考实现如下（以 Python 与 C 为例）：

def sum_iter(n: int) -> int:      # 迭代求和
    res = 0
    for i in range(1, n + 1):     # 依次取 1,2,3,4
        res += i
    return res

def sum_recur(n: int) -> int:     # 递归求和
    if n == 1:
        return 1                  # 终止条件
    return n + sum_recur(n - 1)   # 递归调用

int sumIter(int n) {              // C 版迭代实现
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}

int sumRecur(int n) {             // C 版递归实现
    if (n == 1) {
        return 1;
    }
    return n + sumRecur(n - 1);
}

对应源码见 complexity_exercises.py 与 complexity_exercises.c。

Q1：迭代函数在 `n = 4` 时，每轮循环后累加器 `res` 的取值

循环变量 i 依次取 1, 2, 3, 4。每轮结束后 res 分别为 1、3、6、10，因此函数最终返回 10。这里的 res 是单次累加的"状态"，循环体内只有一行 res += i，迭代的执行路径完全确定，可以逐轮写出状态序列——这正是小规模输入便于"按真实执行顺序推演"的意义。

Q2：递归函数在 `n = 4` 时，参数 `n` 的取值顺序与返回值是如何逐层得到的

实参 n 的取值顺序是 4 → 3 → 2 → 1。最深层（n = 1）触达终止条件返回 1；随后逐层回溯：

1 返回后，sum_recur(2) 得到 2 + 1 = 3；
再上一层得到 3 + 3 = 6；
最外层得到 4 + 6 = 10。

关键点在于：在到达最深调用点时，4 个函数调用都尚未结束。系统为每一层未返回的调用保留栈帧（stack frame），这与迭代只需一个累加变量形成本质区别。更系统的"下降 / 上升"两阶段与调用栈机制可参见正文 iteration_and_recursion.md。

Q3：两种方式的复杂度差异

两者执行的操作（循环次数或函数调用层数）都与 $n$ 成正比，因此 时间复杂度同为 $O (n)$ ；
空间复杂度不同：迭代版只使用常数个变量，空间复杂度为 $O (1)$ ；递归版中先前的调用必须等待子调用返回，调用栈上同时最多持有 $n$ 层调用，空间复杂度为 $O (n)$ 。

这里引出一个易错点：分析空间复杂度时，除了代码中显式声明的变量，还必须计入递归调用自身占用的栈帧空间。仓库源码同样印证了结论——递归实现没有额外的容器变量，额外的 $O (n)$ 空间完全来自调用栈本身。

补充说明：虽然教科书中的尾递归在理想情况下可把空间压到 $O (1)$ ，但章节 summary.md 明确指出，大多数主流语言（Java、Python、C++、Go、C# 等）不支持自动尾递归优化，因此实际仍按 $O (n)$ 空间处理。

三、概念复习二：三段代码的时间复杂度排序

题目给出三个接受正整数 $n$ 的代码片段，要求从低到高排序并给出各自的复杂度。仓库 complexity_exercises 源码中与之对应的三个函数为：linear_loop（线性阶）、quadratic_loop（平方阶）与 logarithmic_loop（对数阶）：

def linear_loop(n: int) -> int:        # 片段1：线性阶
    res = 0
    for i in range(n):                 # 恰好执行 n 次
        res += i
    return res

def quadratic_loop(n: int) -> int:     # 片段2：平方阶
    res = 0
    for i in range(n):
        for j in range(i, n):          # 内层执行 n, n-1, ..., 1 次
            res += j
    return res

def logarithmic_loop(n: int) -> int:   # 片段3：对数阶
    while n > 1:
        n //= 2                        # 每轮将 n 减半
    return n

从低到高的正确排序

排序结果为 片段3 的 $O(\log n)$ < 片段1 的 $O (n)$ < 片段2 的 $O (n^{2})$ 。

片段3（ $O(\log n)$ ）：while 每轮把 n 除以 2（向下取整），执行次数约为 $\log_2 n$ 。例如 $n = 4$ 时 4 → 2 → 1 只执行两轮，最终返回 1；
片段1（ $O (n)$ ）：循环体恰好执行 $n$ 次，与 $n$ 线性相关；
片段2（ $O (n^{2})$ ）：内层循环次数为 $n, n-1, \dots, 1$ ，总次数为 $n + (n-1) + \dots + 1 = n(n+1)/2$ ，去掉低阶项与常数后是二次复杂度。

值得注意， $n (n + 1) / 2 = \frac{1}{2} n^{2} + \frac{1}{2} n$ 的首项系数是 $1 / 2$ ，但大 $O$ 记法忽略常数系数，因此仍记作 $O (n^{2})$ ——这是把"精确操作数"转化为"渐近上界"的标准两步（先数操作数、再求渐近上界）的典型示范，参见 time_complexity.md 中的复杂度推导流程与常见复杂度排序（ $O (1)$ 、 $O(\log n)$ 、 $O (n)$ 、 $O(n \log n)$ 、 $O (n^{2})$ 、 $O (2^{n})$ 、 $O (n!)$ ）。

仓库验证：断言式自测

上述三个函数的正确性可由源码内嵌的断言验证（以 Python 版与 C 版为例）：

assert linear_loop(4) == 6                 # 0+1+2+3
assert quadratic_loop(4) == 20             # 内层累加 j
assert logarithmic_loop(4) == logarithmic_loop(5) == 1   # 4→2→1；5→2→1

C 版则在 main() 中使用 assert 完成相同检查，且已被注册进该章 CMakeLists.txt（add_executable(complexity_exercises complexity_exercises.c)）；Go 语言目录下还单独提供了 complexity_exercises_test.go 形式的单元测试（见 Go 版源码同目录）。阅读任意一门语言的实现并运行其测试，即可验证你手算的每个中间值。

四、概念复习三：两种数组反转方式哪个更省空间

题目给定数组 nums，有两种反转方式：

新建一个等长数组 res，按逆序把元素拷贝进 res 后返回；
用两个下标 i、j 从数组两端向中间移动，每步交换 nums[i] 与 nums[j]。

要求分别判断空间复杂度，并指出哪种属于"原地（in-place）"操作。

参考答案要点

方式1：需要一块与输入等长的辅助数组，空间复杂度为 $O (n)$ ；
方式2：只使用两个下标变量，空间复杂度为 $O (1)$ ，属于原地操作。

这道题的考察价值在于两点权衡。其一，原地反转会就地修改输入数组，只有在允许改动输入的前提下才应优先选用；其二，若必须保留原始数组不变，那么方式1 的拷贝开销无法回避——"省空间"与"保留原数据"在此构成一对约束，需要按场景取舍。这呼应了正文对空间复杂度的定义：只关注额外临时空间（临时数据、栈帧空间），且通常不把输入空间计入，详见 space_complexity.md。

顺带一提，这种"双指针向中间收拢"的思路，其操作计数约为 $n / 2$ 次交换、时间复杂度为 $O (n)$ ，在复杂度排序上是典型的线性阶场景，可以和第二题互相印证。

五、编程练习：用循环实现斐波那契数列（禁止递归）

斐波那契数列定义为 $F (0) = 0$ 、 $F (1) = 1$ ，且对 $n \ge 2$ 有 $F (n) = F (n - 1) + F (n - 2)$ 。给定非负整数 n，要求用循环计算并返回 $F (n)$ ，不得使用递归。

原题提示要点

练习题页给出的三条提示即是最小可行实现的全部线索：

单独处理 n 为 0 或 1 的情况：这两项是数列的已知基值，直接返回即可；
只需保留前两项即可推出下一项：无需存储整个序列，天然把空间压在常数级；
更新两个变量时要小心顺序：不能在后一个变量使用旧值之前就把它覆盖掉。

这实际上与仓库中大量动态规划入门题的递推模式一致——例如 climbing_stairs_dp.py 中"只用前两个状态滚动更新"的写法，就是同一思想的体现。

参考实现

仓库的 complexity_exercises 源码中并未包含斐波那契的成品实现（它属于留白式编程题），下面是根据上述三条提示整理的可运行参考解，读者可直接对照自行实现后再查看：

def fibonacci(n: int) -> int:
    """迭代求解斐波那契数列：O(n) 时间，O(1) 空间"""
    if n == 0:
        return 0
    if n == 1:
        return 1
    prev, curr = 0, 1          # 初始为 F(0)、F(1)
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr   # 先求新项，再整体平移
    return curr

# 自测
assert fibonacci(0) == 0
assert fibonacci(1) == 1
assert fibonacci(10) == 55

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; ++i) {
        int next = prev + curr;   // 必须先暂存新值
        prev = curr;
        curr = next;
    }
    return curr;
}

上述两个版本中，Python 的 prev, curr = curr, prev + curr 是"同步赋值"，右侧两个值在写入前均已计算完毕，天然满足提示 3 的防覆盖要求；C 版则显式引入 next 暂存新项，先移位、再更新，逻辑更贴近底层执行顺序。

复杂度与正确性分析：循环从 2 迭代到 n，共约 $n - 1$ 轮，时间复杂度为 $O (n)$ ；全程仅使用两个临时变量，空间复杂度为 $O (1)$ 。相比教科书常见的朴素递归写法——return fib(n-1) + fib(n-2) 会展开成指数级的重复调用、同时叠加 $O (n)$ 的栈深度——本题刻意用"禁止递归"引导读者练习**自底向上（bottom-up）**的迭代思维，恰与正文中对迭代、递归两种范式的讨论相呼应。这道题源自 LeetCode 的经典题目 Fibonacci Number，建议按该题要求先自行编码、再对照本节参考解。

六、延伸阅读与运行自测建议

若想把这组练习题吃透，建议按以下顺序继续阅读当前仓库的相关章节与源码：

理论基础：iteration_and_recursion.md（迭代/递归范式、调用栈、尾递归）、time_complexity.md（复杂度推导两步法）、space_complexity.md（输入/临时/输出空间划分）；
复习纲要与 Q&A：summary.md（常见复杂度排序、尾递归语言支持差异等易混淆点）；
多语言源码对照：章节目录下各语言的 complexity_exercises 文件，以及正文函数所在的 iteration.c / iteration.py、recursion.*、time_complexity.*、space_complexity.*；
运行验证：Python 直接执行 python3 codes/python/chapter_computational_complexity/complexity_exercises.py 即可跑通全部断言；C/C++ 版本已由各章 CMakeLists.txt 注册为可执行目标，配置 CMake 构建后运行 complexity_exercises 目标即可；Go 版本则可用 go test 运行同目录下的 complexity_exercises_test.go。