article20201018

大数据 | 大数据基础--算法之亚线性时间算法：计算图的平均度算法四

亲爱的读者朋友大家晚上好，上次我们分析了计算平均度的第三个估计算法，它已经是一个近似比为\(1+\epsilon\)的算法了。继续对此算法进行优化得到的算法四比较抽象，就不做详细的分析了，在此把过程展示给大家，有兴趣的小伙伴可以自己研究一下。

Alg III

利用\(E[\Delta_i]\)的\(1+\epsilon\)估计，可以得到\(\Delta_i\rho_i(1+\beta)^i\)是\(\frac{T_i}{n}\)的\((1+\epsilon)(1+\beta)\)估计。于是乎，经过改造的算法如下所示：

1. 从\(V\)中抽取样本\(S\)，\(|S| = \tilde{O}(\frac{L}{\rho\epsilon^2}),L=poly(\frac{log\ n}{\epsilon}),\rho = \frac{1}{t}\sqrt{\frac{\epsilon}{4}\cdot \frac{\alpha}{n} }\)
2. \(S_i \gets S \cap B_i\)
3. \(\boldsymbol{for}\ i \in \{0,\dots,t-1\}\ \boldsymbol{do}\)
   1. \(\boldsymbol{if}\ |S_i| \geq \theta_\rho\ \boldsymbol{then}\)
      1. \(\rho_i \gets \frac{|S_i|}{|S|}\)
      2. \(estimate\ \Delta_i\)
   2. \(\boldsymbol{else}\)
      1. \(\rho_i\gets 0\)
4. \(\boldsymbol{return}\ \hat{\bar{d} } = \sum_{i=0}^{t-1}(1+\Delta_i)\rho_i(1+\beta)^{i}\)

Alg IV

1. \(\alpha \gets n\)
2. \(\hat{\bar{d} } < -\infty\)
3. \(\boldsymbol{while}\ \hat{\bar{d} } < \alpha\ \boldsymbol{do}\)
   1. \(\alpha \gets \alpha/2\)
   2. \(\boldsymbol{if}\ \alpha < \frac{1}{n}\ \boldsymbol{then}\)
      1. \(\boldsymbol{return}\ 0;\)
   3. \(\hat{\bar{d} } \gets AlgIII_{\sim \alpha}\)
4. \(\boldsymbol{return}\ \hat{\bar{d} }\)

算法相关指标

近似比：\((1 + \epsilon)\)

运行时间：\(\tilde{O}(\sqrt{n})\cdot poly(\epsilon^{-1}log\ n)\sqrt{n/\bar{d} }\)

总结

至此，准备的亚线性时间算法已经分析完了，接下来会分析并行模型算法，这部分包括基本问题、排序问题、最小支撑树，敬请期待。