求解问题的基本方法和步骤

其实国内数据结构算法的教学体系如果能借鉴一些国外的优秀课程, 肯定不至于让学生觉得学了没用, 这是听了普林斯顿大学的 Algorithm part I 之后的感受.

通常使用如下步骤来求解一个问题:

1. 定义 API
2. 实现客户代码(或单元测试/TDD)
3. 描述可以实现这个 API 的数据结构的 ADT.
4. 描述算法, 这些算法即 API 所需的方法实现描述.
5. 分析算法的性能特征(时间/空间).

比如并查集(Union-Find), 定义了 API 之后, 根据不同的数据结构可以实现不同的求解算法.

以数组作为数据结构, 在数组元素表示连通分量编号的情况下, 快速查找实现非常简单, 但合并开销太大. 在数组元素表示连通分量树中的点的父节点编号情况下, 可以采用带权算法来将树的高度进行优化, 再采用路径压缩算法, 可以让时间复杂度接近线性. 详见 Algorithm I 课程.