数列、求和、渐近分析与递推关系

两个嵌套循环都可称二次增长，却分别执行 n 平方与 n(n−1)/2 次主体。运行时间还含解释器、分配、表示和具体输入。渐近界描述成本模型随规模增长，相关数量不能互换。

先精确计数，再证明增长并求递归成本。明确收费操作、输入规模，以及最坏、最好或序列总成本。O 应为论证结论，不能先凭印象贴标签。

回忆检查：展开双重和、用对数逆转幂、写完整归纳。按需复习模块 01与模块 04。核心仅需它们；可选二项式增长论证另用模块 05。输入有限、基本操作会终止。

数列为允许整数索引赋值。等差差值固定 d，$a_i=a_0+id$。零到 n−1 的 n 项和为 $na_0+d\,n(n-1)/2$。零项两部分为零。先写起始索引，零基与一基切换会改变常数。

一到 n 的和是 n(n+1)/2。反向排列并逐项相加，每对 n+1、共 n 对，因此原和的两倍 n(n+1)。模块 04 也用归纳证明。两方法覆盖同域，都不依靠成功样例图外推。

等比数列固定比 r，项 $a,ar,ar^2,\ldots$。n≥0 且 r≠1：

令和 S，乘 r 后相减，中间项抵消，得 $(1-r)S=a(1-r^n)$，除法要求 r≠1；r=1 时 na。零项公式零。r=0 也符合有限式，但首项不应被未检查的歧义表示替换。

层成本倍增给 $1+2+\cdots+2^{h-1}=2^h-1$，等成本给 h 倍，逐层减半总不超过首项两倍。这解释后面递归树，都是有限和，不使用无限级数定理。

望远镜和把项写相邻差：$\sum_{i=0}^{n-1}(b_{i+1}-b_i)=b_n-b_0$。展开三项查看抵消与边界，改范围也要改端点。

和线性分拆要求相同索引域。如果某项只在更小范围定义，要补定义或拆范围。成本模型可相加不交类别，但不能把同一事件无意收费两次。

增长分析比较输入增大时的非负函数：常数、对数、n、n log n、多项式、指数。表有直觉但不证明任意足够大输入的比较；下一节量化定义说明义务与常数。

| n | $\log_2n$ | n | $n\log_2n$ | $n^2$ | $2^n$ | |---|---|---|---|---|---|---| | 2 | 1 | 2 | 2 | 4 | 4 | | 4 | 2 | 4 | 8 | 16 | 16 | | 8 | 3 | 8 | 24 | 64 | 256 | | 16 | 4 | 16 | 64 | 256 | 65536 |

固定大于一的底只差正常数，$\log_b n=\ln n/\ln b$，渐近同类。但精确循环仍有底差与取整差；二倍与三倍循环均对数增长，却非相同整数次数。不能因 Theta 忽略常数就删精确式的底。

次数决定多项式渐近，常数可支配小输入。1000n 在 n=10 大于 n²，在 n>1000 后反过来。交点取决于常数，最终增长不承诺每实际数据上的实现速度。

指数最终超过固定次数多项式。可选模块 05 论证：固定整数 k≥0，n≥2(k+1) 时 $2^n\ge\binom n{k+1}\ge(n/2)^{k+1}/(k+1)!$，每分子因子至少 n/2。除 nᵏ 得随 n 线性增长的下界，可超过任何固定常数。k 固定，若随 n 变就是另一主张。

规模需定义。图可依赖顶点与边，矩阵乘依赖三个维度，训练还依赖批大小与迭代数。未声明关系就压成一符号会隐藏成本；后面线性代数保留形状参数。

位长也是规模。数值 N 约需 log₂N 二进制位；N 次迭代在 N 为二幂时，对位长是指数。数值与表示长度不能等同。本实验 n 为明确次数参数，主体计数非完整位复杂度。

内存、比较、算术、通信可有不同成本。固定主体次数仍可能做成本随操作数位长增长的大整数乘法。单位成本模型有用，但要说明分析层次与限制。

f、g 最终非负，g 最终正。$f\in O(g)$ 意为存在固定 c>0、n₀，使全部 n≥n₀ 满足 $f(n)\le cg(n)$。常数先固定再覆盖后续全部输入，不能每 n 换 c。常见写 f=O(g) 是类归属简写。

$f\in\Omega(g)$ 给固定正 c 与阈值下的下界。$f\in\Theta(g)$ 同时给上下，即 $c_1g(n)\le f(n)\le c_2g(n)$ 对全部后续 n，两个正常数。O 上界，Theta 双向紧增长类。

同 f 也 O(n³)，正确但较弱。把 O 当精确会错误解释两个描述。f=n 是 O(n²) 却非 Theta(n²)，因为正常数乘平方不能永在 n 下。上界不供紧性。

小 o更强：任意 ε>0，都存在 n₀，使所有后续 n 满足 $f(n)<\varepsilon g(n)$。相对 g 最终小于任意比例；阈值可依 ε，但固定后覆盖全部后续 n。

n 对 n²，选整数 n₀>1/ε，后续比 1/n<ε，故 n=o(n²)。平方对自身 O 却非小 o，ε=1/2 不可能。直接不等式不需要模块 15 的极限记法。

量词顺序接模块 02：O 是存在 c、n₀ 再全称 n，小 o 是全称 ε、存在 n₀、全称 n。换顺序改变要求。有限比值图提示常数，证明仍需覆盖无限尾。

先明确 f。最坏为规模 n 允许输入的最大成本，最好为最小，平均需输入概率分布。各函数可分别有 O、Omega、Theta。O 不自动是最坏，Omega 不自动是最好；输入模型选函数，渐近符号描述界。

证明后可省低阶与常数，模型前不能。固定字长改任意精度，预建数据改即时构造，收费基本成本可能变；重新审模型，不应迁移旧标签。

先选收费操作。实验一每进入主体一次收费一，不单独计条件、增量、访问、指令。此模型理解循环形状，完整模型加类别会改精确常数；主体若非恒成本也可能改增长。

矩形 n 外乘 n 内有 n²。三角各 i 次有 n(n−1)/2。最终都 Theta(n²)，但精确不同且三角 n=1 零。渐近阈值可排小例，不否定其实际行为。

条件多检查一次，因此正 n 条件 h+2，零 n 一次。都对数增长但精确类别不同，应标公式计什么。

首次搜索非空首匹配只一次，缺失或末匹配 n 次，最坏 n、最好一。平均不能只由两极推，需要目标位置与存在分布。

最坏上界覆盖全部输入，紧性要有输入族达规模。搜索不重复检查，故至多 n；缺失族每规模达 n。最好要给达最小的输入，不能改允许域。假设首项匹配是不同约定，不是通用搜索最坏改进。

m 行 n 项扫描有 mn，m 固定正数时对 n 线性，m=n 时平方。矩阵 AI 常保留多形状与迭代数，声明缩放关系后才化一参数。

时间观察依机器、解释器、输入与范围。常数查询若含列表构造，收费了预建模型不含的设置。缓存、调度、编译、位长也影响。重复描述变化不自行证明无限渐近。

报告范围、输入族与预测操作，观测不符先审设置、隐藏工作与基本成本。后续数值模块扩展到准确性与可复现性。

纳秒时间戳不保证逐纳秒分辨。极短查询可能起止读数相同、测为零，这是测量限制，不是零工作。批量多次使可测，但也含循环与调用开销，应报告范围而非当完美隔离成本。

实验故意展示短时间，取七次最小是选定观察，不是平均或分布保证。更强实验会记录环境、多规模几何递增、分离设置、保留重复观测并比较理论预测。改善实验不改变有限观察与最终界证明的逻辑区别。

递推用更小成本与当前工作定义成本，需基础、允许规模域及算法依据。等半先限制 n=2ʰ，h≥0，减半恰到一。其他大小的取整需另论证，不能默算分数问题规模。

$T(n)=2T(n/2)+n$、T(1)=1，两子问题半大小，n 非递归工作。展开一层 $4T(n/4)+2n$；第 j 层 $2^j$ 子问题各 $n/2^j$，总层工作 n，叶深 h=log₂n。

一个半子递推层成本减半，非叶 $n+n/2+\cdots+2=2n-2$，叶一，T=2n−1。四半子层倍增，非叶 n(n−1)，叶 n²，T=2n²−n。

这是数学工作模型。带记忆的数值求解程序复用相同子问题，不执行全部被建模操作。实验缓存算成本数字，运行时间不是 T 描述的算法时间，混淆会误解释。

减一也可展开：$T(n)=T(n-1)+n$、T(0)=0，得一到 n 和，n(n+1)/2。深度 n 非对数，n−1 非固定比例子问题，后面等比定理不直接适用。

代入验证假设小规模界，推当前且覆盖基础。平衡两子猜 T≤Cn，得 $2C(n/2)+n=(C+1)n$，不能闭合，需要累积层的对数。单子 T≤2n 可以闭合，精确 2n−1 另保基础修正。跟踪大小因子与当前工作。

递推还要求子数、大小正确。代码不均衡、额外复制或输入依赖停止，要重建模型。平均平衡树不证明可极不均分算法的最坏界，先推实际递推再分类。

证明一个清楚的主定理（Master theorem）特例：$T(n)=aT(n/b)+cn^d$，T(1) 固定正，a≥1 整数、b>1 固定整数、c>0、d≥0，n=bʰ。p=log_b a，第 j 层 $cn^d(a/b^d)^j$，叶 Theta(nᵖ)，有限等比和给：

q=a/bᵈ>1 时末层支配，$n^dq^h=n^p$；q=1 时 h 同成本层给对数；q<1 时总上下由根成本常数倍界。叶项不改变分类，结论依明确条件。

更一般版本用 f(n)，常见基本版比较 f 与 nᵖ：O(nᵖ⁻ε)、Theta(nᵖ)、Omega(nᵖ⁺ε)，ε>0；第三还要求最终 $af(n/b)\le c_0f(n)$，c₀<1 的正则条件。声明版本，平衡不等于任何稍小或稍大，纯幂证明不自动涵盖任意振荡 f。

边界 $T=2T(n/2)+n/\log_2n$，T(1)=1，非叶项仅 n≥2。n=2ʰ，第 j 层 n/(h−j)，故精确 $T=n(1+H_h)$，$H_h=1+1/2+\cdots+1/h$。基本 f=Theta(n) 不适用，f 也不比 n 多项式地小，应展开或用适用定理。精确式足够实验，进一步渐近可选。

摊还分析（amortised analysis）界操作序列总成本再除操作数，无需概率。个别昂贵仍可常数摊还，只要整体足够便宜。单次最坏、分布平均、序列摊还不同。

摊还须覆盖模型中全部允许序列。仅追加使容量几何增；每次删除都收缩可能反复扩缩，原证明不涵盖任意交替操作。复用结论前明确操作族。

Python 3.11 或更新，无需包，见入门。@cache 复用相同参数的数值结果，求成本值而非执行所有被建模工作。计时跨机器/构建变化，两版显示同一次实际捕获。每次解释十分：预测三、模型四、诊断三。

五十分钟：预测零、一、四、八、十六全部输出，区分矩形、三角、倍增。正整数 bit_length() 等于 floor(log₂n)+1，零主体零。把三角内止改 i+1 更新精确式；条件收费会改精确数，不自动改增长。

下载 lab1_loop_counts.py

"""Charge one operation per body entry, not elapsed time or every instruction."""


def counts(n):
    rectangular = triangular = doubling = 0
    for _ in range(n):
        for _ in range(n):
            rectangular += 1
    for i in range(n):
        for _ in range(i):
            triangular += 1
    i = 1
    while i <= n:
        doubling += 1
        i *= 2
    assert rectangular == n * n
    assert triangular == n * (n - 1) // 2
    assert doubling == n.bit_length()
    return rectangular, triangular, doubling


def main():
    print("n | rectangular body | triangular body | doubling body")
    for n in (0, 1, 4, 8, 16):
        print(n, "|", " | ".join(map(str, counts(n))))
    print("Body-entry counts exclude loop guards and integer-operation bit costs.")


if __name__ == "__main__":
    main()

n | rectangular body | triangular body | doubling body
0 | 0 | 0 | 0
1 | 1 | 0 | 1
4 | 16 | 6 | 3
8 | 64 | 28 | 4
16 | 256 | 120 | 5
Body-entry counts exclude loop guards and integer-operation bit costs.

五十分钟：预测八行并推三完整解，基础一。运行比较一、二、四子。改基础二，先推新叶贡献。保持二幂，脚本不分析任意 n 取整。解释记忆化求模型为何不自动加速所有实际递归算法。

下载 lab2_recurrences.py

"""Exact recurrences for powers of two; the multiplier counts identical children."""
from functools import cache


@cache
def cost(n, branches):
    if n == 1:
        return 1
    return branches * cost(n // 2, branches) + n


def main():
    print("n | T1(n) | T2(n) | T4(n)")
    for exponent in range(7):
        n = 2 ** exponent
        values = [cost(n, branches) for branches in (1, 2, 4)]
        assert values == [2 * n - 1, n * (exponent + 1), 2 * n * n - n]
        print(n, "|", " | ".join(map(str, values)))
    print("All bases T(1)=1, all non-leaf work=n, all child sizes=n/2.")
    print("Caching computes the numerical model; it is not the runtime of a real recursive algorithm.")


if __name__ == "__main__":
    main()

n | T1(n) | T2(n) | T4(n)
1 | 1 | 1 | 1
2 | 3 | 4 | 6
4 | 7 | 12 | 28
8 | 15 | 32 | 120
16 | 31 | 80 | 496
32 | 63 | 192 | 2016
64 | 127 | 448 | 8128
All bases T(1)=1, all non-leaf work=n, all child sizes=n/2.
Caching computes the numerical model; it is not the runtime of a real recursive algorithm.

五十分钟：指出含列表设置的计时，独立于纳秒预测精确比。零/微小时间可能分辨率限制。n/log₂n 不在基本平衡，比较调和精确式。预测八、九次追加复制，解释昂贵扩容与少于 3m 总界兼容。分配与初始化未收费。

下载 lab3_cost_traps.py

"""Measured scope, a borderline recurrence, and aggregate doubling-array costs."""
from fractions import Fraction
from time import perf_counter_ns


def measure(call):
    best = None
    for _ in range(7):
        start = perf_counter_ns()
        call()
        elapsed = perf_counter_ns() - start
        best = elapsed if best is None else min(best, elapsed)
    return best


def append_cost(m):
    storage, size, copies, writes = [None], 0, 0, 0
    for value in range(m):
        if size == len(storage):
            larger = [None] * (2 * len(storage))
            for i in range(size):
                larger[i] = storage[i]
                copies += 1
            storage = larger
        storage[size] = value
        writes += 1
        size += 1
    assert storage[:size] == list(range(m))
    assert m == 0 or copies + writes < 3 * m
    return copies, writes


def main():
    print("Timing scope: the query reads the first entry; setup creates n entries.")
    for n in (1000, 4000):
        items = list(range(n))
        query_only = measure(lambda: items[0] == 0)
        with_setup = measure(lambda: list(range(n))[0] == 0)
        print(f"n={n}: one comparison; query-only best={query_only} ns; including setup best={with_setup} ns")
    print("Times vary by run/machine; no asymptotic claim follows from these four measurements.")
    print("Borderline: T(2^h)=2*T(2^(h-1))+2^h/h, T(1)=1")
    total, harmonic = Fraction(1), Fraction(0)
    for h in range(1, 6):
        n = 2 ** h
        total = 2 * total + Fraction(n, h)
        harmonic += Fraction(1, h)
        assert total == n * (1 + harmonic)
        print(f"h={h}, n={n}: T/n={total/n}; exact=1+H_h")
    print("The basic balanced f(n)=Theta(n) case does not apply to n/log2(n).")
    for m in (0, 1, 2, 3, 4, 5, 8, 9, 16, 17):
        copies, writes = append_cost(m)
        print(f"appends={m}: copies={copies}, writes={writes}, charged total={copies+writes}")
    print("Charge model counts copies+writes, excluding allocation/initialisation costs.")


if __name__ == "__main__":
    main()

Timing scope: the query reads the first entry; setup creates n entries.
n=1000: one comparison; query-only best=100 ns; including setup best=3700 ns
n=4000: one comparison; query-only best=0 ns; including setup best=15400 ns
Times vary by run/machine; no asymptotic claim follows from these four measurements.
Borderline: T(2^h)=2*T(2^(h-1))+2^h/h, T(1)=1
h=1, n=2: T/n=2; exact=1+H_h
h=2, n=4: T/n=5/2; exact=1+H_h
h=3, n=8: T/n=17/6; exact=1+H_h
h=4, n=16: T/n=37/12; exact=1+H_h
h=5, n=32: T/n=197/60; exact=1+H_h
The basic balanced f(n)=Theta(n) case does not apply to n/log2(n).
appends=0: copies=0, writes=0, charged total=0
appends=1: copies=0, writes=1, charged total=1
appends=2: copies=1, writes=2, charged total=3
appends=3: copies=3, writes=3, charged total=6
appends=4: copies=3, writes=4, charged total=7
appends=5: copies=7, writes=5, charged total=12
appends=8: copies=7, writes=8, charged total=15
appends=9: copies=15, writes=9, charged total=24
appends=16: copies=15, writes=16, charged total=31
appends=17: copies=31, writes=17, charged total=48
Charge model counts copies+writes, excluding allocation/initialisation costs.

练习 1–12 预算 140 分钟、每题五分，扩展 25。声明规模域、操作、界见证，每递推有基础与核对。

九自动选择与书面自评共十分。界需说明函数与常数范围，不只是标签。

必读二十五分钟：在 MIT Mathematics for Computer Science 教材求和与渐近材料中，改写一个界为量词并给常数。

必读十一分钟：MIT 6.006 Recitation 3 的递归树与主定理，比较多项式工作案例及基础。

必读九分钟：教材摊还选段，指出总成本及收费事件，与单次最坏比较。总四十五分钟。

选读：MIT 主定理练习 的更完整条件及 Python 时钟文档 的单位与分辨率。例子与推导原创。

有限和给精确公式，量化渐近用阈值后固定见证比较。递推记录小调用与当前工作，树解释层与叶。定理在条件下总结，摊还界序列而非每单次。

结业任务：推三角与倍增计数、常数证 Theta、解核对平衡递推、解释昂贵追加与线性前缀。练习六十、实验三十、测验十分。每答明确规模、操作、输入模型与计时范围。

模块 07 兼顾图结构与成本。先解释扫描所有顶点与存储邻接项为何依赖两数量，边数不自动是顶点数平方。