目录备份第一章：基础本章主要介绍工具
共五节，前两节主要是对Java语法的回顾，第三节是对三个数据结构、背包、队列和堆栈的API说明。
第四节介绍了算法的分析方法。 第五节对具体例子的联合查找算法，也就是并行调查集进行了实践。
算法分为算法思想和实现细节。 用具体的语言实现细节时，思想和实现细节混杂，难以剥离，难以理解。 本书采用了Java来直接描述算法。
从这一点也可以看出《算法导论》使用伪代码描述算法的理由。 本书采用了Java的子集，大多数语法与其他编程语言相同，很少使用Java的特性语言。
在这里，我默认学习过Java和其他语言的基本语法。 前三节不再叙述了。 道具好好用就行了！
算法分析的很多教材都是直接抛出模型的，没有直接提到模型是怎么来的。
从时间方面来看。 首先从观察实际程序运行时间出发，然后建立数学模型，再对模型进行分类。
从空间上分析了内存。
观察可以从直接现实出发，利用时间API统计程序的执行时间。
根据数据的规模和运营所需的时间，获得增长曲线。 根据曲线粗略得到增长函数。
例如，程序的实际运行时间如下： 横轴为数据大小，纵轴为执行时间。
虽然从上图中不太清楚有效的信息，但如果横轴和纵轴为对数，则得到斜率为3的直线。 这表明原始函数为t(n )=aN3 ) n )=aN3 ) n )=aN3。 取对数，则LG(T ) n )=3lgN lga (t ) n ) )=3lgn LGA (t ) n )=3lgn LGA
由此，可以根据由公式输入的数据的规模计算程序的执行时间。
由此也可以看出，程序的执行时间遵循幂律t(n )=aNb ) n )=aNb ) n )=aNb。
数学模型程序运算的总时间与每条语句的耗时及执行每条语句的频率有关。
前者与计算机、Java编译器、操作系统有关。 后者依赖于程序本身和输入。
在程序中进行多次输入的结果，通过执行最频繁的指令，决定程序的执行时间。 这些指令来自程序的内循环
因此，许多程序的执行时间取决于其中的一些指令。
由此，程序的执行时间从具体的计算机中分离出来，考虑程序本身即可。 更换计算机对时间的影响可以在常数水平上忽略。
增长水平的分类主要分为以下七部分。
请注意，常数大的项不可忽视。 计算机执行每个指令的时间可能不同，有些指令会立即执行以进行缓存。 但是，如果一些命令消耗很多
间。系统不能对算法程序的运行时间产生影响。程序在不同的场景下效果可能不一样。对输入数据存在依赖，存在有些数据直接就是想要的结果，而有些则需要遍历全部也不一定能够找到想要的结果。 并查集 union-find这一节讲的是 union-find 算法，也就是并查集。同时也是对应课程的第一节。
定义问题我们需要明白这个算法解决了什么问题？也就是定义问题，然后是怎么解决的，之后就是改进了。
在现实世界中，如何判断两个人直接或间接的认识，间接认识表示二人通过第三方甚至更多人的联系而认识。
除此之外还有判断两地之间是否有必要建立通信线路，如果存在间接的联系则没必要。等等有很多类似的问题。
将以上的问题抽象起来，从集合的角度来看。要解决的问题则是判断两个点是否存在于同一集合之中。此处集合也称为连通分量。
如图所示，存在 7 个点，点和点之间的联系形成了 3 个连通分量。
当新加入一个联系时，点和点之间的联系随之发生改变。如图，2 和 5 之间建立了联系，变成了 2 个连通分量。
为了解决这类问题，将其中的流程抽象化，自顶向下思考。可以写成五个函数：
首先需要初始化每个点 UF(int N)最后就是建立联系了 void union(int p, int q)判断时需要找到根节点 int find (int p)根据根节点是否一致来判断已经在一个连通分量中 boolean connected (int p, int q)将 API 组织起来：
public static void main(String[] args) { int N = StdIn.readInt(); UF uf = new UF(N); while (!StdIn.isEmpty()) { int p = StdIn.readInt(); int q = StdIn.readInt(); if (uf.connected(p,q)) { continue; } uf.union(); StdOut.println(p + " " + q); } StdOut.println(uf.count() + "components");}完整代码如下：
public class UF { private int[] id; private int count; public UF(int N) { count = N; id = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; } } public int count() { return count; } public boolean connected(int p, int q) { return find(p) == find(q); } public int find(int p) { } public void union(int p, int q) { } public static void main(String[] args) { int N = StdIn.readInt(); UF uf = new UF(N); while (!StdIn.isEmpty()) { int p = StdIn.readInt(); int q = StdIn.readInt(); if (uf.connected(p,q)) { continue; } uf.union(p,q); StdOut.println(p + " " + q); } StdOut.println(uf.count() + "components"); }}下面就是如何实现了！
细节实现首先需要思考如何表示点与点之间的关系。
可以采用数组来表示，索引代表点本身，而存储的值代表指向的点。
起初一条联系都没有，都是孤立的点，所以将其指向的点都标识为自己，也就是数组中存储的值都改为其下标。
public UF(int N) { // 表示连通分量的个数，初始为 N count = N; id = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; }}数组的定义就是父节点，所以直接返回父节点即可。（注意此处的父节点同时也是根节点）
public int find(int p) { return id[p]; }首先判断是否已经连接，也就是父节点是否一致。已经连接的话就不需要在进行后续操作了，反之需要进行后续操作。
public void union(int p, int q) { int pID = find(p); int qID = find(q); if (pID == qID) { return; } for (int i = 0; i < id.length; i++) { if (id[i] == pID) { id[i] = qID; } } count--; }为什么要遍历？假设存在两个连通分量，其中一个需要合并成一个，那么就需要将涉及到其中的所有点的父节点都修改为指向另外一个连通分量的父节点。
改进 find每次进行 union 都需要执行一遍 for 循环，是一个线性增长。
此外 N 个点就有 N 个联通分量，假设要变成 1 个联通分量的话最多需要进行 N - 1 次 uoion 操作。
所以这个时间复杂度就是 O ( N 2 ) O(N^2) O(N2) 了。
union 的修改如下：
public void union(int p, int q) { int pRoot = find(p); int qRoot = find(q); if (pRoot == qRoot) { return; } id[pRoot] = qRoot; count--; }直接赋值干掉了一个 for 循环，消除了线性增长。
但是 find 也要随之修改。find 需要拿到根节点，根节点的修改才能代表整个连通分量的合并。
可以修改 find 为如下：
public int find(int p) { while(p != id[p]) { p = id[p]; } return p; }通过循环找到根节点。如图，假设 3 和 5 之间要连接。那么首先找到 3 的根节点 9 ，5 的根节点 6 ，将 9 和 6 的指向修改即可。
修改前：
修改后：
这样就使得和 3 在同一连通分量下的所有阶段都合并到和 5 相关的连通分量中。而之前则是需要一个循环来修改所有与 3 相关的连通分量中的所有值。
注意每次拿到的是根节点，而非父节点。之前虽然得到的也是父节点，但因为只有两层的关系，所以也是根节点。此处修改 unoin 后，就变为了多层的关系。
这样操作带来的坏处就是如果层数过多， find 需要循环多次才能拿到根节点。而且在也与输入的数据有关，在一些情况下甚至还不如之改进前的速度快。
增加加权判断find 操作次数多是因为层数过深，进一步修改就是降低层数。可以将其想象成一颗倒立的树，每次合并之时都是小树指向大树，这样就降低了树高。
假设有两颗树，树高分别为 5 和 3 。如果 5 指向 3 ，树高就会变为 8 。反之 3 指向 5 ，因为 3 没有 5 大，所以高度还是 5 ，3 则是挂在了 5 上。
加权就是判断树高，使得小树挂在大树上。
首先增加一个数组，用于存储树高。其高度均为 1 。
public WeightedQuickUnion(int N) { count = N; id = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; } sz = new int[N]; for (int i = 0; i < N; i++) { sz[i] = 1; } }union 修改如下：
public void union(int p, int q) { int i = find(p); int j = find(q); if (i == j) { return; } if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }else { id[j] = i; sz[i] += sz[j]; } count--; } 压缩路径最初因为需要修改大量连接而低效。
将其优化后又因为当 find 操作需要循环多次而低效。
加权后的效果已经很好了，但是依旧存在 find 循环问题，最好不要让其循环，其实也就是压缩路径了。
可以在其循环之时顺便将父节点直接指向根节点。例如 CPP 版递归时进行压缩路径的实现。
int find(int x) { if (f[x] == x) {return x;} return f[x] = find(f[x]); } 总结这样优化后已经是最好的了，但依旧不是常数级别。事实上常数是不可能的，加权加上压缩路径已经是最优的了。