大数据 | 大数据基础--算法之亚线性时间算法求连通分量的数目

亲爱的读者朋友大家好，上次我们分析了如何用一个亚线性时间算法估计一个点集合的直接，并对算法给出的结果的近似比进行了分析。这次我们来看另外一个经典的问题，求连通分量的数目。

同样地，还是让我们先来看一下问题的定义：

定义：

已知：\(G = (V,E),\epsilon,d = deg(G)\)，图\(G\)用邻接表表示，其中\(d\)表示所有节点中度最大的节点的度，\(|V| = n,|E| = m \leq d\cdot n\)

求出：一个\(y\)，使得\(C - \epsilon \cdot n \leq y \leq C + \epsilon \cdot n\)，其中\(C\)为使用线性算法求解得到的标准解

问题分析：

当数据量小的时候，我们也有经典的算法进行求解，也就是经典的搜索策略，时间复杂度为\(O(n)\)，其中\(n\)是节点的个数，还是老问题，当节点数目太多的时候，就需要一个亚线性时间复杂度的算法对结果进行一个近似的估计。

在正式分析算法之前，我们先将问题进行一定的转化：记顶点\(v\)所属的连通分量中的节点数目为\(n_v\)，\(A,A \in V\)是一个连通分量的点集合，则存在如下等式关系：\(\sum_{u \in A}{\frac{1}{n_u} } = \sum_{u \in A}{\frac{1}{|A|} } = 1\)，这个很容易证明，因为同一个连通分量中的每一个点的\(\frac{1}{n_v}\)是一样的，都是分量中点的个数的倒数。如此，则最终的结果\(C\)可以表示为\(\sum_{u \in V}{\frac{1}{n_u} }\)。因此进一步地，对\(C\)的估计可以转化为对\(\frac{1}{n_u}\)的估计。

求解问题的思想：

\(n_u\)很大，精确计算很难，但是此时\(\frac{1}{n_u}\)很小，可以用一个很小的常量代替\(\frac{1}{n_u}(0\)或者\(\frac{\epsilon}{2})\)，如果我设\(\hat{n_u} = min\{n_u,\frac{2}{\epsilon}\}\)，则\(\hat{C} = \sum_{u \in V}{\frac{1}{\hat{n_u} } }\)，使用\(\hat{C}\)来估计\(C\)可以获得很不错的结果。

引理：

\(\forall u \in V\)，有\(|\frac{1}{n_u} - \frac{1}{\hat{n_u} }| \leq \frac{\epsilon}{2}\)，即\(|C - \hat{C}| \leq \frac{\epsilon \cdot n}{2}\)

引理的证明非常简单，分成两步，第一步证明\(|\frac{1}{n_u} - \frac{1}{\hat{n_u} }| \leq \frac{\epsilon}{2}\)，第二步证明\(|C - \hat{C}| \leq \frac{\epsilon \cdot n}{2}\)

证明（一）：\(\frac{1}{\hat{n_u} } = max\{\frac{1}{n_u},\frac{\epsilon}{2}\}\)。如果\(\frac{1}{n_u}>\frac{\epsilon}{2}\)，\(\frac{1}{\hat{n_u} } = \frac{1}{n_u} \Rightarrow \frac{1}{\hat{n_u} } - \frac{1}{n_u} = 0 \Rightarrow |\frac{1}{\hat{n_u} } - \frac{1}{n_u}| = 0 \leq \frac{\epsilon}{2}\)；如果\(\frac{1}{n_u}\leq \frac{\epsilon}{2}\)，\(|\frac{1}{\hat{n_u} } - \frac{1}{n_u}| = |\frac{\epsilon}{2} - \frac{1}{n_u}| < \frac{\epsilon}{2}\)

证明（二）：\(|C - \hat{C}| = |\sum_{u \in V}{\frac{1}{\hat{n_u} } } - \sum_{u \in V}{\frac{1}{n_u} }| = |\sum_{u \in V}{(\frac{1}{\hat{n_u} } - \frac{1}{n_u} })| \leq \sum_{u \in V}|{\frac{1}{\hat{n_u} } - \frac{1}{n_u} }| = \frac{\epsilon \cdot n}{2}\)

算法-计算\(\hat{n_u}\)

思想很简单，就是一个小型的搜索，如果搜索到的点的个数小于\(\frac{2}{\epsilon}\)就继续搜索，否则直接返回\(\frac{2}{\epsilon}\)。时间复杂度为\(O(d\cdot \frac{1}{\epsilon})\)，\(d\)越大，用的时间越长，\(\frac{1}{\epsilon}\) 越大，用的时间越长。

算法-计算\(n_u\)

从节点集合中随机选出\(r = b/{\epsilon}^2\)个节点构成节点\(U\)，对每个节点应用上一个算法，于是最终的\(\hat{C} = \frac{n}{r} \sum_{u \in U}{\frac{1}{\hat{n_u} } }\)，时间复杂度为\(O(d/{\epsilon}^3)\)

算法评价

计算连通分量的数目是一个较为简单的问题，下次介绍最小生成树的求解，敬请期待~