本笔记基于ROBERT SEDGEWICK & KEVIN WAYNE开设的《Algorithms》课程，同时配有同名教材。
slides本身内容丰富详实，所以我会先甄选出重点的篇幅整理出来并做简单批注，后续会添上对应算法题的演示。
课程总览：
使用Quick-Find方法来解决，直接对数组的每一个元素进行检查和操作：
代码实现：
使用这个方法的问题是成本太高了，对N个目标进行N次union连接操作共需要访问数组N²次。
试一试别的方法：使用Quick-Union（懒人方法），通过对元素的“根”来进行检查和操作。
代码实现：
但这个懒人办法也太慢了。前一个Q-Find的union操作要访问N次数组，同时它的“树”（把元素连接起来的样子想象成是树的枝桠）是扁平的，但是保持这样的扁平代价太大；后一个Q-U的“树”会变得非常高，使其find操作也可能需要访问N次数组。那怎么办呢？只要在操作树的时候进行“权衡”就能两全其美啦：
“权衡”之后Q-Union的树不再肆意地乱长，而是根据以小服大的方式比较均衡扁平地排列开来了。再想一想，还可以把树变得更加扁平吗？
对，使用路径压缩！将检查过后的节点直接指向根，这样树就进一步扁平了。
对解决动态连接问题的这几种方法总结、对比一下，我们要追求在最坏情况下效率最高（成本最小）的方法：
现在来简单看一看如何分析算法（的效率/成本）：
使用“约等于”的波浪号标记来简化数字进行分析：
来看一下不同算法复杂度的增长速度：
常用的用来标记算法复杂度的符号说明：
每篇文章除特殊声明外均以 CC BY-NC-SA 4.0 协议发布，非商业用途可以在保留署名和来源的情况下任意转载。