1.2 常见复杂度分析

读完复杂度是什么后，再用约 30 分钟把循环、分支、多个输入和额外空间逐项算出来。目标不是看缩进猜标签，而是先写操作次数表达式，再给出带假设的复杂度结论。

从“看起来像”改成“算出来”

输入是什么，规模变量分别代表什么？
要统计哪一种基本操作？
每个代码块执行多少次？
顺序块相加，嵌套范围求和或相乘后，表达式是什么？
分析的是最好、最坏、平均、期望，还是摊还成本？
使用了多少输入、输出和辅助空间？

沿着这六步走，复杂度不是猜出来的标签，而是一段可以复核的推导。

顺序执行：先相加

python

def summarize(left, right):
    left_total = 0
    for value in left:
        left_total += value

    right_total = 0
    for value in right:
        right_total += value

    return left_total, right_total

令 n = len(left)、m = len(right)。两个循环先后执行，操作数近似为 n + m，所以时间是 Θ(n + m)，不是 Θ(nm)。

若已知 m = O(n)，例如 m 等于 n、固定为常数或不超过 n，就可化简为 Θ(n)。没有这类约束时应保留两者。保留独立变量能让调用者看见真正的扩展方向。

同一个输入上的两个顺序循环可以合并主导项：

text

3n + 2n + 10 = 5n + 10 = Θ(n)

这里的最后一个等号是在归类增长阶，不是在说实际工作量只剩 n 步。

嵌套执行：先看范围

两个完整、独立的范围

python

def matches(left, right):
    result = []
    for first in left:
        for second in right:
            if first == second:
                result.append((first, second))
    return result

外层 n 次，每次都跑完整的 m 次内层循环，因此比较次数是 nm，时间为 Θ(nm)。若结果共有 k 对，创建元组和追加带来 Θ(k) 工作及输出空间；返回列表引用本身不复制这些结果。这里 k ≤ nm，Θ(nm) 的简式假定 n、m 均非零；m 为 0 时，外层仍需走过 n 次。

依赖外层位置的范围

python

def unordered_pairs(values):
    result = []
    for left in range(len(values)):
        for right in range(left + 1, len(values)):
            result.append((values[left], values[right]))
    return result

内层不是每次都执行 n 次。准确的迭代数是：

text

(n - 1) + (n - 2) + ... + 1 + 0
= n(n - 1) / 2
= Θ(n²)

最终增长阶仍是平方，但推导理由不是“看见两层循环”。这个版本产生 n(n - 1)/2 个结果，因此输出空间也是 Θ(n²)。

嵌套不一定相乘到平方

python

def shrinking_work(n):
    steps = 0
    remaining = n
    while remaining > 1:
        for _ in range(10):
            steps += 1
        remaining //= 2
    return steps

固定十次工作的成本是常数，每轮又把问题减半。总步骤约为 10 log₂ n，所以是 Θ(log n)。

每轮减半：为什么是对数

二分查找每轮只保留一半区间。经过 k 轮后，剩余规模约为 n / 2^k。当它降到 1 时：

text

n / 2^k ≤ 1
2^k ≥ n
k ≥ log₂ n

这是最坏情况的 Θ(log n) 探测次数；若第一次中点就命中，最好情况为 Θ(1)。二分查找的前提是数据已按所用比较规则排序；如果为了查找一次而先排序，还要把排序成本计入整个任务。

分支：先注明分析哪一种情况

python

def contains(values, target):
    for value in values:
        if value == target:
            return True
    return False

情况	输入特征	比较次数	紧界
最好	第一个元素命中	1	`Θ(1)`
最坏	最后命中或不存在	`n`	`Θ(n)`
平均	取决于目标位置与缺失概率	需要分布	不能凭空断言

条件语句本身不会自动让复杂度变成平均值。最坏成本取可到达分支中的最大值；平均或期望成本必须说明概率来自哪里。

四类模式放进一个可运行实验

下面程序使用 Python 3.9+，统计模型操作并用断言核对结果。二分部分数的是中点探测，每轮可执行一次相等比较和一次大小比较。频率表在通常哈希假设下期望构建时间为线性，但哈希表结论依赖运行时的哈希与扩容行为；这里验证的是返回内容和访问次数模型，不是给所有输入承诺固定耗时。

python

# analysis_demo.py

def linear_steps(n: int) -> int:
    steps = 0
    for _ in range(n):
        steps += 1
    return steps

def binary_search_probes(values: list[int], target: int) -> int:
    left = 0
    right = len(values) - 1
    probes = 0

    while left <= right:
        middle = (left + right) // 2
        probes += 1
        if values[middle] == target:
            return probes
        if values[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return probes

def triangular_steps(n: int) -> int:
    steps = 0
    for left in range(n):
        for _ in range(left + 1, n):
            steps += 1
    return steps

def frequency_table(values: list[int]) -> dict[int, int]:
    frequencies: dict[int, int] = {}
    for value in values:
        frequencies[value] = frequencies.get(value, 0) + 1
    return frequencies

def main() -> None:
    linear = linear_steps(8)
    binary = binary_search_probes(list(range(8)), 8)
    triangular = triangular_steps(8)
    frequencies = frequency_table([3, 1, 3, 2, 1, 4, 5, 5])

    assert linear == 8
    assert binary == 4
    assert triangular == 28
    assert frequencies == {3: 2, 1: 2, 2: 1, 4: 1, 5: 2}

    print(f"线性步骤：{linear}")
    print(f"二分探测：{binary}")
    print(f"三角循环步骤：{triangular}")
    print(f"频率表键数：{len(frequencies)}")
    print("分析检查通过")

if __name__ == "__main__":
    main()

运行：

bash

python3 analysis_demo.py

输出：

text

线性步骤：8
二分探测：4
三角循环步骤：28
频率表键数：5
分析检查通过

逐项核对：

线性循环完整走过 8 个位置。
在 [0, 1, ..., 7] 中查找不存在且更大的 8，依次探测中点值 3、5、6、7，共 4 轮；本例实际执行 8 次相等或大小比较。
无序元素对共有 8 × 7 / 2 = 28 对。
八个输入值形成五个不同键；字典本身占 Θ(u) 空间，其中 u 是不同值的数量，且 u ≤ n。

空间复杂度：先说你在计哪一种空间

名称	包含什么	例子
输入空间	调用者交给算法的数据	传入的 `values`
输出空间	必须返回或写出的结果	`unordered_pairs` 的结果列表
辅助空间	算法运行时额外申请的空间	频率表、临时数组、递归栈

工程和面试里说“空间复杂度”时，常指辅助空间，但并非统一约定。最稳妥的写法是：

text

输入空间 Θ(n)，输出空间 Θ(k)，辅助空间 Θ(u)

原地更新不等于完全不占空间

python

def double_in_place(values):
    for index in range(len(values)):
        values[index] *= 2

在每个数值运算可视为常数成本的模型下，若不计输入容器，这个函数使用 Θ(1) 辅助空间。Python 任意精度整数越长，乘法结果及临时对象就越大，需要额外计入位数。循环变量和少量标量仍占空间，只是不会随 n 增长。

递归栈必须计入

python

def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 2:
        return 1
    return n * factorial(n - 1)

这里 n 是非负整数，0! 和 1! 都返回 1，负数被拒绝。在把乘法视为一步的模型下，递归调用数和栈深度都是 Θ(n)。实际 Python 大整数乘法成本随位数增长，n! 本身也需要 Θ(n log n) 位；较大 n 还会碰到递归深度限制。它没有显式创建列表，不代表空间为常数。

平均、期望和摊还不是同一个词

概念	需要概率吗	回答的问题
平均情况	需要输入分布	输入按某种分布出现时，平均成本多少？
期望成本	需要算法随机性和/或输入分布	随机选择等因素下，期望成本多少？
摊还成本	不需要	一整串操作的总成本，平均分到每次是多少？

动态数组追加是典型的摊还分析。大多数追加只写一个位置，某次容量不足时却要申请更大数组并复制已有元素，单次最坏成本可达 Θ(n)。从空数组开始且容量按几何比例增长，一串 n 次追加的总复制量仍是 Θ(n)，于是每次追加的摊还成本是 Θ(1)。这不是说每一次都花常数时间，也不是对随机输入取平均。

常见库操作要附上条件

哈希表

哈希表查找常被写成期望 O(1)，通常依赖以下条件：

哈希函数把常见键分布得足够均匀；
负载因子受到控制，扩容策略合理；
键的哈希与相等比较成本可视为常数；
输入不是专门制造大量冲突的对抗数据。

最坏保证取决于具体实现，不能把“哈希表永远是 O(1)”写进通用结论。

排序

归并排序的时间是 Θ(n log n)，通常需要 Θ(n) 辅助空间。
快速排序在合适的枢轴假设下，平均或期望时间为 Θ(n log n)；持续出现极不平衡划分时，最坏时间为 Θ(n²)。
语言内置排序可能使用混合算法。分析真实程序时，应查对应版本的官方合同，不能只凭函数名猜实现。

复制与切片

Python 内置 list 的切片会创建新的浅拷贝列表，复制长度为 k 的切片需要 Θ(k) 时间和空间。C++ 容器按值传递、Java 的某些复制 API、字符串拼接和大整数运算也可能把隐藏成本带进循环体。分析时要展开你实际调用的 API。

实战：最高频元素

python

def most_common(values):
    if not values:
        return None

    counts = {}
    for value in values:
        counts[value] = counts.get(value, 0) + 1

    winner = None
    winner_count = 0
    for value, count in counts.items():
        if count > winner_count:
            winner = value
            winner_count = count

    return winner

此处输入为整数列表。并列最高频时返回最早出现的值：Python 3.7+ 的字典保留插入顺序，更新已有键不改变位置；空列表返回 None。比如 [3, 1, 3, 1] 返回 3。

令 n 为输入长度，u 为不同值数量：

第一个循环执行 n 次。在通常的哈希假设下，期望时间是 Θ(n)。
第二个循环执行 u 次，时间是 Θ(u)。
因为 u ≤ n，总期望时间可简化为 Θ(n)。
计数表有 u 个键，辅助空间为 Θ(u)。
若键的哈希或相等比较不是常数成本，或者遭遇严重冲突，需要把相应成本补进模型。

“两个循环所以 2n，最后是 O(n)”只完成了表面计算；把 u 和哈希假设写出来，结论才可供别人复核。

一页速查

代码形状	先写出的表达式	常见紧界	检查点
固定次数操作	`c`	`Θ(1)`	操作本身是否真是常数成本？
一个完整循环	`cn`	`Θ(n)`	是否可能提前返回？
两个顺序输入	`n + m`	`Θ(n + m)`	不要擅自令 `m = n`
两个完整嵌套输入	`nm`	`Θ(nm)`	是否还要输出 `k` 个结果？
三角范围	`n(n-1)/2`	`Θ(n²)`	内层边界依赖哪个变量？
每轮减半	`log₂ n`	`Θ(log n)`	前置排序是否已完成？
分治排序	`2T(n/2) + Θ(n)`	`Θ(n log n)`	子问题是否等大？
递归链	`T(n-1) + Θ(1)`	`Θ(n)`	同时计递归栈

过关练习

先不要运行，写出推导，再用不同规模验证操作计数：

把 unordered_pairs 改为只计数、不保存结果。时间是否变化？输出和辅助空间怎样变化？
分析“对 n 个查询，分别在长度为 m 的有序数组中二分查找”。答案应保留哪两个变量？
找一处你熟悉语言中的切片或复制 API，查清它是视图还是复制，再修正所在循环的复杂度。
解释为什么动态数组追加“摊还 Θ(1)”不等于“每次最坏 Θ(1)”。

让推导与观测成本对齐

重新分析 unordered_pairs：若只计数而不保存结果，时间仍是 Θ(n²)，输出空间却从 Θ(n²) 降下来。再分析“对 n 个查询，分别在长度为 m 的有序数组中二分查找”，保留两个规模变量，得到最坏时间 Θ(n log(m + 1))；写作 m + 1 也覆盖 m 为 0 或 1 时每次查询的固定开销。不能把这个最坏紧界套到每次首次中点就命中的输入上。

接着找一处真实的切片、复制或排序调用，确认它是视图还是复制、前置条件是什么。动态数组追加的摊还 Θ(1) 也不能改写成每次最坏 Θ(1)。专业分析不追求漂亮标签，只追求变量、假设和成本都对得上。

查阅实现契约

Python Wiki：TimeComplexity：核对常见容器操作的实现假设。
Python list.sort：分析内置排序时先读公开契约。
Open Data Structures：循环、摊还分析与数据结构成本。

下一步：正式的界与递推式

循环账已经对齐。下一篇把 O、Ω、Θ、递归树、Master Theorem 和摊还分析连成一张完整地图，再进入数组与链表。

继续学习渐近界、递推式与摊还分析

第1章逻辑

第2章集合论

第3章证明方法

第4章递归、归纳与递推

第5章关系与函数

第6章组合数学

第7章图论

第8章概率与统计

第9章数论

第10章线性代数

第11章微积分与优化

第12章信息论与数值计算

1.2 常见复杂度分析

从“看起来像”改成“算出来”

顺序执行：先相加

嵌套执行：先看范围

两个完整、独立的范围

依赖外层位置的范围

嵌套不一定相乘到平方

每轮减半：为什么是对数

分支：先注明分析哪一种情况

四类模式放进一个可运行实验

空间复杂度：先说你在计哪一种空间

原地更新不等于完全不占空间

递归栈必须计入

平均、期望和摊还不是同一个词

常见库操作要附上条件

哈希表

排序

复制与切片

实战：最高频元素

一页速查

过关练习

让推导与观测成本对齐

查阅实现契约

下一步：正式的界与递推式