时间复杂度分析

Published: February 20, 2020 by Daltao

• Categories:
• techonology 15

• Tags:

启发式合并技巧及应用

考虑这样一个问题，有一棵$n$个顶点的树，树上每个顶点都有对应的颜色。现在要求回答，以每个顶点为根的子树中存在多少不同颜色的顶点。

我们可以想到这样一个方法，就是为每个顶点记录子树中所有颜色组成的集合。但是当每个顶点的颜色都不同，且树退化成一条链表的时候，集合的总大小就达到了$O(n^2)$。

但是我们可以在处理到某个顶点的之前处理所有子结点，而子结点处理完后不必在维护颜色集合信息，父结点可以直接继承某个子结点的颜色集合，之后将其余子结点的颜色集合一起做并集操作即可。

但是这样做的时间复杂度是多少呢？很显然在最坏的情况下还是$O(n^2)$，原因是我们可能一直继承了大小最小的那个子树的信息。

这里我们可以不必考虑继承哪个集合，这里我们修改集合的合并过程，原先是将某个集合向另外一个集合合并，但是这里我们修改成让较小的集合向较大的集合合并。

所谓的启发式合并就是指每次都让较小的数据合并到较大的数据。

下面我们来证明启发式合并的时间复杂度$O(n\log_2n)$（这里用哈希表维护集合）。实际上我们从每个顶点的颜色出发，我们发现每次这个颜色被并入到另外一个集合时，这意味着这个颜色的所在集合的大小至少翻了一倍。但是一个集合的大小最多为$n$，因此这个颜色最多被加入$\log_2n$次，由此总的时间复杂度为$O(n\log_2n)$。

问题1：给定$n$个顶点和$m$条边，每条边都有一个颜色。之后给出$q$个询问，每个询问给出两个不同的顶点$u,v$，如果仅保留颜色为$c$的边$u,v$可以连通，那么称$u,v$是$c$连通的，问总共有多少不同的颜色$c$，满足$u,v$是关于$c$连通的。

这个问题挺有趣的，实际上就是要为不同的颜色建立一副图，判断对于某种颜色，两个顶点是否连通而已。这里如果某个顶点没有颜色$c$的关联边，那么就不必在颜色为$c$的图上加入这个顶点，可以证明总的顶点数不会超过$2m$。记录$S(v)$表示顶点$v$的出现在了哪些颜色的图上。

现在考虑每个请求$u,v$，我们要判断$u,v$在哪些颜色下保持连通。很显然我们不需要枚举所有的颜色，只需要考虑出现在$u,v$颜色交集中的颜色即可。但是算这个交集会比较麻烦，我们这里可以用启发式合并的技巧，遍历较小的集合来算交集，这样时间复杂度为$O(min(\mid S(u)\mid, \mid S(v)\mid)\alpha(m))$，其中$\alpha$是阿克曼函数。

但是上面的方法也不能保证多好的时间复杂度，因为可能存在两个顶点之间存在$m$条边，而询问每次都是这两个顶点。因此我们可以缓存每次查询的结果，这样就能保证处理的请求都是不同的顶点对。

现在来考虑时间复杂度是多少。我们记将每个顶点的颜色集合的大小按照从大到小排序后得到序列$x_1,x_2,\ldots,x_k$，其中$k$是所有颜色图上的顶点总数，且$k=O(m)$。可以看出最坏结果应该为$\sum_{i=1}^{O(\sqrt{q})}ix_{i+1}$。可以发现公式中$i$越大，$x_i$越小，但是它的权重也越大，因此为了使的总和最大，一定有$x_1=x_2=\ldots=x_{O(\sqrt{q}})=O(\frac{m}{\sqrt{q}})$，这时候的总和为$O(\frac{m}{\sqrt{q}}\cdot q)=O(m\sqrt{q})$，这里我们将哈希表的时间复杂度和并查集的时间复杂度简单设为$O(1)$。

树上卷积问题

给定一颗包含$n$个顶点的树，根为$1$，每个顶点$v$都包含了一个一阶多项式$p_v$。现在对于每个顶点$v$，定义一个函数$f$，其中$f(v)=\prod_{c\in T(v)}p_c$，其中$T(v)$表示的是以$v$为根的子树。

现在要求对于每个顶点$v$，计算出$f(v)$。

这个问题可以类似于树形DP解决。但是我们发现每个顶点都需要跑若干次多项式乘法，一个顶点的最坏时间复杂度为$O(n^2)$，因此总的最坏时间复杂度是否就是$O(n^3)$呢？

实际上不是的。我们会发现总共有${n\choose 2}=O(n^2)$对顶点，而每对顶点恰好在它们的LCA处相遇1次。每次多项式乘法的时间复杂度为已经处理的顶点数乘上下一个子树中的顶点数，正好等于新增的相遇顶点对数。因此我们可以保证在树上计算多项式乘法的总的时间复杂度约束于$O(n^2)$。

势能分析

势能分析可以用于分析一些复杂的数据结构的各项操作的时间复杂度上限。

首先我们需要为数据结构的每个状态赋予一个势能。

考虑我们对某个数据结构做了$n$次操作。第$i$次操作的真实时间复杂度为$a_i$，而第$i$次操作完成后的势能为$w_i$。则记第$i$次操作的摊还时间复杂度为$b_i=a_i+w_i-w_{i-1}$。很显然有：

$$b_1+\ldots+b_n\\ =(a_1+w_1-w_0)+\ldots +(a_n+w_n-w_{n-1})\\ =a_1+\ldots+a_n+w_n-w_0$$

其中$w_0$是数据结构初始时候的势能。将$w_n$和$w_0$移动到左边，就可以得到真实的时间复杂度之和：

$$a_1+\ldots+a_n=b_1+\ldots+b_n+w_0-w_n$$

如果我们始终保证$w_i\geq 0$，那么可以得到更加简单的一个上限：

$$a_1+\ldots+a_n\leq b_1+\ldots+b_n+w_0$$

问题1：给定一个序列$a_1,\ldots,a_n$，要求支持三种操作：第一种给定$y_i$将某个区间中的所有数$x$变为$x\pmod y_i$。第二种给定$z_i$，将区间中所有的数都变成$z_i$。第三种查询区间和。其中$1\leq a_i,y_i,z_i\leq 10^9$，且$1\leq n\leq 10^5$。

我们可以用平衡树来实现。为每个连续的拥有相同值的区间，创建一颗BST。之后我们记值为$m$的某个连续区间的势能为$\log_2n(\log_2m+1)$，而整个序列的势能为每个区间的势能之和。

下面考虑操作$2$，每个操作2，都至多创建两个新的区间，并回收掉多个旧的区间，由于每个旧的区间的释放的势能至少为$\log_2n$，因此可以正好摊掉区间合并的时间复杂度。因此其操作$2$的摊还时间复杂度为$O(\log_2n(\log_2M+1))$，$M$为最大的可能值。

接下来考虑操作$1$，操作$1$最多还是会创建两个新的连续区间，并且对于每个被处理的值为$m$的区间，都要满足$y_i\leq m$，这意味着$m\pmod y_i$至少会减少一半，因此会释放最少$\log_2n$的势能用于摊还时间。操作$1$的摊还时间复杂度为$O(\log_2n(\log_2M+1))$。

最后我们考虑第三种操作，很显然暴力遍历所有连续区间是不可行的，我们可以在每次区间创建修改的时候将其同步到某个线段树上即可，由于时间复杂度也是$O(\log_2n)$，因此是可以摊的（只是常数增大了而已）。事实上所有查询操作都可以在这颗树上进行。

因此我们$n$次操作的摊还时间复杂度上限为$O(n\log_2n(\log_2M+1))$，而由于势能上限也为$O(n\log_2n(\log_2M+1))$，因此真实的时间复杂度上限为两者之和$O(n\log_2n(\log_2M+1))$。