算法练习(93):连通性问题分析(1.5.5-1.5.6)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 数组的访问次数
• quick-union算法分析

题目

1.5.5 在一台每秒能够处理 10⁹ 条指令的计算机上，估计 quick-find 算法解决含有 10⁹ 个触点和 10⁶ 条连接的动态连通性问题所需的最短时间（以天记）。假设内循环 for 的每一次迭代需要执行 10 条机器指令。

---

1.5.5 Estimate the minimum amount of time (in days) that would be required for quick-find to solve a dynamic connectivity problem with 10⁹ sites and 10⁶ input pairs, on a computer capable of executing 10⁹ instructions per second. Assume that each iteration of the inner for loop requires 10 machine instructions.

分析

由算法练习(91):quick-union(1.5.2)可知

答案

题目

1.5.6 使用加权 quick-union 算法完成练习 1.5.5 。

---

1.5.6 Repeat Exercise 1.5.5 for weighted quick-union.

分析

答案