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

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

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

(实验题)

1.5.21 Erdös-Renyi 模型。使用练习 1.5.17 的用例验证这个猜想:得到单个连通分量所需生成的整数对数量为 1/2NlnN

1.5.22 Erdös-Renyi 模型的倍率实验。开发一个性能测试用例,从命令行接受一个intT 并进行 T 次以下实验:使用练习 1.5.17 的用例生成随机连接,和我们的开发用例一样使用 UnionFind 来检查触点的连通性,不断循环直到所有触点均相互连通。对于每个 N,打印出 N 值和平均所需的连接数以及前后两次运行时间的比值。使用你的程序验证正文中的猜想:quick-find 算法和 quick-union 算法的运行时间是平方级别的,加权 quick-union 算法则接近线性级别。

1.5.23 在 Erdös-Renyi 模型下比较 quick-find 算法和 quick-union 算法。开发一个性能测试用例,从命令行接受一个 intT 并进行 T 次以下实验:使用练习 1.5.17 的用例生成随机连接。保存这些连接并和我们的开发用例一样分别用 quick-find 算法和 quick-union 算法检查触点的连通性,不断循环直到所有触点均相互连通。对于每个N,打印出 N 值和两种算法的运行时间的比值。

1.5.24 适用于 Erdös-Renyi 模型的快速算法。在练习 1.5.23 的测试中增加加权 quick-union 算法和使用路径压缩的加权 quick-union 算法。你能分辨出这两种算法的区别吗?

1.5.25 随机网格的倍率测试。开发一个性能测试用例,从命令行接受一个 intT 并进行T 次以下实验:使用练习 1.5.18 的用例生成一个 N×N 的随机网格,所有连接的方向随机且排列随机。和我们的开发用例一样使用 UnionFind 来检查触点的连通性,不断循环直到所有触点均相互连通。对于每个N,打印出 N 值和平均所需的连接数以及前后两次运行时间的比值。使用你的程序验证正文中的猜想:quick-find 算法和 quick-union 算法的运行时间是平方级别的,加权 quick-union 算法则接近线性级别。注意:随着N 值加倍,网格中触点的数量会乘 4,因此平方级别的算法的运行时间会变为原来的 16 倍,线性级别的算法的运行时间则变为原来的 4 倍。

1.5.26 Erdös-Renyi 模型的均摊成本图像。开发一个用例,从命令行接受一个 intN,在 0 到 N-1 之间产生随机整数对,调用connected() 判断它们是否相连,如果不是则调用union() 方法(和我们的开发用例一样)。不断循环直到所有触点均相互连通。按照正文的样式将所有操作的均摊成本绘制成图像。

评论

发布