在动态连通性问题中，quick-union算法改进了quick-find算法中union()方法的执行速度，但是并不能在所有输入情况下都提升执行速度。以下来介绍对于quick-union算法的一些优化。

假设在互联网中有两台计算机需要互相通信，那么该怎么确定它们之间是否已经连接起来还是需要架设新的线路连接这两台计算机。这就是动态连通性问题。动态连通性问题在日常生活中十分常见，比如上文所说的通信网络中的连通性问题，比如物理化学中的渗流问题。通过并查集这种数据结构及union-find算法可以解决动态连通性问题。

随着计算机处理数据量的增大，程序运行时消耗的时间与内存空间也逐步增加。对于同一个问题，不同的算法解决方案所耗费的代价不尽相同，对算法的性能进行合理、准确的分析可以为算法的选择、改进提供可靠的依据。 Continue reading

链表是一种基础的数据结构，在某些情况下链表比数组更适合用来表示集合类的抽象数据类型。链表的定义如下：

链表是一种递归的数据结构，它或者为空（null），或者是指向一个节点（node）的引用，该节点含有一个泛型的元素和一个指向另一条链表的引用。

在结构化存储数据集时，链表是数组的一种重要的替代方式。

许多基础数据类型都和对象的集合有关。具体来说，数据类型的值就是一组对象的集合，所有的操作都是关于添加、删除或是访问集合中的对象。

本节介绍三种数据类型：背包（Bag）、队列（Queue）和栈（Stack），它们的不同之处在于删除或访问对象的顺序不同。同时还介绍了三种数据类型的数组实现及简单应用，在下一篇中介绍链表及这三种数据类型的链表实现。 Continue reading

在Coursera上学习了普林斯顿的算法公开课（课程链接， 配套教材网站）。收获很多，对基本的排序，查找算法也有了一些了解，但是时间一久就全忘记了。在接下来的文章中按照课程及配套教材对重要的知识点做一个总结，当作复习与备忘。 Continue reading