分治法的核心与归并排序

分治法

分治法的核心思想正如同他的名字一样：分而治之。

想象一下你想要整理一副散落满地的扑克牌，直接面对52张乱序的牌可能会让人感到无从下手。但是如果你只需要整理其中的一张牌，那么这一张牌自己就是有序的，在这之上我们就可以将整理一张牌的问题扩大规模到两张牌，随后52张。这样每一步任务的难度都非常简单。

分治法的核心策略就是：不断地将大问题切分成原本问题的一半，直到问题变得极小（我们叫它Base Case），此时再进行解决，最后将每一个这样的小问题累加回去，得到原本问题最终的解。

归并排序

很多人谈到分治法，首先想到的模范算法就是 归并排序 (Merge Sort) 算法了。归并排序和其他排序算法一样，会将一个无序的队列整理成一个有序的队列，但不同于其他排序算法，归并排序做的是不断将两个已经排好的短数列合并成一个长有序数列。

由于你之前应该已经学过数据结构预算法了，那么你大概之前已经学过什么是归并排序。我在之前已经写过了有关归并排序的内容，你可以在这里查看有关归并排序的代码实现，原理讲解以及算法可视化：

https://naughtychas.github.io/notes/COMP2119/chapter9/

Chapter 9 & 10: 排序算法

总而言之，归并排序主要分为两步执行流程。先来看看分和治都具体在哪里：

递归函数首先执行分：我们不假思索地将数组从中间一刀两断，左边一半右边一半。

随后我们来治：我们使用递归的思路将切分的左右两半数组做同样的事情：排序。我们相信递归函数一定能够把左右两半分别排好序还给我们。

这样的步骤一直到我们碰到Base Case为止。当数组被分的足够小，也就是在Base case时只有一个数，那么这个数字一定是自然有序的。如此，我们就往回找一步：上一次分割时候分出了两个Base case，这一步我们将其合并回一个两个数的数组。

归并排序真正的魔法发生在合并这步。假设手里有两堆牌，左手的一堆按照递归函数的假设已经排好序了，右手的一堆同样也是有序。而你的任务是将它们合并成一堆有序的牌。实际上你不需要重新比较所有的牌，你只需要盯着两堆牌最上面的那一张，像拉拉链一样把两副牌拉在一起就可以了。

在这一步中，我们使用双指针策略来合并两堆牌。假如说左手的牌堆是1, 4, 6，右手是1, 7, 9, 10，那么我们首先比较左手顶部的牌1和右手顶部的牌1。由于两张牌一样，我们默认将左手边的牌堆中的牌放入结果堆，这时候左手堆的指针向前移一位，露出了下一张牌4。

下一步就是比较左手的4和右手的1。显然右手的1更小，因此将1放入结果堆。以此类推，通过这种方式，我们只需要线性扫描一遍两个数组，使用$O(n)$的时间，就能完成合并。

如果你不明白具体过程还是建议你去上面的链接文章中看一看。

归并递推式

假设$T(n)$是排序$n$个数字所需要的时间。

先来看子问题。由于我们将问题切成了两半，所以我们需要处理两个规模为$\frac{n}{2}$的子问题。这样一来这一步贡献了$2T(\frac{n}{2})$的工作量。

当我们将子问题解决之后，我们还要像刚才那样将结果缝合在一起。缝合步骤贡献多少工作量？由于我们使用拉拉链一般的策略，每个子数组只需要遍历一遍，因此缝合两个长度总和为$n$的有序数组，工作量与$n$成正比，也就是$cn$或$\Theta(n)$。

由于归并排序的任务就是子问题与合并，这样我们就得出了那个经典的归并排序递推式：

$$T(n) = 2T(\frac{n}{2}) + \Theta(n)$$

这个公式直观的告诉我们，解决规模为$n$的问题的成本，等于解决两个一般规模问题的成本，再加上合并他们的线性成本。

数学推导与严谨性证明

我们在上一步得到了递推式：

$$T(n) = 2T(\frac{n}{2}) + \Theta(n)$$

但是在COMP3352这节课中，我们不仅要在意这些算法的效率，还要更进一步去思考它们的数学严谨性。

剥洋葱的简单推导

在一个归并排序中，我们一共需要经过多少次数与数之间的对比？换句话说，归并排序中我们的总工作量是多少？

在刚才的递推式中，我们稍作修改：

$$T(n) = 2T(\frac{n}{2}) + C\Theta(n)$$

这里的$Cn$代表合并$n$个元素所需要的线性时间。接下来我们将其一层一层剥开，你可以尝试画一棵树来更好地理解：

第0层

也就是顶层。在这里我们处于最开始的开始，摆在你面前的是一个规模为$n$的问题，那么如果我们想要合并这一层的内容，在子问题完工之后，我们不难得出这一层的合并成本是$Cn$，同时也是这一层的总成本。
第1层

接下来规模为$n$的问题数组分裂成了 两个规模为$\frac{n}{2}$ 的子问题。那么我们如法炮制，这一层的每个子问题的合并成本就一定是 $C(n/2)$ ，同时由于这一层从上一层分裂出了两个子问题 (因为递推式的那一项是$2T(\frac{n}{2})$)，因此如果要计算这一层的总成本，则需要乘以2：

$2 \times C(n/2) = Cn$

因此这一层的总成本还是$Cn$。
第2层

按照上面的规律，这一层分裂出了4个规模为$n/4$的子问题。那么这一层的总成本就是：

$4 \times C(n/4) = Cn$

不难看出在归并排序中，每一层的工作量总和永远是$Cn$。

那么我们一共会有多少层呢？因为每次规模减半，直到触及Base case为止，也就是只剩一个元素，那么树的高度就是$\log_2{n}$。

所以，层数乘以每层的工作量就能够得到归并排序算法的总工作量，也就是：

$$\text{Total} \approx (Cn) \times (\log_2{n}) = O(nlogn)$$

数学归纳证明

推导能够告诉我们有关归并的直觉，但是证明需要更严密的逻辑。

剥洋葱法得出的结论只是一个有理有据的猜测：上一步我们得到了$T(n) = O(nlogn)$，但是在证明这里，我们需要理解为什么$T(n) = O(nlogn)$。也就是说我们要证明：对于所有的$n$，算法的运行时间$T(n)$都一定不会超过$C \cdot n\log{n}$，其中C是某个固定的常数。

为了证明这一点，我们需要证明存在这样一个常数$C$，这个常数能够使得$T(n) \leq Cn \log{n}$。

为什么要引入这样一个常数C？由于按照Big-O的定义，就拿$O(n\log{n})$举例好了（
我们就可以知道：存在某个常数$C$，使得$T(n) \leq C \cdot n\log{n}$。

总的来说，如果我们想要证明算法的一定跑的比这个时间要快，那么通过Big-O的定义来证明复杂度不会超过$O(n\log{n})$就再合适不过了。如果想要使用Big-O，我们就要找到这样一个常数。如果找得到那么就得证，找不到就不行。

假设对于每个规模更小的子问题，结论都是成立的，也就是$T(n/2) \leq C \frac{n}{2} \log{\frac{n}{2}}$，

我们将这个假设带入原始方程：

$$T(n) = 2T(n/2) + Cn$$
$$T(n) \leq 2(C\frac{n}{2}\log{\frac{n}{2}}) + Cn$$

约掉括号内外的2：

$$T(n) \leq Cn\log{(\frac{n}{2})} + Cn$$

利用对数性质$\log{(\frac{a}{b})} = \log{a} - \log{b}$可得：

$$T(n) \leq Cn(\log{n} - \log{2}) + Cn$$

$$T(n) \leq Cn\log{n} - Cn + Cn$$

$$T(n) \leq Cn\log{n}$$

$$\text{Q.E.D.}$$

至此，我们就完成了证明。

我们在这里如何运用数学归纳法？由于我们假设对于一个大小为$n/2$的输入，结论就成立。那么如果我们能够倒腾出来通过$T(n/2)$能退出来$T(n)$也一定符合这个结论，那么我们就可以安全得证了。

万能公式：主定理

如果每次遇到新的算法都需要画树或者做归纳法，那么这样会浪费不少时间。

所以我向你介绍算法分析中的核武器：主定理 (Master Theorem) 。

主定理用来解决形如$T(n) = aT(n/b) + f(n)$的递推式的复杂度分析。其中常量的概念是：

$a$：代表子问题的数量。也就是你的问题在每次递归时被分成几个小问题。
$b$：代表了子问题的缩小比例，指代了每个子问题中，你要从上一层切掉多少的数据来形成子问题。

在归并排序中，由于我们每次撇去一半的元素，因此在这里我们的缩小比例就是2。
$f(n)$：即是分裂和合并的成本。

主定理的核心有点像是一场拔河比赛，参赛双方分别是树叶和每层合并的成本。

树叶也就是我们所说的子问题。在这里我们关心 树叶的增长速度$n^{\log_{b}{a}}$ ，这代表着递归的基本工作量。也就是如果不做很热合并操作，光是把问题切碎到最后一步的基本工作量。

而每层合并的成本就是$f(n)$。这代表了根节点这一层需要合并它的子问题的结果所需要的切分/合并工作量。

但我们如何比较拔河结果？我们分析三个情况：

叶子更重

$n^c > f(n)$

如果$f(n)$增长的比$n^c$要慢（课件上具体来说是慢了$n^\epsilon$这么多），说明你的工作量主要集中在叶子这边。

因此，你的算法的复杂度主要由叶子来决定。你可以得出结论：

$$T(n) = O(n^{\log_{b}{a}})$$

势均力敌

$n^c \approx f(n)$

如果你发现$f(n)$和$n^c$是同一个量级的，比如$f(n) = \Theta(n^c)$，这说明每一层的工作量都差不多。

因此，算法的复杂度由它们一起决定。也就是：

复杂度 = (层数 $\times \log{n}$) $\times$ (每层工作量 $\times n^c$)

即：

$$T(n) = O(n^c \log{n})$$

根部更重

$n^c < f(n)$

如果$f(n)$增长的比$n^c$更快，说明你的递归过程越靠近上层，合并步骤越费劲。你的工作量主要集中在顶部。

因此，算法的复杂度由根节点决定：

$$T(n) = O(f(n))$$

我们来试一下如何将主定理运用到归并排序中吧。由于归并排序的递推式是：

$$T(n) = 2T(\frac{n}{2}) + \Theta(n)$$

我们不难发现归并排序的递推式满足主定理的要求，而且你也能提出关键信息诸如：$a = 2$, $b = 2$, $f(n) = \Theta(n)$。

接下来，我们要比较叶子的增长速度和每层合并的成本，也就是比较$n^{\log_{2}{2}}$和$f(n) = n$看看谁赢。

由于$n^{\log_{2}{2}}$ 就等于 $n$，于是我们落入了第二种情况，势均力敌。当递归树叶子的权重和根权重相当时，套用复杂度公式我们就可以得到

$$T(n) = O(n^{\log_{b}{a} \log{n}}) = O(nlogn)$$

选择问题

由于绝大多数的分治思想都是从归并排序开始讲起来的，所以对于大家来说已经是很司空见惯的内容了。有没有什么不一样的？

有的兄弟有的。在这一部分，我们来想象你有一个内容随机排列的数组。那么，你 如何在不完全排序的情况下，找到数组中第$k$大的数？

最简单直白的方法是将所有数字进行排序。如果我们想找第$k$大的数字，最笨的方式就是花$O(n \log{n})$的时间排序，然后直接访问第$k$个。

但是这样的问题是我们花了很多精力在无用功上，排序让我们知道所有数据的大小。在一场百米赛跑中，如果我们只想知道谁是第五名，我们不需要精确地直到第50名和51名谁快谁慢。即便使用最小堆的方法，在$k$很大的时候，并且在最坏情况下（$k = n/2$）的算法效率仍然是$O(n\log{n})$。

我们要追求$O(n)$的线性时间。

切分与丢弃

这一部分我们的解决方案和快速排序比较相像，但是有一个本质区别，那就是我们每次只需要递归枢轴的其中一边。这个算法我们通常称之为快速选择 (QuickSelect) 算法。

想象你面前有一堆杂乱的数字，排成数列。你的目标是寻找第$k$大的数。

第一步，我们随便从数字中选择一个数作为基准，我们把它叫做 枢轴$x$ (Pivot)。
第二步，我们将剩下的所有数字分成三堆：

$L$堆包含所有比$x$小的数字。
$M$堆包含所有等于$x$的数字。
$R$堆包含所有比$x$大的数字。

这一步只需要耗时$O(n)$，因为它只遍历了一遍数组。

第三步是这个算法最关键的一步。由于我们知道这三堆中各有多少个数字，我们就可以立刻判断出我们要找的那个“第$k$大”的数位于哪一堆。具体可以分为三种情况，看我娓娓道来：

情况A：

如果$R$堆的数量$|R|$已经大于等于$k$了，那么说明第$k$大的数肯定在这一组中。那么我们就可以直接舍弃$L$与$M$堆的内容，直接递归去$R$堆里继续寻找目标。
情况B：

如果$k$刚好落在$M$的范围内，即：

$$|R| < k \leq |R| + |M|$$

那么说明你这次选择的枢轴就是你的目标，可以直接return返回结果了。
情况C:

如果前两堆的数量都不够，那么只能说明目标只能在$L$堆里。这时候我们要递归寻找$L$中的目标。

需要注意由于我们已经排除了$|R|$个大值和$|M|$个中间值，因此我们要找的目标在$L$堆里面的序数就变了：我们下一步要寻找第$k - |R| - |M|$大的数值。

如果我们选择的枢轴非常理想，每次能够将数组完美减半，那么问题规模的减小速度非常可观：

$n$ → $n/2$ → $n/4$ → $n/8$...

直接将他们加起来，我们得到总工作量是：

$$n + \frac{n}{2} + \frac{n}{4} + ... = 2n$$

也就是$O(n)$。这就是快速选择的理想情况复杂度。

当你开始考虑最差情况时，就会出现问题。如果假设我们选择的枢轴每次都是最小的那个数，那么在每次递归中，$L$堆一定是空的，因此每次递归都只能从$R$排除一个数字。问题规模从$n$变成$n - 1$，$n - 2$ ...，总复杂度就会直接退化成$O(n^2)$。

所以我们的问题出现了，如何保证我们每次选择的枢轴，一定能够尽可能切掉大块数据？

中位数的中位数

为了保证算法在最坏情况下复杂度也是$O(n)$，我们需要一种确定性的方法来选择枢轴，而不是靠运气。

在这里我们使用Median of Medians算法来解决这个问题：

为了选出一个大概率位于中间的枢轴，我们首先进行下列步骤：

分组：我们将$n$个元素按每5个元素一组的规律，分成$n/5$个小组。
组内排序：对于每个小组中的5个数，我们寻找它们的中位数。由于只有5个数，寻找中位数的速度是极快的，因此我们将这步看作常数时间$O(1)$。
递归寻找枢轴：

现在我们拥有了这所有$n/5$个组各自的中位数，我们需要将这些数字拿出来，递归调用刚才的算法，找出这些数字中的中位数。这个“中位数组的中位数”，Median of Medians，就是我们要找的枢轴。

但是看起来这样的方法缺少依据啊？我们为什么要选择这样的计算方法？为啥非得是5？

我们来看看选出来这个最终枢轴是什么情况，就假设它是$x$吧。同时我们命名每一个组中选出来的那个中位数叫“组长”。

由于$x$是那$n/5$个小组组长的中位数，所以至少有一半的组长比$x$大。
而对于每一个比$x$大的组长，它那组里面至少还有2个组员比他自己大。

如果我们思考连带效应，把我们已知的内容总结一下：至少有一半的组长$\geq x$，并且每个这样的组里面至少有三个人 $\geq$ 这个组长 $\geq x$。

所以，在整个数组中，我们算出至少有$3 \times (n/10) = 3n/10$的人比$x$大。反过来同理，也至少有$3n/10$的人比$x$小。

这意味着无论$x$选的再偏，如果我们使用$x$去切分数组，最坏的一堆，包括$L$或者$R$，都最多只能包含$7m/10$个元素。不过为了计算方便，我们一般说这个最值近似$3n/4$。
只要我们保证每次递归都能稳定切掉恒定比例的数据，例如30%，递归树的深度就一定是$\log{n}$，且每层工作量按指数级递减，总和收敛于$O(n)$。

所以我们来把所有的开销加起来吧。

$$T(n) \leq T(n/5) + T(3n/4) + Cn$$

其中：

$T(n/5)$ 代指找组长的中位数所花费的递归成本
$T(3n/4)$ 代指在最坏情况下，递归去剩下的那一堆里寻找第$k$大的数的成本。由于我们保证了最好的一堆至少有$n/4$，那么我们就知道最坏的一堆最多包含$3n/4$的数据。
$Cn$ 代指分组，找每组中位数，以及最后划分$L, M, R$的线性工作量。

为了证明这样的策略始终有效，我们需要证明存在一个常数$K$，使得$T(n) \leq K \cdot n$

在这里我们先来试试假设$K = 20C$，看看能不能证明出来。

来用数学归纳法吧。首先我们假设所有小于$n$的数$m$，结论都成立，因此我们得到：

$$T(m) \leq 20C \cdot m$$

我们接下来需要验证$T(n)$是否也小于$20C \cdot n$。把假设带入递推式的右边：

$$T(n) \leq [20C \cdot (\frac{n}{5})] + [20C \cdot (\frac{3n}{4})] + C \cdot n$$

经过简单的代数运算把括号展开，我们最后得到：

$$T(n) \leq 4Cn + 15Cn + Cn$$

$$T(n) \leq 20Cn$$

$$\text{Q.E.D.}$$

得证了。但是你有想过为什么我们假设目标的系数是20？

20关联到这道题还能剩下多少余量来处理杂务。例如这次，我们直接将常数留成$K$，看看为了能让证明成立，$K$至少要是多少。

由于我们要证明复杂度$T(n)$是线性的$O(n)$，在数学上的意义还记得吗？寻找一个常数$K$使得$T(n) \leq K \cdot n$。前面的$C$属于题目已知的常数。这个常熟代表我们在做分组，找中位数，划分数组这些杂务必须要花费的固定代价，而$K$就是那个倍率。

递推公式：

$$T(n) \leq T(n/5) + T(3n/4) + Cn$$

如果把目标$T(n) \leq Kn$带入会发生什么？左边的预算变成$Kn$，右边的开销分子问题来衡量：第一个子问题花了$K \cdot (0.2n)$的开销，第二个花了$K \cdot (0.75n)$，杂务花了$C \cdot n$。

为了能让证明成立，预算必须要大于等于开销。因此我们可以证明这样一个不等式：

$$Kn \geq K(0.2n) +K(0.75n) +Cn$$

大家都有$n$，约掉：

$$K \geq 0.2K + 0.75K +C$$

合并$K$：

$$K \geq 0.95K + C$$

观察这个式子。这意味着当我们递归处理完子问题后，我们已经消耗了总预算$K$的95%，也就是说，我们只剩下5%的预算来分配给杂务$C$了。

不难得出：

$$K - 0.95K \geq C$$

$$K \geq 20C$$

这就是20的由来了。我们通过中位数查找把算法的规模缩减为原来的$1/5 + 3/4 = 0.95$，这就意味着通过每一层递归，相比原问题我们节省了5%的工作量。由于每一层只能节省5%的工作量，所以为了覆盖掉每一层固定$C$的这么多杂活，我们的总预算$K$就必须是$C$的20倍。

加速代数运算

如果说归并排序教会了我们“分治能维持效率”，那么这一部分我们来看看分治是如何暴力打破所谓“物理极限”。我们来看看分治思想是如何加速整数乘法和矩阵乘法的。

整数乘法 / Karatsuba算法

想象你要在计算机里计算两个超级大的整数相乘，计算机该如何进行计算？

就像我们使用的竖式乘法一样：如果是两个$n$位数，那么就一共需要进行$n \times n$次运算，复杂度是$O(n^2)$。对于超大整数来讲，这种计算方式太慢了。

我们起初尝试对这样的的计算引入分治法。把两个$n$位的数字$x, y$，切成左右两半。对于$x$来说，$a$代表高位，$b$则是低位。我们可得：

$$x = 2^{\frac{n}{2}} \cdot + b$$

同理：

$$y = 2^{\frac{n}{2}} \cdot + b$$

那么$xy$的乘积就是：

$$xy = (2^{n/2}a + b)(2^{n/2}c + d) = 2^n(ac) + 2^{n/2}(ad + bc) + bd$$

由于$2^n$本质上就是移位操作，在计算机中计算几乎没有任何成本，核心难点是我们如何计算$ac$, $ad$, $bc$, $bd$。

因此，我们尝试递归地计算这四个规模为$n/2$的乘法，可以得到递推式：

$$T(n) = 4T(n/2) + O(n)$$

根据主定理， $a = 4$, $b = 2$, $\log_{2}{4} = 2$

因此，$T(n) = O(n^2)$

最后算下来发现复杂度还是 $O(n^2)$，根本没有任何提升。

后来数学家发现为了打破$O(n^2)$的瓶颈，我们需要减少乘法的次数，也就是让那个 $a = 4$ 变小。

观察中间的那一项 $(ad + bc)$，实际上我们只需要知道它们的和就可以了，不需要真的一定要计算出$ad$ 和$bc$。

所以我们尝试从 $(a + b)(c + d)$展开：

$$(a + b)(c + d) = ac + ad + bc + bd$$

$$ad + bc = (a + b)(c + d) - ac - bd$$

由于$ac$和$bd$我们本身就要算，现在我们只需要计算三次乘法就可以了：

$P_1 = ac$
$P_2 = bd$
$P_3 = (a + b)(c + d)$

那么中间项$(ad + bc)$就可以直接通过$P_3 - P_1 - P_2$得到了。

所以现在我们的主定理中$a$的系数由4变成了3：

$$T(n) = 3T(n/2) + O(n)$$

根据主定理我们知道复杂度降低到了$O(n^{1.585})$，相比$O(n^2)$，已经是一个非常大的提速了。

矩阵乘法 / Strassen算法

同样的剧本在矩阵乘法这边又上演了一次。

如果我们需要让两个$n \times n$的矩阵$A$, $B$相乘，最终得到结果$C$，按照暴力做法硬算的复杂度是$O(n^3)$。

那么如果我们将矩阵切分成四块$n/2 \times n/2$的子矩阵：

$$
\begin{pmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{pmatrix}
\times
\begin{pmatrix} B_{11} & B_{12} \ B_{21} & B_{22} \end{pmatrix}
$$

根据矩阵乘法规则，我们需要计算八个子矩阵的乘积。使用递归的话就可以得到递推式：

$$T(n) = 8T(n/2) + O(n^2)$$s

根据主定理最后得到复杂度仍然是$o(n^3)$s。

在1969年，Strassen发现实际上我们根本不需要8次乘法，相反，只需要进行七次相乘和若干个加减法就足够了。我们不需要掌握这个算法具体是怎样一个流程和步骤，看看就好。

在上面子矩阵的基础上，我们定义7个中间矩阵：

$$
\begin{aligned}
M_1 &= (A_{11} + A_{22})(B_{11} + B_{22}) \
M_2 &= (A_{21} + A_{22})B_{11} \
M_3 &= A_{11}(B_{12} - B_{22}) \
M_4 &= A_{22}(B_{21} - B_{11}) \
M_5 &= (A_{11} + A_{12})B_{22} \
M_6 &= (A_{21} - A_{11})(B_{11} + B_{12}) \
M_7 &= (A_{12} - A_{22})(B_{21} + B_{22})
\end{aligned}
$$

利用这 7 个结果，可以拼出最终的乘积矩阵 $C = A \cdot B$：

$$
\begin{aligned}
C_{11} &= M_1 + M_4 - M_5 + M_7 \
C_{12} &= M_3 + M_5 \
C_{21} &= M_2 + M_4 \
C_{22} &= M_1 - M_2 + M_3 + M_6
\end{aligned}
$$

如果矩阵的规模仍非常巨大，就对每个子矩阵递归继续应用Strassen算法就行了。当规模缩小到一定程度（比如 $n$ 很小），直接使用普通矩阵乘法计算就行。

因此，我们可以得到递推式：

$$T(n) = 7T(n/2) + O(n^2)$$

使用主定理，我们计算出叶子的权重大概为$n^{\log_{2}{7}} \approx n^{2.808}$，根部为$n^2$.因此，我们得到Strassen算法的复杂度为 $O(n^{2.808})$。

运用这个算法，我们就可以在大规模矩阵运算中显著减少计算量。

分治这一部分就讲完了。最后的最后，

我恨递归。

两个 $n \times n$ 的矩阵 $A$ 和 $B$ 相乘，得到 $C$。
暴力做法是 $O(n^3)$。
如果我们把矩阵切成 4 块 $n/2 \times n/2$ 的子矩阵：
$$
\begin{pmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{pmatrix}
\times
\begin{pmatrix} B_{11} & B_{12} \ B_{21} & B_{22} \end{pmatrix}
$$
根据矩阵乘法规则，我们要计算 8 个子矩阵的乘积（$A_{11}B_{11}, A_{12}B_{21}$ 等等）。
递归式：$T(n) = 8T(n/2) + O(n^2)$（加法是 $n^2$）。
主定理：$\log_2 8 = 3$。
结论： 依然是 $O(n^3)$。没用。

2. Strassen 的魔法 (Slide 50)

Volker Strassen 在 1969 年发现了一个惊人的事实：你不需要 8 次乘法，7 次就够了！

他在 Slide 50 列出了一堆看起来像天书一样的公式（$M_1$ 到 $M_7$）。你不需要背诵这些公式（就像你不需要背诵圆周率后100位）。
你只需要理解他的核心思想：
他构造了 7 个复杂的中间矩阵（$M$），每个 $M$ 都是通过一次子矩阵乘法得到的。
然后，通过在这个 7 个 $M$ 之间做加减法，神奇地还原出了结果矩阵 $C$ 的四个部分。

代价与收益：

代价： 加法和减法的次数变多了（Slide 50 说用了 18 次加减法）。但这影响的只是 $O(n^2)$ 前面的常数。
收益： 乘法次数从 8 降到了 7。这改变了递归树的分支数量，直接改变了复杂度指数。

3. 最终分析

递归式：
$$T(n) = 7T(n/2) + O(n^2)$$

主定理比较：

叶子：$n^{\log_2 7} \approx n^{2.808}$
根部：$n^2$
显然 $2.808 > 2$，叶子占主导。
复杂度 = $O(n^{2.808})$。

这就是为什么 Slide 51 说这是一个里程碑。虽然 $2.8$ 和 $3$ 看起来差的不多，但在数学上，它打破了 $O(n^3)$ 是矩阵乘法下界的迷信。后续的算法（如 Coppersmith-Winograd）只是在 Strassen 的思路上继续把指数往下压。

FINAL STOP & CHECK

至此，我们已经讲完了整份课件。

总结一下这一章的“代数分治”：

直接分治往往没有用： 如果你只是把 $n^2$ 的问题拆成 4 个 $n/2$ 的问题，或者把 $n^3$ 拆成 8 个，复杂度是不会变的。
核心在于减少子问题数量 ($a$)： Karatsuba 把 4 变成 3，Strassen 把 8 变成 7。
手段是“加法换乘法”： 利用代数恒等式，增加廉价的加减法操作，来节省昂贵的递归乘法操作。

对于这最后一部分，或者整份课件的任何内容，你还有什么疑问吗？

分治法的核心与归并排序

分治法

归并排序

归并递推式

数学推导与严谨性证明

万能公式：主定理

选择问题

切分与丢弃

中位数的中位数

最近点对问题

常数邻居原则

加速代数运算

整数乘法 / Karatsuba算法

矩阵乘法 / Strassen算法

2. Strassen 的魔法 (Slide 50)

3. 最终分析