理解迭代：for、while 与嵌套循环的复杂度

这一篇在系列中的位置

本篇覆盖知识点 01—12：先解释循环如何推进，再分析执行次数和单次操作成本。原有示例与链接继续保留，新增 range、累加器与复合状态更新的细节。

迭代是过程，循环是实现它的控制结构

迭代（iteration）是重复执行某些步骤的过程或方法。for、while 等循环语句，是实现迭代的控制结构。相同的代码可以被反复执行，每轮处理的数据和程序状态则可以不同。

例如，累加列表中的元素时，每轮都执行“把当前元素加到总和上”，但当前元素与累计结果不断变化。迭代也不要求生成一个数值结果；逐行处理日志、等待任务就绪，都可以采用迭代方式。

“重复直到条件不满足”更贴近 while 的行为，不能直接覆盖所有循环的结束方式。空数据或一开始就不成立的条件可以使循环体执行零次；缺少有效退出路径的循环也可能一直运行。

for 的核心：从迭代器取下一项

Python 的 for item in iterable 先求值获得可迭代对象，再获取其迭代器；每轮取下一项、绑定给 item，然后执行循环体。当迭代器耗尽时，循环正常结束。迭代器用 StopIteration 表示耗尽，这个信号由 for 处理。

可迭代对象提供获取迭代器的能力，例如列表、字符串、range；迭代器保存取值进度并提供下一项。range(3) 是可迭代对象，iter(range(3)) 才是取值用的迭代器。生成器对象本身也是迭代器。

因此，for 不要求先调用 len()，也不要求预先知道执行次数。下面用内存中的文本流模拟逐行读取文件，输出 start、ready；读取真实文件也使用同样的遍历结构，无需先统计行数。

from io import StringIO

log_file = StringIO("start\nready\n")
for line in log_file:
    print(line.rstrip())

追问：先求值、再获取迭代器，分别在做什么

对 for item in numbers，先求值 numbers：查找这个名称，取得它引用的对象；如果写成 for item in get_items()，则先调用函数，取得返回对象。求值可能只是名称查找，不要求创建新数据或进行数学计算。

接着，for 取得该对象的迭代器，概念上相当于 cursor=iter(source)。循环每轮请求下一项，把得到的值绑定给 item，再执行循环体；迭代器耗尽时正常结束。列表提供数据，列表迭代器保存逐项访问的进度。

in 后的表达式在每次开始执行这条 for 时只求值一次。下面 get_items called 只打印一次，随后两轮输出 body: 10 和 body: 20。若 source 本身已是迭代器，iter(source) 按迭代器协议取得其自身，所以“获取”不意味着必定新建一个不同对象。

依据：for 语句求值与绑定顺序 ↗ · 迭代器协议 ↗。

def get_items():
    print("get_items called")
    return [10, 20]

for item in get_items():
    print("body:", item)

知识点 03—04：range 的边界与累加器

range(start, stop, step) 表示按固定步长推进的整数序列，stop 始终不包含在结果中。默认 step=1；正步长时向较大值推进，负步长时向较小值推进，步长不能为零。range(1, 4) 得到 1、2、3，range(3, 0, -1) 得到 3、2、1。方向和边界不配合时，结果为空。

range 对象保存起点、终点和步长，按需计算元素，不是先建立包含所有元素的列表。下面的 list(...) 为了展示结果，才显式把元素收集起来。

求和时，total 是累加器。初始化为 0，因为 0 是加法的单位元：尚未处理任何数字时，总和就是 0。第 i 轮开始前，total 等于此前处理过的数字之和；执行 total += i 后，它又包含了当前数字。这个始终成立的性质叫循环不变量。

乘积累加器通常从 1 开始；最大值不能一律从 0 开始，否则全为负数时会出错。初始化方式取决于要维护的含义。

依据：Python range ↗。不变量是对下面代码的分析。

print(list(range(1, 4)))
print(list(range(3, 0, -1)))
print(list(range(4, 1)))

total = 0
for i in range(1, 4):
    before = total
    total += i
    print(i, before, total)

while 的核心：每轮开始前检查条件

while condition 在每轮执行循环体之前检查条件，包括第一轮。条件的真值为真才进入循环体；为假则正常结束。因此，它可能一次也不执行。Python 检查的是对象的真值，不要求表达式恰好返回布尔对象 True；例如，空列表的真值为假。

条件不是持续监控的。如果循环体中途使条件变假，当前轮剩余语句仍会继续执行，除非遇到 break、return 等控制流变化。下面输出 1、2、3：最后一轮把 i 改成 3 后，仍执行 print(i)；下一次检查才退出。

存在退出条件还不够，状态更新必须能使它在有限步内到达。例如，把下面的 i += 1 去掉，i < 3 就一直成立。

i = 0
while i < 3:
    i += 1
    print(i)

知识点 06—07、11：复合更新决定状态序列

用 while 管理状态时，先写清楚三件事：初始状态是什么、什么状态允许继续、每轮如何生成下一状态。例如 i=1、i <= n 和 i = 2 * (i + 1)。

《Hello 算法》的示例先执行 i += 1，再执行 i *= 2。两步按顺序生效，所以当前值为 1 时，下一值是 4，而不是 3。交换两句就变成 i = 2 * i + 1，序列改为 1、3、7、15、31……。

下面设置 n=50，原顺序访问 1、4、10、22、46，总和为 83；交换顺序访问 1、3、7、15、31，总和为 57。每轮加入总和的是更新前的值；更新后的值留给下一轮条件检查。

从初值开始，经过 k 次更新有 iₖ = 3 × 2ᵏ − 2。要到达输入规模 n 附近，只需要对数量级的更新次数。因此，循环体执行次数为 Θ(log n)，尽管这里只出现了一层循环。这里计算的是次数，整数位数、打印等成本仍需另行分析。

复盘建议：不运行代码，手工推导两种更新顺序的前五项，再用实际输出核对。

def collect_steps(limit, reverse=False):
    i = 1
    values = []
    while i <= limit:
        values.append(i)
        if reverse:
            i *= 2
            i += 1
        else:
            i += 1
            i *= 2
    return values

first = collect_steps(50)
second = collect_steps(50, reverse=True)
print(first, sum(first))
print(second, sum(second))

知识点 08：存在条件与能够结束是两回事

要证明循环可以结束，可以找一个有下界、每轮都严格减少的整数度量。例如遍历 1 到 n 时，剩余元素个数每轮减少 1，不会小于 0。反过来，变量每轮变化，不代表退出状态一定可到达。

例如 i 从 1 开始每轮加 2，始终是奇数。若继续条件写成 i != 10，就永远不会碰到 10；写成 i < 10 则在更新到 11 后结束。下面只运行能结束的版本，输出 1、3、5、7、9，最终 i=11。

continue 也会影响这条证据链：如果跳过了必要更新，同一状态可能一直重复。状态由外部任务决定的轮询，则不能仅靠本地状态证明外部任务一定就绪，应设计超时或取消路径。循环中的一次阻塞调用还可能使外层超时检查无法及时执行。

i = 1
visited = []
while i < 10:
    visited.append(i)
    i += 2
print(visited)
print(i)

break、continue 与循环的退出范围

for 与 while 都支持 break 和 continue。这些语句改变控制流，分析实际执行次数时也要考虑它们。

在 while 中使用 continue 时，要确认没有跳过必要的状态更新，否则可能重复停留在同一个状态。

下面输出 0 0、1 0、2 0。每次 break 结束的是内层循环，外层仍取下一个 i。

for i in range(3):
    for j in range(3):
        print(i, j)
        break

选择循环时，先看谁决定下一轮

“for 更紧凑，while 更灵活”是经验描述。遍历数据时，for 自动管理取下一项，通常更简洁；由状态决定是否继续时，while 通常更直接。“灵活”不代表能完成更多种任务，也不能直接推出运行更快。

修改 Python for 的循环变量，不会直接改变迭代器下一项。需要动态步长时，可以用 while 管理状态，也可以把推进规则封装在生成器中。

继续看具体场景：Python 的 while 与 for：三个循环示例。

复杂度数的是总工作量，不是语法层数

时间复杂度描述工作量怎样随输入规模增长，不等同于某次运行花了多少秒。以下约定 n、m 是输入规模，并采用通常的基本操作成本模型：简单计数、比较与状态更新按 O(1) 计。涉及大整数位数、I/O 或昂贵函数时，要重新评估操作成本。

在每层都完整执行 n 次、最内层每次操作为常数成本这类情况下，两层为 n × n，三层为 n × n × n，k 层对应 O(nk)。这是特定执行结构的结果，不能仅凭缩进层数套用。

内层每轮次数不同，应逐轮累加。例如 0 + 1 + … + (n−1) = n(n−1)/2，仍按平方增长。单次内层工作相同时，可以直接用“外层次数 × 单次内层工作”计算；不同则需要求和。

O(...) 表示渐近上界，不表示恰好执行这么多次。这里给出的无提前退出示例，也具有对应的紧确增长阶；强调上下界同阶时，可写成 Θ(...)。“升维”可以帮助想象多重组合枚举，但不是复杂度分析规则。

三个两层循环：平方、线性与三角形计数

下面三个示例都包含两层循环，但次数分别为 n²、3n、n(n−1)/2。取 n = 10，实际输出 100 30 45。内层固定三次时，多一层嵌套只增加常数倍工作。

n = 10
square = fixed = triangular = 0

for i in range(n):
    for j in range(n):
        square += 1

for i in range(n):
    for j in range(3):
        fixed += 1

for i in range(n):
    for j in range(i):
        triangular += 1

print(square, fixed, triangular)

共享进度：两层嵌套也可以是线性的

下面输出 10。关键是 j = 0 在外层循环之前，只初始化一次。第一轮内层把 j 从 0 推进到 n；之后每轮检查 j < n 都为假。

内层循环体总共执行 n 次，外层及条件检查也是线性次数，因此整体为 O(n)。如果把 j = 0 移到外层循环体内，内层每次重新从零开始，就变成 O(n²)。

分析嵌套循环时，必须看状态是否重置、是否跨轮复用，以及内层是否真的每轮都跑完整遍。

n = 10
j = 0
count = 0

for i in range(n):
    while j < n:
        j += 1
        count += 1

print(count)

倍增推进：两层嵌套可以是 n log n

每次外层循环都把 j 重置为 1，但内层每轮把它翻倍。取 n = 10，进入内层时的 j 依次为 1、2、4、8，共四次；变成 16 后退出。外层十次，因此输出 40。

对 n ≥ 1，最小的轮数 t 满足 2t ≥ n，即 t = ⌈log₂ n⌉。总次数为 n × ⌈log₂ n⌉，整体为 O(n log n)。这里的推导依据是状态推进规则。

n = 10
count = 0

for i in range(n):
    j = 1
    while j < n:
        count += 1
        j *= 2

print(count)

一层循环也能是平方复杂度；时间与空间要分别分析

循环体中的函数调用不一定是常数成本。下面只有一层显式循环，但 sum(values) 每次都遍历整个列表。令列表长度为 n，调用 sum 共 n 次，因此在上述成本模型下整体为 O(n²)。示例返回 18：列表之和为 6，累计三次。

如果找到元素就 break，还要区分输入情况：线性查找的最好情况可能是 O(1)，最坏情况为 O(n)。有提前退出不代表最坏复杂度自动降低。

嵌套层数也不能直接决定空间复杂度。固定深度的循环若只保留少量计数变量，额外空间通常为 O(1)；如果把所有 n² 个组合存入列表，才需要随结果数量增长的 O(n²) 空间。要说明分析的是输入空间、输出空间，还是额外工作空间。

def repeated_sum(values):
    result = 0
    for _ in range(len(values)):
        result += sum(values)
    return result

print(repeated_sum([1, 2, 3]))

知识点 12：字符串示例还要看输出与单次成本

原文的两层循环枚举 n² 个坐标，并把每个坐标转成文字后拼进结果。n² 是循环体次数；字符转换、格式化和追加的成本还要单独计算。不能因为正文只写了一句，就把这句话的代价视为固定常数。

当 n 可以无限增长时，坐标数字的位数也会增长，平均格式化长度涉及 log n；仅输出所有坐标，就需要与生成字符总量相匹配的工作和存储。反复拼接不可变字符串，还可能涉及已有内容的复制；某些实现会优化特定追加形式，实际行为必须结合具体实现核验，不能从语法直接推断复制次数。

因此，本系列用纯计数版本说明 n² 次枚举，用列表保存片段后一次 join 展示另一种输出构造方式。下面 n=2，输出四个坐标；它是输出方式示例，不是一份字符串性能基准。生成完整结果本身所需的空间不会因为改用 join 就消失。

依据：Python 官方：不可变序列拼接与替代方式 ↗。坐标数量和数字长度是对示例的推导。

def coordinates(n):
    pieces = []
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            pieces.append(f"({i}, {j})")
    return ", ".join(pieces)

print(coordinates(2))

可复现验证：数次数，再解释增长关系

把上面计数示例中的 n 分别改成 10 和 100，直接运行，可得到以下结果。这些数字统计的是指定循环体的执行次数，不是耗时。

验证时先确认：输入规模是什么、计数的基本操作是什么、状态在哪里初始化、是否存在提前退出、单次操作成本是否随输入变化。计数结果可以核验示例，但几个输入点本身不能证明渐近复杂度；还需要给出乘积、求和或状态推进的推导。

把原来的表述整理得更准确

迭代（iteration）是重复执行某些步骤的过程或方法，for 和 while 是实现迭代的常见循环结构。在 Python 中，for 通过迭代器逐项获取数据，适合遍历可迭代对象，也可以通过 range(n) 实现固定次数的重复，不要求预先知道元素总数。while 在每轮开始前检查条件，适合由状态或条件决定是否继续的任务。两者都支持提前退出，选择时应以控制机制和可读性为依据。

循环可以嵌套，但时间复杂度必须根据实际操作总次数和单次操作成本分析。在每层都完整执行 n 次、最内层每次操作为常数成本这类情况下，k 层嵌套具有 O(nk) 的时间复杂度。内层次数固定、按倍增推进、复用状态或提前退出时，必须根据实际行为重新计算，不能直接套用“每加一层就增加一次方”。

相关笔记：while 与 for 的实际示例 · 理解递归：从函数调用到逐层返回。

语言机制依据：Python 官方文档：for 语句 ↗ · while 语句 ↗ · 迭代器协议 ↗ · 真值判断 ↗ · break 与 continue ↗。复杂度与计数关系由本文示例推导，读者可以通过改变输入规模自行核验。

本篇复盘：把状态、退出和成本分别讲清楚

以下题目是作者建议的复盘练习，不代表已经完成：

1. 为什么 for 可以遍历长度未知的生成器？谁提供下一项？
2. 为什么把累加器写在循环体内部会丢失此前结果？
3. while 的条件在循环体中途变假，当前轮会立即停止吗？
4. 一个状态更新虽然一直变大，为什么仍可能不能到达预定退出条件？
5. 原文的字符串拼接示例，为什么不能只用 n² 次循环来断言实际运行时间？

返回总索引 · 下一篇 · 在学习地图中复盘

本系列的来源与许可

本篇是《Hello 算法》相关主题的重新组织与补充讲解。署名、修改说明及 CC BY-NC-SA 4.0 许可见 系列来源说明；对应知识点和官方依据均可从索引核验。

这篇笔记在全书中的位置

本篇已经纳入 Hello 算法 Python 全书精讲。保留原来的章节和路径；后续章节的发布进度以全书覆盖表为准。