大数据 大数据基础--算法之亚线性时间算法求点集合的直径
大数据 | 大数据基础--算法之亚线性时间算法求点集合的直径
亲爱的读者大家好,上次我们分析大数据中常用的亚线性空间算法,这次我们来看一个亚线性时间算法。这一部分要介绍的亚线性时间算法总共有四个,这篇短文介绍的是其中之一,求点集合的直径。
我们先来看一下问题定义:
定义:
已知:有\(m\)个点,点与点之间的距离使用邻接矩阵表示,则\(D_{ij}\)表示点\(i\)到点\(j\)的距离,\(D\)是一个对称矩阵,并且满足三角不等式\(D_{ij} \leq D_{ik} + D_{kj}\)。
求出:点对\((i,j)\)使得\(D_{ij}\)是最大的,则\(D_{ij}\)是这\(m\)个点的集合的直径。
普通求解方法
当数据量小的时候这个问题非常简单,只需要把矩阵中所有的数字都扫一遍,复杂度是\(O(m^2)\),记作\(O(n)\)。
或者数据量再稍微大一些,也可以用并行的方法将时间进一步地缩小,但是这样做就比较依赖于硬件资源。
当数据量进一步扩大,我们则希望用一个亚线性的方法来解决这个问题,也就是说时间复杂度为\(O(\sqrt{n})\),当然我们之前说过我们采取的是一个近似的算法,那么我们所估计的结果有多精确,也要给出一个衡量。
近似比
算法给出的结果与理论最优结果的一个比较
求解算法:The Indyk’s Algorithm
- 任选\(k \in [1,m]\)
- 选出\(l\),使得\(\forall i,D_{ki} \leq D_{kl}\)
- 返回\((k,l),D_{kl}\)
算法分析之近似比分析
最优解记为 \(opt\),是点 \(i\) 和点 \(j\) 之间的距离
则有\(\frac{opt}{2} \leq D_{kl} \leq opt\)。
算法分析之近似比证明不等式
关于不等式的右侧易证,左侧的证明如下所示: \[ \begin{align*} opt = &D_{ij}\\ \leq &D_{ik} + D_{kj}\\ \leq &D_{kl} + D_{kl}\\ \leq &2D_{kl} \end{align*} \] 算法评价
算法的时间复杂度为\(O(m) = O(\sqrt{n})\)。读完整个算法之后会发现其实只做了一件事情(一转化成数学语言看起来就比较抽象了),就是在邻接矩阵中随便选出一行,然后求出其最大值,而这个值便具有\(1/2\)的近似比,同时算法也是一个亚线性时间复杂度的算法。
计算点集合的直径是一个简单的问题,而后面将要讲解的连通分量等就比较麻烦了,这将会在接下里的短文中慢慢分析,敬请期待~