算法分析与设计之分治算法

---

• 💂 个人主页:风间琉璃
• 🤟 版权: 本文由【风间琉璃】原创、在CSDN首发、需要转载请联系博主
• 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦

---

前言

提示：这里可以添加本文要记录的大概内容：

---

预览：

一、分治算法divide and conquer

1.1 分治定义

分治算法（divide and conquer）的核心思想：分而治之 ，即将原问题划分成 k 个规模较小，并且结构与原问题相似的独立子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治所能解决的问题一般具有以下几个特征：

• 该问题的规模缩小到一定的程度可以直接求解

  绝大多数问题都可以满足该特征，因为问题的计算复杂性一般是随着问题规模的增加而增加；

• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质

  这个特征是应用分治算法的前提，也是大多数问题可以满足的，此特征反映了 递归思想 的引用；

• 利用该问题分解出的子问题的解可以合并为该问题的解

  能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心算法或动态规划法；

• 该问题所分解出的各个子问题是相互独立的，即**子问题之间不包含公共的子问题 **

  第四条特征涉及到 分治的效率，如果各子问题是不独立的，则分治要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治，但 一般用动态规划较好。

分治算法是一种通过递归的方式将问题分解为多个子问题，然后分别解决这些子问题，最后合并子问题的解以得到原问题解的方法。分治算法一般都比较适合用递归来实现，通常由以下三个步骤组成：

1. 分解（Divide）：将原问题划分为若干个规模较小但结构与原问题相同的子问题。

2. 解决（Conquer）：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。

3. 合并（Combine）：将子问题的解组合成原问题的解，自底向上逐步求出原来问题的解。

它的一般的算法设计模式如下：

Divide-and-Conquer(P)
{// 如果问题 P 的规模小于或等于阈值 n0（即问题足够小），则直接用 ADHOC 算法解决// ADHOC(P) 是用于处理小规模问题的基本算法if(|P| ≤ n0) ADHOC(P); // 将问题 P 拆分为 k 个子问题 P1, P2, ..., Pk. 每个子问题的规模比原问题更小，通常按照某种划分规则进行分解divide P into smaller subinstances P1,P2,...,Pk;//遍历所有 k 个子问题，逐个处理for(i=1;i<k;i++){yi ← Divide-and-Conquer(Pi)  //递归调用 Divide-and-Conquer(Pi) 解决子问题 Pi，将其结果存储在 yi 中}// 将所有子问题的解 y1, y2, ..., yk 通过合并算法 MERGE 组合为原问题 P 的解return MERGE(y1, y2, ..., yk);
}

|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC§是用于处理小规模问题的直接算法。这是分治算法的终止条件，也是递归的基本情形。当问题规模小到不需要进一步分解时，即当P的规模不超过n0，可以用算法ADHOC§求解。

Divide-and-Conquer(Pi)递归调用表示继续将子问题划分为更小的子问题，直到这些子问题的规模小于或等于阈值 n0时，使用 ADHOC 方法直接解决。这是分治法中的“治”的部分。MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。

参考教材：

1.2 分治法的复杂性分析：递归方程

分治算法的复杂度通常由递归关系式来表示。**假设每次分解后生成 a个子问题，每个子问题的规模是原问题的 $1/b$，即每个子问题的大小为$\mid P\mid /b$，**而合并过程的复杂度为$f(n)$个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有递归关系式为：
$$T(n)=aT(n/b)+f(n)$$
这个关系式的解可以用主定理（Master Theorem）来分析，主定理根据 a、b 和f(n)的值给出了不同情况下的复杂度。但是并不是所有的递归方程都可以使用主定理求解，对于合并代价是非多项式、分解不符合$aT(n/b)$的形式主定理不适应。此时可以考虑使用迭代法和递归树法求解。

1.2.1 主定理

对于如下的递归表达式可以通过比较$f(n)$和$n^{lo{g}_{b}a}$的大小进行判定，谁大取谁，相等乘logn,判断顺序推荐1->3->2。

对于第三种情况f(n)大，但满足前一个条件还需要满足正则条件$af(n/b)\le cf(n),c<1$，需要找到一个满足条件c这个定理才适用。

• $T(n)=9T(n/3)+n$
  $$\begin{gathered} a=9,b=3,n^{lo{g}_{3}9}=n^2\ge f(n)=n; \\ (n^2大，直接取n^2)通过主定理得出：T(n)=O(n^2) \end{gathered}$$

给定递归式：$T(n)=2T\left(\frac{n}{2}\right)+f(n),\text{其中 }f(n)=n\log n$。

${\log }_{b}a={\log }_{2}2=1$,而$f(n)=n\log n$，大于$n^{{\log }_{2}2}=n$。是否满足第三种情况呢？$f(n)/n^{lo{g}_{b}a}=nlo{g}_{b}a/n=logn<n^{ϵ}$,f(n)大于 ，但不是多项式地大于,则不能用主方法求解该递归式。这里要求$f(n)/n^{lo{g}_{b}a}=nlo{g}_{b}a/n=n^{ϵ}$,因此只能使用迭代法或者递归树。

不适用主定理的情况：

• 子问题数量 a不是常数，比如动态变化。

  $T(n)=nT\left(\frac{n}{2}\right)+n^2$，子问题数量 a=n，不是常数。无法直接用主定理，因为a是输入规模的函数。

• 子问题数量a小于1

  $T(n)=\frac{1}{2}T\left(\frac{n}{2}\right)+n^2$，子问题数量 a = 1/2，理论上少于 1，这种形式不符合递归定义（实际问题通常不这样设置）。若假设 a 的实际意义是问题的分布比 1 小一半，则递归展开的分量逐渐减少，主定理仍不适用。

• 子问题的划分和合并代价不能简化为单一的多项式。

  $T(n)=2T\left(\frac{n}{2}\right)+n\log n$。

1.2.2 递归树法

$T(n)=2T(n/2)+n^2$使用递归树。

所以总的时间复杂度为
$$\begin{array}{c}\begin{array}{rl}T(n)=& \frac{n^2}{2^0}+2(\frac{n^2}{4})+4(\frac{n^2}{16})+\cdots +2^{{\log }_{2}n}(\frac{n^2}{2^{{\log }_{2}n+{\log }_{2}n}})({\log }_{2}n\text{ 层})\\ =& n^2(1+\frac{1}{2}+\frac{1}{2^2}+\cdots +\frac{1}{2^{{\log }_{2}n}})\\ =& n^2(\frac{1-(\frac{1}{2}{)}^{{\log }_{2}n+1}}{1-\frac{1}{2}})\\ =& 2n^2-n\end{array}\end{array}$$
所以$T(n)=O(n^2)$。

结论：

递归深度是由每次递归缩小问题规模的因子b决定的，因此递归的深度为$ \log_b n$。

即使每次递归会产生多个子问题（比如 3 个），这只会影响递归树的宽度，而深度不变。

补充：

对于一个无穷等比级数：$S = a + aq + aq^2 + aq^3 + \cdots $。其中：$a$是首项，$q$是公比，且 ( |q| < 1 )。

该无穷等比级数的和 ( S ) 为：
$$S=\frac{a}{1-q},\text{当 }|q|<1$$

1.2.3 迭代法

迭代法（又称递归展开法）是一种通过逐步展开递归方程，分析每一层递归调用的代价来求解递归关系的方法。它的核心思想是通过展开递归关系，观察每一层的代价，直至达到递归的基准条件，从而得出递归的总体代价（时间复杂度）。

求解$T(n)=2T\left(\frac{n}{2}\right)+n\log n$

用递推展开法：

• 展开递归：
  $$T(n)=2\left(2T\left(\frac{n}{4}\right)+\frac{n}{2}\log \frac{n}{2}\right)+n\log n$$

  $$T(n)=4T\left(\frac{n}{4}\right)+n\log \frac{n}{2}+n\log n$$

• 继续递归 k 次，得：
  $$T(n)=2^{k}T\left(\frac{n}{2^k}\right)+\sum _{i=0}^{k-1}{2}^i\cdot \frac{n}{2^i}\cdot \log \frac{n}{2^i}$$

• 当$k=\log n$时，问题规模为 1，得 T(1)=O(1)：$T(n)=O(n{\log }^{2}n)$。

每次递归将问题规模缩小一半，因此递归树的深度（层数）是 ${\log }_{2}n$，即从 n缩小到 1 需要${\log }_{b}n$次递归，递归深度是由每次递归缩小问题规模的因子b决定的，

二、典型例题

2.1 Mergesort

排序问题：给定n个元素，要求将它们重新排列为升序或降序的顺序。

归并排序是一种经典的 分治法 排序算法，以下是其具体步骤：

1. 分解（Divide）：将数组划分为两个相等或接近相等的子数组。
2. 递归排序（Conquer）：对每个子数组递归调用归并排序，直到子数组的大小为 1（自然是有序的）。
3. 合并（Combine）：将两个有序的子数组 合并 为一个有序数组。

如何高效合并两个有序列表，使用线性时间完成。给定两个有序数组A和B，需要合并它们为C，保持C的元素有序。
假设：A长度为m，B长度为n。

合并算法过程：

1. 使用两个指针i和j，分别指向A和B的起始位置。
2. 比较A[i]和B[j的值，将较小的元素复制到临时数组C中，并移动相应指针。
3. 当一个数组的指针到达末尾时，将另一个数组的剩余元素直接复制到C 中。

每次比较后指针移动，因此比较次数最多为 m+n，整体复杂度为O(m+n)。

归并排序的时间复杂度T(n)表示对大小为n的输入进行归并排序所需的比较次数。它由以下递归公式定义：

将数组划分为两个大小为n/2的子数组，时间复杂度为O(1)。将两个大小为n/2的子数组合并为一个数组，所需时间为O(n)。T(n)为总的比较次数，由分解、递归、合并三部分组成。总时间复杂度为$O(n\log n)$，无论最优、平均还是最差情况。证明方法包括展开递归、递归树分析和主定理法，明显直接套用主定理最简单。

2.2 Counting Inversions

逆序对：如果i < j，但$a_i>a_j$，那么(i, j)是一个逆序对。如下图在序列1，3，4，2，5中3-2和4-2构成两个逆序对。

直接检查所有的逆序对，其时间复杂度为$O(n^2)$。利用分治法求解逆序对，其时间复杂度为$O(n\log n)$。

• Divide：将数组分为两部分，左半部分：从起始位置到中点；右半部分：从中点到结束。通过递归处理这两个子数组，分别计算其中的逆序对。

• Conquer：对左右子数组递归地进行处理，统计每部分的逆序对数量。

• Combine：合并左右子数组时，统计跨越左右部分的逆序对数量，逆序对中一个来自左边数组，另一个来自右边数组。

最终的逆序对数量等于：$\text{total inversions}=\text{left inversions}+\text{right inversions}+\text{cross inversions}$

前提条件：Merge-and-Count函数已经假设A和B两个子数组已经排序。

后置条件：Sort-and-Count返回一个排序后的数组，并且统计该数组中的倒排对的数量。

递归调用的深度是$O(\log n)$, 因为在每次递归时，我们将数组分成两个子数组，所以递归的深度是对数级别的，即$O(\log n)$。每层递归的合并操作时间复杂度是 O(n)，每次合并两个数组时，时间复杂度是线性的，因为每个元素都会参与合并过程。因此，整体的时间复杂度是$O(n\log n)$。

2.3 棋盘覆盖

残缺棋盘是一个有$2^k\times 2^k(k\ge 1)$个方格的棋盘，其中恰有一个方格残缺。下图给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。

这样的棋盘称作“三格板”或者“L”型骨牌，残缺棋盘问题就是用这四种三格板覆盖更大的残缺棋盘。在覆盖中要求：

• 两个三格板不能重叠
• 三格板不能覆盖残缺方格，但必须覆盖其他所有方格

利用分治法递归地解决问题：

• Divide棋盘分割:将棋盘划分为四个大小为$2^{n-1}\times 2^{n-1}$的子棋盘。确定残缺点所在的子棋盘，使用对应的“L”型骨牌覆盖其余三个子棋盘的交界方格，可使另外三个子棋盘转化为独立子问题，以标记新的虚拟残缺点，保证递归的完整性。因为要保持子问题和原问题具有相同的结构。

• Conquer: 对每个子棋盘递归应用相同的覆盖策略，直到棋盘大小为$2\times 2$ 时（递归的基线），可以直接覆盖。

• Combine: 当递归返回时，所有子棋盘都已覆盖，最终完成整个棋盘的覆盖。

分析：

（1）以k=2时的问题为例，用二分法进行分解得到用双线划分的四个k=1的棋盘，如下图所示。==但是分治算法适用问题特点是子问题与原问题具有相似结构。==但这四个棋盘，并不都是与原问题相似且独立的子问题。第1个子问题与原问题相似(因为残缺方格在原图的左上部，使得第一个子图中有一个残缺方格) 。而右上角、左下角和右下角三个子棋盘(也就是图中标识为2、3、4号子棋盘)，并不是原问题的相似子问题，自然也就不能独立求解。

为了保证分治法能够顺利应用到所有子问题中，我们可以在每个递归步骤中进行特殊的处理：当我们划分棋盘时，可以检查每个子棋盘的残缺方格位置。对于每个子棋盘，我们需要根据其具体情况来决定如何放置 “L” 型骨牌以及如何处理残缺格子。

• 对于第一个子问题（左上角），它的处理方式与原问题一致，因此可以直接用分治法解决。

• 对于其他三个子问题，我们需要通过增加额外的覆盖步骤来保证它们的残缺格子能够被正确处理。

使用一个①号三格板(图中阴影)覆盖2、3、4号三个子棋盘的各一个方格；

把覆盖后的方格，也看作是残缺方格(称为“伪”残缺方格)，这时的2、3、4号子问题就是独立且与原问题相似的子问题了。

（2）推广至k=2其它情况：

• 当残缺方格在第1个子棋盘时，用①号三格板覆盖其余三个子棋盘的交界方格
• 当残缺方格在第2个子棋盘时，则首先用②号三格板进行棋盘覆盖；
• 当残缺方格在第3个子棋盘时，则首先用③号三格板进行棋盘覆盖；
• 当残缺方格在第4个子棋盘时，则首先用④号三格板进行棋盘覆盖；

这样处理后可使另外三个子棋盘转化为独立子问题。

（3）推广至k=1,2,3,4,….：

将$2^k\times 2^k$棋盘分割为4个$2^{k-1}×2{k-1} $子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为将这3个无特殊方格的子棋盘转化为特殊棋盘，可用一个三格板覆盖这3个子棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。

设T(k)是覆盖一个$2^k\times 2^k$棋盘所需时间，从算法的划分策略可知，T(k)满足如下递推式：（注意这里k是在指数上）
$$
T(k)=\left{\begin{array}{l}
O(1) ;k=0\
4 T(k-1) ; k>0 \

\end{array}\right.
$$
解此递推式可得$T(k)=O(4^k)$。由于覆盖一个$2^k\times 2^k$棋盘所需的骨牌个数为$(4^k-1)/3$，所以，该算法是一个在渐进意义下的最优算法。

2.4 最大和数组

最大子数组问题是一个经典的分治法问题（也可以动态规划），目标是在一个数组中找到具有最大和的连续子数组。例如，数组[−2, 1, −3, 4, −1, 2, 1, −5, 4]的最大和子数组是[4, −1, 2, 1]，其和为6。

分治法思路：通过将数组分成两部分来递归求解问题，核心思想是将问题划分为以下三种情况：

• 最大子数组位于左半部分。

• 最大子数组位于右半部分。

• 最大子数组跨越中点。

最终通过递归计算左、右两部分的最大子数组，以及跨越中点的最大子数组，取三者中的最大值作为结果。

算法步骤：

• Divide将数组分为两部分：左半部分$A[left\dots mid]$，右半部分$A[mid+1\dots right]$。

• Conquer：递归地求解左/右半部分的最大子数组。对于跨越中点的最大子数组，其最大数值必然包含中点，而且是从左边某个位置到右边某个位置的连续子数组。可以分别从中点向左和向右扩展，找到左半部分和右半部分的最大和，然后将两部分相加。比如求左边部分的最大和，从中点mid向左遍历，逐步累加元素，直到当前划分子问题的左边界。在累加过程中，记录当前的最大累加和。

• Combine：取左半部分、右半部分以及跨越中点的最大子数组的最大值作为结果。

时间复杂度分析：分解时间每次递归将数组分为两部分，分解操作耗时 O(1)。合并时间计算跨越中点的最大子数组需要 O(n)的时间。每次递归调用两次子问题，每个子问题的规模是原问题的一半：$T(n)=2T\left(\frac{n}{2}\right)+O(n)$。根据主定理，递归关系的时间复杂度为$O(n\log n)$。

2.5 Closest Pair of Points

最近点对问题 (Closest Pair of Points) 是一个经典的几何问题，给定平面上的n个点，要求找出距离最近的两个点对。

暴力解法：检查所有的点对p和q，计算它们之间的欧几里得距离，选择最小的那个。对于n个点，所有的点对数量是 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$，因此总的比较次数是$O(n^2)$。

对于二维平面上的点集，分治法是一种更高效的解决方案。

使用四象限划分的设想：将平面分成四个象限，每个象限对应一个子区域，并递归处理每个区域中的点集。这种方法的问题在于，无法保证每个象限中的点数是均匀分布的（即每个象限中有大约 n/4个点）。例如，如果所有点都位于第一象限，那么其他三个象限将为空。那么分治算法无法有效缩小问题规模，递归深度会增大，失去分治的效率。理论上的时间复杂度可能退化到接近 $O(n^2)$。

按 x-坐标排序：

• Divide划分：按x-坐标对点集P排序。找到x-坐标的中位数，并用它画一条垂直分割线L，将点集划分为左右两部分，$P_L$位于L左侧或包含中位数的点；$P_R$：位于L右侧的点。确保左右点集大致均匀（约n/2 点）。

  

• Conquer（递归解决子问题）:分别递归计算$P_L$和$P_R$的最近点对及其最小距离：

  • $d_L$：左半部分的最近点对距离。
  • $d_R$：右半部分的最近点对距离。

  当前最近距离$d=\min (d_L,d_R)$。

• Combine（合并）:检查跨越 L 的点对是否有更小的距离。筛选与分割线L距离小于d的点，构成带状区域S。按y-坐标排序S中的点。逐一检查S中每个点与最多7个距离较近的点之间的距离，更新最小距离$d_S$。取三者中的最小值：$d=\min (d_L,d_R,d_S)$。

下面考虑跨越分割线L的点对，在最近点对问题中，假设两部分点的最近距离小于$\delta$。以下是优化后寻找最近点对的方法，基于几何观察和带状区域的性质。算法思想：只需检查位于距离分割线L小于$\delta$的点，形成一个宽度为$2\delta$的带状区域（strip）。然后对带状区域内的点按y-坐标排序，使得检查过程可以通过较少的点对计算完成。几何观察表明，带状区域中一个点只需与排序列表中后 7 个点比较即可，无需检查所有点对，如果又暴力比较的话，时间复杂度又为$O(n)$，因此需要采取上面的措施。

• 筛选带状区域的点：从原始点集中筛选出与分割线L的水平距离小于$\delta$的点，形成带状区域S： S = { p ∈ P ∣ ∣ x p − x L ∣ < δ } S = \{p \in P \mid |x_p - x_L| < \delta\} S={p∈P∣∣xp​−xL​∣<δ}，筛选复杂度为 O(n))。

• 按y-坐标排序：对带状区域中的点按y-坐标排序。由于递归过程中原始点集已排序，因此排序复杂度为$O(n\log n)$。

• 检查 y-排序列表中的点对：遍历排序后的点列表，对每个点$p_i$，只检查$p_i$后至多 7 个点的距离。更新当前最小距离及对应点对。

令 $s_i$ 为$2\delta$-带状区域中按y-坐标排序的第i个点。
**结论：**如果 $|j-i|>7$，则$s_i$和$s_j$之间的距离至少是$\delta$。

考虑宽为$2\delta$，高为$\delta$的矩形区域R，其中点$s_i$的y-坐标是矩形的底部。矩形的宽为$2\delta$，因为这是左右分割线两侧各延伸$\delta$的范围。如果点$s_j$超出矩形 R 的上边界，则它与$s_i$ 的垂直距离必然大于$\delta$，不可能是最近点对。因此，只需检查在矩形R内的点。

将 R分割为$2\times 4=8$个正方形区域：每个正方形的边长为$\delta /2$。任意两个点在同一个正方形内的距离小于$\delta /\sqrt{2}$。==但由于最近点对的距离至少为$\delta$，==一个正方形内最多容纳 1 个点。R 中的 8 个正方形，每个正方形至多有 1 个点。因此，除了点$s_i$本身，矩形内最多还有 7 个其他点。

算法首先将点集按x-坐标排序，并递归地将点集分成左右两半，分别求解左右子集的最近点对距离${\delta }_1$ 和 ${\delta }_2$，然后合并结果得到 $\delta =\min ({\delta }_1,{\delta }_2)$。在合并阶段，仅需检查位于分割线附近宽度为 $2\delta$的带状区域内的点，并对按y-坐标排序的点集中每个点与其后至多7个点比较距离，更新$\delta$。

时间复杂度$T(n)=O(nlo{g}^{2}n)$。Shamos 1975 定理指出：使用分治法的最近点对算法，通过**在初始时对点集按 x-和 y-坐标排序，并在递归中通过归并排序维护预排序列表，**可以将总时间复杂度优化到$O(n\log n)$。

2.6 Karatsuba算法（大整数的乘法）

给定两个 n 位整数 x 和 y(x,y都是二进制)，计算 x × y。

可以通过Karatsuba算法实现，它是一个快速的整数乘法算法，将原本的乘法问题分解为更小的子问题，从而减少计算复杂度。

分治法乘法步骤（基于二进制）：

1.拆分整数

假设有两个 n 位的二进制整数x和y，将它们拆分为两部分
$$\begin{gathered} x=x_1\cdot 2^{n/2}+x_0 \\ y=y_1\cdot 2^{n/2}+y_0 \end{gathered}$$
其中：

• $x_1$ 和 $x_0$ 分别是x的高位和低位（高n/2位和低n/2位）
• $y_1$ 和 $y_0$ 分别是b的高位和低位。

通过这样的拆分，可以把两个 n 位数的乘法分解为四个较小数的乘法运算，拆分可以类别于10进制，这样比较好理解。

2.子问题分解

根据二进制的乘法规则，原始的乘积$a\times b$可以分解为以下四部分
$$xy=(x_1\cdot 2^{n/2}+x_0)(y_1\cdot 2^{n/2}+y_0)$$
展开后
$$xy=x_1\cdot y_1\cdot 2^n+(x_1\cdot x_0+x_0\cdot y_1)\cdot 2^{n/2}+x_0\cdot y_0$$
这个公式中有四个乘法：$x_1\times y_1$、$x_1\times y_0$、$x_0\times y_1$、$x_0\times y_0$。

3.优化（Karatsuba 分治法）

为进一步优化，可以减少乘法次数。根据 Karatsuba 算法，可以减少到三个乘法：

4.递归求解

每一步乘法都可以递归地按照相同的方式进行分治。最终当子问题的规模足够小（例如规模为 1 时），可以直接通过位运算得到结果。

传统的乘法复杂度是$O(n^2)$，因为有n位，每两位都要相乘。如果不经过第三步的优化，分治后的复杂度还是$O(n^2)$。

通过分治法，特别是 Karatsuba 算法，可以将两个二进制整数的乘法复杂度从$O(n^2)$降到$O(n^{1.585})$。这通过将大整数分割为较小的子整数，并递归计算它们的乘积，同时减少直接乘法运算次数来实现。

2.7 Matrix Multiplication 矩阵乘法

矩阵乘法的分治法通过将大矩阵分解为小矩阵递归计算，从而减少复杂度。

• Divide：将两个$n\times n$的矩阵A和B分成 $\frac{n}{2}\times \frac{n}{2}$的子矩阵：
  $$A=\left[\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right],B=\left[\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right]$$

其中：$A_{11},A_{12},A_{21},A_{22}$是矩阵A 的 4 个子矩阵，大小均为 $\frac{n}{2}\times \frac{n}{2}$；$B_{11},B_{12},B_{21},B_{22}$是矩阵B的 4 个子矩阵。

• Conque递归计算 8 个子矩阵的乘积：

$$C_{11}=A_{11}{B}_{11}+A_{12}{B}_{21},C_{12}=A_{11}{B}_{12}+A_{12}{B}_{22}{C}_{21}=A_{21}{B}_{11}+A_{22}{B}_{21},C_{22}=A_{21}{B}_{12}+A_{22}{B}_{22}$$

通过递归方式计算这些$\frac{n}{2}\times \frac{n}{2}$的矩阵乘法。

• Combine将上述结果组合成最终矩阵 C：
  $$C=\left[\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right]$$

这里需要进行 4 次矩阵加法。

现在来分析一下时间复杂度，分解时间复杂度为O(1)，只需将矩阵分块。求解需要递归计算 8 次$\frac{n}{2}\times \frac{n}{2}$的矩阵乘法，每次乘法复杂度为 $T\left(\frac{n}{2}\right)$。合并需要$O(n^2)$的时间进行矩阵加法。递归关系为：$T(n)=8T\left(\frac{n}{2}\right)+O(n^2)$。根据主定理，解得：$T(n)=O(n^3)$

改进方向：Strassen 算法通过减少递归中矩阵乘法的次数（从 8 次减少到 7 次），将时间复杂度降低到 $O(n^{{\log }_{2}7})\approx O(n^{2.81})$。

Strassen算法引入了 7个中间变量（通过标量乘法计算）,然后通过这些中间变量，计算最终矩阵 C的元素。通过递归，将矩阵分成更小的子矩阵，使用Strassen方法计算。由于只需 7次乘法而非传统的8次，时间复杂度递归关系变为：$T(n)=7T\left(\frac{n}{2}\right)+O(n^2)$。算法伪代码如下：

结束语

感谢阅读吾之文章，今已至此次旅程之终站 🛬。

吾望斯文献能供尔以宝贵之信息与知识也 🎉。

学习者之途，若藏于天际之星辰🍥，吾等皆当努力熠熠生辉，持续前行。

然而，如若斯文献有益于尔，何不以三连为礼？点赞、留言、收藏 - 此等皆以证尔对作者之支持与鼓励也 💞。