算法(4th ed)(212):基础——案例研究:union-find 算法 7.2.9

阅读数:8 2019 年 11 月 9 日 15:59

算法(4th ed)(212):基础——案例研究:union-find 算法 7.2.9

(实现:均摊成本的图像)

与对其他任何数据结构实现的讨论一样,我们应该按照 1.4 节中的讨论在实验中用典型的用例验证我们对算法性能的猜想。图 1.5.10 详细显示了我们的动态连通性问题的开发用例在使用各种算法处理一份含有 625 个触点的样例数据(mediumUF.txt)时的性能。绘制这种图像很简单(请见练习 1.5.16):在处理第 i 个连接时,用一个变量 cost 记录其间访问数组(id[]sz[])的次数,并用一个变量 total 记录到目前为止数组访问的总次数。我们在 (i, cost) 处画一个灰点,在 (i, total/i) 处画一个红点,红点表示的是每个操作的平均成本,即均摊成本。图像能够帮助我们更好地理解算法的行为。对于 quick-find 算法,每次 union() 操作都至少访问数组 625 次(每归并一个分量还要加 1,最多再加 625),每次 connected() 操作都访问数组 2 次。一开始,大多数连接都会产生一个 union() 调用,因此累计平均值徘徊在 625 左右;后来,大多数连接产生的 connected() 调用会跳过 union(),因此累计平均值开始下降,但仍保持了相对较高的水平(能够产生大量 connected() 调用并跳过 union() 的输入性能要好得多,例子请见练习 1.5.23)。对于 quick-union 算法,所有的操作在初始阶段访问数组的次数都不多;到了后期,树的高度成为一个重要因素,均摊成本的增长很明显。对于加权 quick-union 算法,树的高度一直很小,没有任何昂贵的操作,均摊成本也很低。这些实验验证了我们的结论,显然非常有必要实现加权 quick-union 算法,在解决实际问题时已经没有多少进一步改进的空间了。

算法(4th ed)(212):基础——案例研究:union-find 算法 7.2.9

图 1.5.10 所有操作的总成本(625 个触点)

评论

发布