跳转到内容
← 返回算法
算法范式计算机科学 · 算法设计约 26 分钟阅读

分治算法

Divide and Conquer

"分而治之"——这句话在政治上是权谋，在算法里是智慧。 分治（Divide and Conquer）是最古老、最有力的算法设计范式之一。它的逻辑无比简单：把一个大问题拆成若干个同类小问题，递归地解决每个小问题，再把结果合并起来。

分治递归主定理归并排序

"分而治之"——这句话在政治上是权谋，在算法里是智慧。

分治（Divide and Conquer）是最古老、最有力的算法设计范式之一。它的逻辑无比简单：把一个大问题拆成若干个同类小问题，递归地解决每个小问题，再把结果合并起来。

这一思想在数学里其实由来已久。但将其系统化为计算机算法设计方法，正是 20 世纪中叶计算机科学成型期的重大贡献。归并排序、快速排序、FFT、Strassen 矩阵乘法——这些算法都是分治思想的直接产物。

破除误解：分治不等于"拆成两半"

很多人把分治等同于"二分"，认为每次一定要把问题对半劈开。这是过度简化。分治的核心不是"分几份"，而是三步骤的递归结构：

  1. Divide（分解）：将问题分解为若干规模更小的子问题
  2. Conquer（解决）：递归地解决每个子问题（足够小时直接解决）
  3. Combine（合并）：把子问题的解合并为原问题的解

有些分治每次分成 2 份（归并排序），有些分成 3 份（三分搜索），有些分成更多（FFT 分成 2 组，但每组不一定是原问题的一半）。关键是"同类子问题"和"合并"。

主定理：分析分治复杂度的利器

分治算法的时间复杂度通常满足递推关系：

T(n)=a⋅T ⁣(nb)+f(n)T(n) = a \cdot T\!\left(\frac{n}{b}\right) + f(n)

其中：$a$ 是子问题个数，$b$ 是每个子问题的规模缩减比例，$f(n)$ 是分解和合并的代价。

主定理（Master Theorem）（由 Bentley、Haken、Saxe 1980 年建立，Cormen 等推广）：

设 c=log⁡bac = \log_b a（子问题叶节点数量的增长指数），则：

条件结论
f(n)=O(nc−ε)f(n) = O(n^{c-\varepsilon})（$f$ 增长较慢）T(n)=Θ(nc)T(n) = \Theta(n^c)
f(n)=Θ(nclog⁡kn)f(n) = \Theta(n^c \log^k n)T(n)=Θ(nclog⁡k+1n)T(n) = \Theta(n^c \log^{k+1} n)
f(n)=Ω(nc+ε)f(n) = \Omega(n^{c+\varepsilon})（$f$ 增长较快，且满足规律性条件）T(n)=Θ(f(n))T(n) = \Theta(f(n))

典型例子：

  • 归并排序：$T(n) = 2T(n/2) + O(n)$，$a=2, b=2, c=1$，f(n)=Θ(n1)f(n)=\Theta(n^1)，第二种情况：T(n)=Θ(nlog⁡n)T(n)=\Theta(n \log n)
  • 二分查找：$T(n) = T(n/2) + O(1)$，$a=1, b=2, c=0$，f(n)=Θ(1)=Θ(n0)f(n)=\Theta(1)=\Theta(n^0)，第二种情况：T(n)=Θ(log⁡n)T(n)=\Theta(\log n)
  • Strassen 矩阵乘法：T(n)=7T(n/2)+O(n2)T(n) = 7T(n/2) + O(n^2)，c=log⁡27≈2.807c=\log_2 7 \approx 2.807，f(n)=O(n2)=O(nc−ε)f(n)=O(n^2)=O(n^{c-\varepsilon})，第一种情况：T(n)=Θ(nlog⁡27)T(n)=\Theta(n^{\log_2 7})

三种情形，三张账：钱花在树的哪一层

主定理的三种情形不是三条要背的规则，而是同一个问题的三个答案：递归树的总开销，主要花在哪一层？ 下面三个递推式各代入 n=1024=210n = 1024 = 2^{10} 算一遍，答案会自己浮出来。

情形一：叶子层吃掉一切

T(n)=8T(n/2)+n2T(n) = 8T(n/2) + n^2

$a=8, b=2$，c=log⁡28=3c = \log_2 8 = 3；f(n)=n2=O(n3−1)f(n) = n^2 = O(n^{3-1})，属第一种情形，结论 Θ(n3)\Theta(n^3)。

代入验算：第 $i$ 层有 8i8^i 个规模为 n/2in/2^i 的子问题，每个花 (n/2i)2(n/2^i)^2，所以第 $i$ 层总开销是 8i⋅n2/4i=2in28^i \cdot n^2/4^i = 2^i n^2。每往下一层，开销翻一倍。 $n=1024$ 时：

层 $i$012…910（叶）
本层开销 / n2n^2124…5121024

总和 =n2(211−1)≈2n2⋅n=2n3= n^2(2^{11} - 1) \approx 2n^2 \cdot n = 2n^3。最后一层单独就占了总和的一半，前面十层加起来才抵得上它一层。这就是"叶子主导"：8log⁡2n=n38^{\log_2 n} = n^3 个叶子，每个常数代价，叶子数量本身就是答案。

情形二：每层花一样多

T(n)=2T(n/2)+nT(n) = 2T(n/2) + n

$c = 1$，f(n)=Θ(n1)=Θ(nclog⁡0n)f(n) = \Theta(n^1) = \Theta(n^c\log^0 n)，第二种情形（$k=0$），结论 Θ(nlog⁡n)\Theta(n\log n)。

代入验算：第 $i$ 层有 2i2^i 个规模 n/2in/2^i 的子问题，每个花 n/2in/2^i，本层总计恰好 $n$——与层数无关。$n=1024$ 有 11 层（$i=0$ 到 $10$），总计 11×1024=1126411 \times 1024 = 11264，正是 nlog⁡2n+nn\log_2 n + n 的量级。这类递推的多出来的那个 log⁡n\log n 因子，就是"层数"本身。

情形三：根节点吃掉一切

T(n)=2T(n/2)+n2T(n) = 2T(n/2) + n^2

$c = 1$，f(n)=n2=Ω(n1+1)f(n) = n^2 = \Omega(n^{1+1})；再验规律性条件：a f(n/b)=2(n/2)2=n2/2≤12f(n)a\,f(n/b) = 2(n/2)^2 = n^2/2 \leq \tfrac12 f(n)，系数 12<1\tfrac12 < 1，条件满足，结论 Θ(n2)\Theta(n^2)。

代入验算：第 $i$ 层开销 =2i(n/2i)2=n2/2i= 2^i (n/2^i)^2 = n^2/2^i，每往下一层减半，是个收敛的几何级数，总和 <2n2< 2n^2。$n=1024$ 时根节点一层就是 1048576，全树不到它的两倍。合并太贵，递归下去纯属陪跑。

主定理管不着的那一类

主定理不是万能的，最经典的漏洞是：

T(n)=2T(n/2)+nlog⁡nT(n) = 2T(n/2) + \frac{n}{\log n}

$c=1$，而 f(n)=n/log⁡nf(n) = n/\log n。它比 $n$ 小，但不是多项式级地小——n/(n/log⁡n)=log⁡nn / (n/\log n) = \log n，永远追不上任何 nεn^\varepsilon。所以它既不满足情形一（需要 f=O(n1−ε)f = O(n^{1-\varepsilon})），也不满足情形二（需要 f=Θ(nlog⁡kn)f = \Theta(n\log^k n) 且 k≥0k \geq 0，这里 $k = -1$）。三个抽屉都放不进去。

换成递归树就有答案了。第 $i$ 层开销 =2i⋅n/2ilog⁡(n/2i)=nlog⁡n−i= 2^i \cdot \dfrac{n/2^i}{\log(n/2^i)} = \dfrac{n}{\log n - i}，把 $i = 0$ 到 log⁡2n−1\log_2 n - 1 全加起来：

∑i=0log⁡n−1nlog⁡n−i=n(1+12+13+⋯+1log⁡n)=n⋅Hlog⁡n=Θ(nlog⁡log⁡n)\sum_{i=0}^{\log n - 1} \frac{n}{\log n - i} = n\left(1 + \tfrac12 + \tfrac13 + \cdots + \tfrac{1}{\log n}\right) = n \cdot H_{\log n} = \Theta(n \log\log n)

（HmH_m 是调和数，Hm≈ln⁡mH_m \approx \ln m。）$n = 1024$ 时 H10≈2.93H_{10} \approx 2.93，总计约 $2999$ 次操作——夹在 $n = 1024$ 与 nlog⁡n=10240n\log n = 10240 之间，一个主定理三种情形都表达不出来的量级。

该记住的是：主定理是递归树求和的一个快捷方式，不是它的替代品。碰到 log⁡\log 出现在分母、或者子问题规模不均匀（如 $T(n) = T(n/3) + T(2n/3) + n$）的时候，回到递归树，老老实实按层求和。

经典案例

归并排序

最干净的分治实例。将数组二分，递归排序两半，线性时间合并：

  • 分解：$O(1)$（找中点）
  • 子问题：2×T(n/2)2 \times T(n/2)
  • 合并：$O(n)$
  • 总计：T(n)=Θ(nlog⁡n)T(n) = \Theta(n \log n)

归并排序是分治的教科书范例，也是第一个被严格证明时间最优（对比较排序而言）的算法。

Strassen 矩阵乘法

1969 年，Volker Strassen 发现了一个让数学界震惊的结果：2×22 \times 2 矩阵相乘本以为需要 8 次标量乘法，他找到了仅用 7 次的方案（代价是更多加法）。

将大矩阵分块为 2×22 \times 2 的子矩阵，递归运用 7 乘法方案，总代价从朴素的 O(n3)O(n^3) 降至 O(n2.807)O(n^{2.807})。

虽然常数大、实现复杂，但 Strassen 第一次证明矩阵乘法的复杂度上界可以低于朴素的 n3n^3，开启了整个矩阵乘法算法的研究方向（值得强调：这是把上界往下压，而非给出下界——矩阵乘法的真实下界至今仍是开放问题，目前只有平凡的 Ω(n2)\Omega(n^2)）。沿着这条路，Coppersmith-Winograd（1990，常引作 1987）把指数降到约 $2.376$，此后经 Williams（2012）、Alman-Williams（2020）等一系列改进，当前最优记录约为 O(n2.371)O(n^{2.371})，但这些算法常数巨大，实用价值有限。

那 Strassen 自己实用吗？答案是"在一个具体的门槛之上"。 实践中的做法是混合：矩阵大时递归用 Strassen 切分，子矩阵小到某个交叉点（crossover point）以下就切回朴素三重循环。交叉点具体在哪，取决于机器：只数算术操作次数、不管缓存与流水线的理论分析给出的值低到 $n = 8$（Higham）或 $n = 12$（Huss-Lederman 等），实测值通常更高。Higham 1990 年那篇把 Strassen 塞进 Level-3 BLAS 的论文给出的经验判断是：矩阵维数超过约 100 之后，这个方法才真正开始有实用价值。

还有一条比速度更要命的代价：数值稳定性。 朴素矩阵乘法的舍入误差界是逐元素（component-wise）的——每个输出元素的误差只跟参与它的那一行一列有关。Strassen 做不到，因为它的 7 个乘积把矩阵中相隔很远的元素加在了一起；它只能给出范数（norm-wise）误差界，而且递归层数越多，误差界里的常数增长越快。Higham 在《数值算法的精度与稳定性》第 23 章里的结论是：Strassen 在两方面比朴素乘法差——误差界更弱（范数而非逐元素），且常数增长更快。所以在需要逐元素精度保证的科学计算里，Strassen 通常直接被排除，与它快多少无关。

最近点对问题

平面上 $n$ 个点，找距离最近的两点。朴素方法 O(n2)O(n^2)，分治可做到 O(nlog⁡n)O(n \log n)：

  1. 按 $x$ 坐标排序，从中间垂直线分成左右两半
  2. 递归求左半部分最近距离 dLd_L、右半部分 dRd_R，令 d=min⁡(dL,dR)d = \min(d_L, d_R)
  3. 关键步骤：检查跨越中线的点对——只需检查距中线距离 ≤d\leq d 的点，且可以证明每个点最多只需与 7 个邻居比较
  4. 合并代价 $O(n)$，总计 O(nlog⁡n)O(n \log n)

这道题的精妙在于"合并"步骤中对潜在跨界点对的剪枝论证，是分治设计中最有教学价值的例子之一。

大整数乘法（Karatsuba 算法）

朴素的长乘法对两个 $n$ 位整数需要 O(n2)O(n^2) 次单位乘法。1960 年，Anatoly Karatsuba（当时是苏联学生）提出分治方案：

将 $n$ 位整数 x=xH⋅10n/2+xLx = x_H \cdot 10^{n/2} + x_L，则：

x⋅y=xHyH⋅10n+(xHyL+xLyH)⋅10n/2+xLyLx \cdot y = x_H y_H \cdot 10^n + (x_H y_L + x_L y_H) \cdot 10^{n/2} + x_L y_L

朴素地需要 4 次半长整数乘法，但注意：

xHyL+xLyH=(xH+xL)(yH+yL)−xHyH−xLyLx_H y_L + x_L y_H = (x_H + x_L)(y_H + y_L) - x_H y_H - x_L y_L

只需 3 次半长整数乘法！递推：$T(n) = 3T(n/2) + O(n)$，解为 T(n)=O(nlog⁡23)≈O(n1.585)T(n) = O(n^{\log_2 3}) \approx O(n^{1.585})。

这件事的经过值得复述。1960 年，Kolmogorov 在莫斯科大学开了一个关于计算复杂性的讨论班，他在班上提出一个猜想：沿用了几千年的 O(n2)O(n^2) 长乘法就是最优的，并把证明这个下界当作讨论班的目标之一。一周之内，班上一名 23 岁的学生 Karatsuba 拿出了上面这三行恒等式，把猜想推翻了。Kolmogorov 在下一次讨论班上亲自宣布了这个结果，随后把讨论班解散了——目标已经不存在。1962 年他以 Karatsuba 与 Ofman 的名义把方法发表在《苏联科学院院报》上，据 Karatsuba 后来的回忆，发表时并没有事先通知他。

手算 Karatsuba：1234 × 5678

三行恒等式看着轻巧，真正让人相信它的是把数字算完。拆 $x = 1234$、$y = 5678$，取 xH=12, xL=34, yH=56, yL=78x_H = 12,\ x_L = 34,\ y_H = 56,\ y_L = 78（基数 10210^2）：

步做什么数值
1乘法① xHyHx_H y_H12×56=67212 \times 56 = 672
2乘法② xLyLx_L y_L34×78=265234 \times 78 = 2652
3乘法③ (xH+xL)(yH+yL)(x_H{+}x_L)(y_H{+}y_L)46×134=616446 \times 134 = 6164
4中项 $= ③ - ① - ②$$6164 - 672 - 2652 = 2840$
5按位拼装672×104+2840×102+2652672 \times 10^4 + 2840 \times 10^2 + 2652
6相加6 720 000+284 000+2652=7 006 6526\,720\,000 + 284\,000 + 2652 = \mathbf{7\,006\,652}

朴素做法要算四次两位乘法：12×56=67212{\times}56 = 672、12×78=93612{\times}78 = 936、34×56=190434{\times}56 = 1904、34×78=265234{\times}78 = 2652，中项是 $936 + 1904 = 2840$——和第 4 步一模一样。两条路径给出同一个中项 2840，但一条用了 4 次乘法，另一条用 3 次乘法加 2 次加法和 2 次减法。

这张表最该注意的是第 3 步的 46×13446 \times 134。xH+xL=46x_H + x_L = 46 还是两位，但 yH+yL=134y_H + y_L = 134 变成了三位——半长相加会溢出到 $n/2 + 1$ 位。教科书的递推式 $T(n) = 3T(n/2) + O(n)$ 假装三个子乘法规模相同，实际实现里第三个略大一点，必须专门处理这个进位，否则就是一个经典的边界 bug。渐进复杂度看不见这一位，代码看得见。

同时也看清了另一件事：在 $n = 4$ 位这个规模上，Karatsuba 根本不划算。省下一次两位乘法，换来四次多位加减，还多了一次跨位拼装。它要赢，得等 $n$ 大到"一次乘法比几次加法贵得多"的时候。

现场：大数库里的阈值就是这个交叉点

GNU 多精度库 GMP 是这套理论最直接的落地。GMP 的乘法不是一个算法，是一个按规模分层的算法梯队：小操作数走朴素长乘法（basecase），大一点走 Karatsuba，再大走 Toom-3、Toom-4，最大走 FFT 类算法。切换点是一组编译期常量，Karatsuba 那一档叫 MUL_TOOM22_THRESHOLD（GMP 把 Karatsuba 归类为 Toom-2.2）。

这个常量的取值不是拍的，是在目标机器上实测出来的。GMP 官方维护一张跨架构的调优表，在 56 台测试主机上实测出的阈值分布在 8 到 46 limb 之间，中位数 24；具体到几款 CPU：ARM Cortex-A72（64 位）测出 8，Cortex-A53 测出 14，Intel Nehalem 16，AMD Zen 20，Intel Haswell 22。GMP 手册自己的说法是这个阈值"可以低到 10 limb"。

一个 limb 在 64 位机器上是 64 比特，所以中位数 24 limb 大约是 1536 比特、约 460 位十进制数。换句话说：低于 460 位的整数相乘，"更快的算法"在真机上更慢。

三点值得记住：

  1. 同一份算法，最优阈值在不同 CPU 上差 5 倍以上（8 vs 46）。差异来自乘法器延迟、寄存器数量、缓存行为——全是渐进分析里被抽象掉的东西。
  2. 分层是常态，不是妥协。真实的高性能库几乎从不"选一个算法"，而是按规模串起一条流水线，每一档都在自己的区间里最优。这和跳表在小集合上退回线性扫描、排序库在小数组上退回插入排序是同一种工程手法。
  3. 交叉点是可以测的，也应该测。 GMP 提供 tune 程序在目标机上自动搜索这些常量。把阈值写死在源码里，等于假设所有机器长得一样。

分治与动态规划的区别

两者都用递归分解，区别在于子问题是否重叠：

分治动态规划
子问题不重叠（独立）重叠（被重复计算）
内存不需要记忆化需要记忆化或表格
例子归并排序、FFT斐波那契、最长公共子序列

若用动态规划解子问题不重叠的问题，浪费内存；若用分治解子问题重叠的问题，指数级重复计算。

递归树：理解复杂度的直觉工具

分析分治复杂度的核心工具是递归树：把递推展开成树，每层求和，最终相加。

以 $T(n) = 2T(n/2) + cn$ 为例：

层 0：                cn          → cn
层 1：       cn/2  +  cn/2        → cn
层 2：    cn/4+cn/4+cn/4+cn/4     → cn
...
层 log n： n 个叶节点各 c          → cn
```

共 log⁡n+1\log n + 1 层，每层 $cn$，总计 Θ(nlog⁡n)\Theta(n \log n)。

并行化视角：分治天然是 fork-join

分治有一个常被略过的性质：它的递归结构就是一张并行任务依赖图。"递归解决左半和右半"这句话里，左右两半之间没有任何数据依赖，可以同时算；只有"合并"必须等两边都完成。这正是 fork-join 并行模型的形状——fork 出两个子任务，join 等它们回来。

于是同一份分治代码可以不改结构地并行化。Cilk（后来的 Cilk Plus、OpenCilk）就是围绕这件事设计的语言扩展：把递归调用前加一个 spawn，把合并前加一个 sync，编译器和运行时负责其余部分。Java 7 引入的 ForkJoinPool（Doug Lea 实现）是同一模型在 JVM 上的实现，Arrays.parallelSort 就跑在它上面。

运行时的关键机制是工作窃取（work stealing）：每个工作线程有自己的双端任务队列，从一端取自己 fork 出的任务（保持缓存局部性），空闲时从别人队列的另一端偷一个来做。Blumofe 与 Leiserson 在 1999 年的《ACM 期刊》上证明了这个调度器的效率界——这是第一个对带依赖的多线程计算给出可证明良好调度的结果，也是今天几乎所有任务并行运行时的理论依据。

分治的并行度不是免费的，取决于合并有多贵。 用两个量来衡量：工作量（work）T1T_1 是单核总操作数，跨度（span）T∞T_\infty 是依赖链上最长的那条路径（无限核也躲不掉的时间），并行度就是 T1/T∞T_1 / T_\infty。归并排序：

  • 只并行递归、合并仍然串行：T1=Θ(nlog⁡n)T_1 = \Theta(n\log n)，但跨度被那次最后的 Θ(n)\Theta(n) 合并卡住，T∞=Θ(n)T_\infty = \Theta(n)，并行度只有 Θ(log⁡n)\Theta(\log n)。$n$ 涨一千倍，能用上的核只多 10 倍——基本等于没并行。
  • 把合并本身也做成分治并行（二分找中位数、递归归并两侧）：跨度降到 Θ(log⁡3n)\Theta(\log^3 n)，并行度提升到 Θ(n/log⁡2n)\Theta(n/\log^2 n)。这套分析见 CLRS 的并行算法一章（第 3 版第 27 章、第 4 版第 26 章）。

该记住的判断：一个分治算法好不好并行，看的不是它分成几份，而是合并步骤本身能不能被分治。合并只要还是一遍线性扫描，跨度就锁死在 Θ(n)\Theta(n)，加核无用。这也解释了为什么快速排序在实践中比归并排序更容易并行——它的"合并"是空的，代价前置到了 partition 上，而 partition 也能并行化。

跨域连接

  • 数论：把两个半长乘积之和写成一次乘法减去两项已算出的乘积，四次乘法降到三次，直接推翻了"长乘法已是最优"的猜想。它的意义超出速度：这是把"某运算至少需要多少次基本操作"这类下界猜想真正打掉的早期案例之一。整数乘法的上界此后一路被压到对数线性，而下界至今没有非平凡结果。
  • 相变与临界现象：重整化群的做法是按尺度分层，每层积掉一半自由度并把效果合并进有效参数——递归结构与分治完全一致。合并步是否封闭决定成败：粗粒化后若能用同一族参数描述，递推就成立；若每层都冒出新形式的相互作用，递推就发散。这与"子解能否被廉价拼起来"是同一个条件。
  • 气候建模：显式迭代求解椭圆方程收敛极慢，因为信息只能一格一格传，长波误差要走遍整个网格才被消掉。多重网格把误差按尺度分解：粗网格一步抹掉长波分量，细网格只负责短波，逐层递归。这与分治同源，也解释了"网格加密一倍而迭代次数不变"为何是多重网格独有的性质。
  • 并发：递归解决左右两半之间没有数据依赖，只有合并必须等两边完成——这就是分叉汇合模型的形状，代码结构不改即可并行。但并行度由合并决定：合并若仍是一遍线性扫描，依赖链上最长的那条路径就锁死在线性，加核无用。归并排序必须把合并本身也做成分治，跨度才降得下来。
  • 快速傅里叶变换：它是分治影响面最广的一次落地，也是"合并步靠代数恒等式而非比较"的样板。在大数运算里它还是算法梯队的最后一档：小操作数走朴素长乘法，中等规模走三乘法分治，再大切到多分块方案，最大的才转成多项式乘法交给它。每档的切换阈值都要在目标机器上实测，写死等于假设所有机器长得一样。

参考文献

  • Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022. （第2、4章分治与主定理；第26章并行算法与工作/跨度分析）
  • Karatsuba, A. & Ofman, Y. "Multiplication of Many-Digital Numbers by Automatic Computers." Soviet Physics Doklady 7, 1963.
  • Karatsuba, A. A. "The Complexity of Computations." Proceedings of the Steklov Institute of Mathematics 211, 169–183 (1995).（Karatsuba 本人对 1960 年 Kolmogorov 讨论班经过的回忆）
  • Strassen, V. "Gaussian Elimination is Not Optimal." Numerische Mathematik 13, 1969.
  • Higham, N. J. "Exploiting Fast Matrix Multiplication within the Level 3 BLAS." ACM Transactions on Mathematical Software 16(4), 352–368 (1990).
  • Higham, N. J. Accuracy and Stability of Numerical Algorithms. 2nd ed. SIAM, 2002. （第23章：Strassen 的范数误差界与稳定性代价）
  • Huss-Lederman, S., Jacobson, E. M., Johnson, J. R., Tsao, A. & Turnbull, T. "Implementation of Strassen's Algorithm for Matrix Multiplication." Proceedings of Supercomputing '96 (SC '96), 1996.
  • Blumofe, R. D. & Leiserson, C. E. "Scheduling Multithreaded Computations by Work Stealing." Journal of the ACM 46(5), 720–748 (1999).
  • GNU MP 手册，Karatsuba Multiplication 一节与官方调优数据表 MUL_TOOM22_THRESHOLD（跨 56 台主机的实测阈值）。

延伸阅读

  • Kleinberg, J. & Tardos, É. Algorithm Design. Pearson, 2005. （第5章分治，最近点对的合并论证讲得最清楚）
  • Herlihy, M. & Shavit, N. The Art of Multiprocessor Programming. 2nd ed. 2020.（fork-join 与工作窃取的实现视角）
  • Harvey, D. & van der Hoeven, J. "Integer Multiplication in Time O(nlog⁡n)O(n\log n)." Annals of Mathematics 193(2), 563–617 (2021).（Karatsuba 那条线的当前终点）

正文中引用本条 · 4 · 其中 2 条来自其他领域

宇宙学暗物质晕与星系旋转曲线大尺度结构形成