数据结构 2025.6.26

chenzhiyv · 2025-06-26 19:50:46 · 个人记录

归约

当A问题是B问题的子问题，就是B题的代码能原封不动地用来通过A问题时，我们将B问题认为是难于A问题的。 这时候，当我们解决了B问题时，A问题也被解决了，这就叫做将A问题归约到B。

同时，有一些问题能够经过转化变成另一些问题，我们就叫做A问题等价于B问题

复杂度下界

当我们对一个问题完成归约后，如将B问题归约或转化为A问题，则解决A问题的时间复杂度不能低于B问题。

如矩阵乘法（这里认为矩阵乘法的复杂度是 O(n^3) 的， 01 矩阵乘法与 min/max +/ \times 矩阵乘法，即定义矩阵乘法为 c_{i,j} = min_k( a_{i,k} + b_{k,j} ) 均是这个复杂度）。树上数颜色难于 \sqrt n /2 \times \sqrt n /2 的矩阵乘法，具体转化如下：

1. 首先，建立一个树高为 \sqrt n/2 的树，这个树有 \sqrt n/2 条链，将链分为前一半和后一半，前一半对应前一个矩阵，后一半对应后一个矩阵，我们这样规定链上的颜色：

   当对应的 \sqrt n \times \sqrt n 的矩阵上这个点的值为 0 时，树链上这个点的颜色是任意赋得一个与其他点均不同的一个颜色。

   当对应的矩阵上的点为 1 时，此时规定在第 i 条链的 j 个点上，在前一部分颜色是矩阵的 j ，后一部分是矩阵的 i 。

   此时， c_{i,j} = \sum_{k} [a_{i,k}=1][b_{k,j}=1] ，等价于链上有多少个相同的颜色

2.每次查询一条两边都是 \sqrt n /2 长的树链，这样树链上的颜色就是 2 * \sqrt n /2 - 前后链上颜色相同的数量。当询问有 O(n) 量级的时候，问题就变成一个完整的矩阵乘法，复杂度不能低于 {\sqrt n /2 }^3 ，上界为 O( n^{1.5} ) ，即 O(n \sqrt n)

其余问题可以类似证明，问题见ppt即博客

复杂度平衡

这里了解即可，具体内容有 log 分块，如四毛子，将块分组，分别预处理，降低复杂度，具体见题。