观察
运行时间和输入本身相对无关，主要取决于问题规模
例：统计文件中三个数和为0的数量
public class ThreeSum{
public static int count(int a[]){
int N = a.length, cnt = 0;
for(int i = 0; i < N; i++){
for(int j = i + 1; j < N; j++){
for (int k = j + 1; k < N; k++){
if(a[i] + a[j] + a[k] == 0)
cnt += 1;
}
}
}
}
}
一种表示计时器的抽象数据类型：
public class StopWatch{
private final long start;
public StopWatch(){
start = System.currentTimeMillis();
}
public double elapsedTime(){
long now = System.currentTimeMillis();
return (now - start) / 1000.0;
}
}
数学模型
程序运行总时间主要和两点有关：
- 执行每条语句的耗时（取决于计算机、Java编译器和操作系统）
- 执行每条语句的频率（取决于程序本身和输入）
对于执行频率，有些分析很容易，如在 Three.count() 中将 cnt 设为 0 的语句只会执行一次；有些需要深入分析，如 Three.count() 中的 if 语句会执行 N(N-1)(N-2)/6 次。
近似
用 ~f(N) 表示所有随着N增大除以f(N)的结果趋近于1的函数。用g(N)~f(N)表示随着g(N)/f(N) 随着N增大趋近于1。
一般用到的近似方式都是g(N)~f(N)，其中 f(N)=Nb(logN)c，其中a,b和c均为常数，将f(N)称为g(N)的增长数量级。
常见的增长数量级函数:
| 描述 | 函数 B |
|---|---|
| 常数级 | 1 |
| 对数级 | logN |
| 线性级 | N |
| 线性对数级 | NlogN |
| 平方级 | N^2 |
| 立方级 | N^3 |
| 指数级 | 2^N |
执行最频繁的执行决定了程序执行的总时间——称这些指令为程序的内循环
成本模型
用成本模型来评估算法的性质，这个模型定义了所研究算法中的基本操作。例如，3-Sum问题的成本模型是访问数组元素的次数。
构建运行时间的数学模型所需步骤：
- 确定输入模型，定义问题规模
- 识别内循环
- 根据内循环中的操作确定成本模型
- 对给定输入，判断这些操作的执行频率
如二分查找，它的输入模型是大小为N的数组a[]，内循环是while循环中所有语句，成本模型是比较操作（比较两个数组元素的值）
设计更快的算法
2-Sum 问题
假设所有整数各不相同，这个问题很容易在平方级别——双重循环来解决，下面利用归并排序和二分查找在线性对数级别解决 2-Sum 问题：
思路：当且仅当 -a[i] 存在于数组中（且a[i]非0）时，a[i] 存在于某个和为0的整数对中。
public class TwoSumFast{
public static int count(int[] a){
//先排序
Arrays.sort(a);
int cnt = 0;
for(int i = 0; i < a.length; i++){
if(BinarySearch.rank(-a[i], a) > i)
cnt++;
}
return cnt;
}
}
归并排序所需时间与NlogN成正比，二分查找所需时间和logN成正比，因此整个算法运行时间和NlogN成正比。
3-Sum 问题
同样假设所有整数各不相同，同上面一样，当且仅当 -(a[i] + a[j]) 在数组中（不是a[i] 也不是 a[j]）时，整数对（a[i] 和 a[j]）为某个和为0的三元组的一部分。
public class ThreeSumFast{
public static int count(int[] a){
//先排序
Arrays.sort(a);
int cnt = 0;
for(int i = 0; i < a.length; i++){
for(int j = i + 1; j < a.length; j++)
if(BinarySearch.rank(-(a[i] + a[j]), a) > j)
cnt++;
}
return cnt;
}
}
内存
对象
数组
字符串对象
当调用substring()方法时，就创建了一个新的String对象（40字节），但仍然重用了相同的value[]数组，因此该字符串的子字符串只会使用40字节的内存，也就是说，一个子字符串的额外内存是一个常数，构造一个子字符串所需时间也是常数。
举例：union-find 算法
动态连通性
问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，一对整数p q可以被理解为“p和q是相连的”，具有如下性质；
- 自反性：p和p是
- 对称性：若p和q相连，则q和p也相连
- 传递性：若p和q相连且q和r相连，则p和r也相连
union-find 算法API
| 方法名 | 操作 |
|---|---|
| UF(int N) | 以整数标识（0到N-1）初始化N个触点 |
| void union(int p, int q) | 在p和q之间添加一条连接 |
| int find(int p) | p所在的分量的标识符（0到N-1） |
| boolean connected(int p, int q) | 如果p和q存在于同一个分量则返回true |
| int count() | 连通分量的数量 |
用一个以触点为索引的数组id[]作为基本数据结构来表示所有分量。初始有N个分量，每个触点都构成了一个只含有它自己的分量，因此将id[i]初始化为i，其中i为0到N-1。find()判定它所在分量所需的信息保存在id[i]之中。connected()方法只有一条语句find(p)==find(q)，它返回一个布尔值。
实现
1 quick-find 算法
代码
public class UF{
private int[] id;
private int count;
public UF(int N){
id = new int[N];
count = N;
for(int i = 0; i < N; i++){
id[i] = i;
}
}
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--;
}
public int find(int p){
return id[p];
}
public boolean connected(int p, int q){
return id[p] == id[q];
}
public int count(){
return count;
}
}
分析
上述代码的find方法十分高效，因为仅仅需要一次数组读取操作就能够找到该节点的组号，但是问题随之而来，对于需要添加新路径的情况，就涉及到对于组号的修改，因为并不能确定哪些节点的组号需要被修改，因此就必须对整个数组进行遍历，找到需要修改的节点，逐一修改，每次添加新路径带来的复杂度就是线性关系了，如果要添加的新路径的数量是M，节点数量是N，那么最后的时间复杂度就是MN，显然是一个平方阶的复杂度，对于大规模的数据而言，平方阶的算法是存在问题的，这种情况下，每次添加新路径就是“牵一发而动全身”，想要解决这个问题，关键就是要提高union方法的效率，让它不再需要遍历整个数组。
2 quick-union 算法
代码
id[] 数组用父链接的形式表示了一片森林，从任何触点所对应的节点开始跟随链接，最终都将到达含有该节点的树的根节点。quick-union 中 union() 的实现只用了一条语句就将一个根节点变为另一个根节点的父节点，从而归并了两棵树。
public class QuickUnionUF{
private int[] id;
private int count;
public QuickUnionUF(int N){
id = new int[N];
count = N;
for(int i = 0; i < N; i++){
id[i] = i;
}
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot){
return;
}
id[pRoot] = qRoot;
count--;
}
public int find(int p){
while(p != id[p]){
p = id[p];
}
return p;
}
public boolean connected(int p, int q){
return find(p) == find(q);
}
public int count(){
return count;
}
}
分析
quick-union 算法看起来比 quick-find 算法更快，因为它不需要为每对输入遍历整个数组。但树这种数据结构容易出现极端情况，因为在建树的过程中，树的最终形态严重依赖于输入数据本身的性质，比如数据是否排序，是否随机分布等等。比如在输入数据是有序的情况下，构造的BST会退化成一个链表。如下图所示。
定义：一棵树的大小是它的节点的数量。树中一个节点的深度是它到根节点的路径上的链接（也就是边）数。树的高度是它的所有节点中的最大深度。
命题：quick-union 算法中 find() 方法访问数组的次数为1加上给定触点所对应的节点的深度的两倍。union() 和 connected() 访问数组的次数为两次find() 操作（若union()中给定的两个触点分别存在于不同的树中则还需要加1）。
由命题G可知，对于整数对0 i，union()操作访问数组的次数为2i+2（触点0的深度为i，触点i的深度为0）。因此，处理N对整数所需的所有find()操作访问数组的总次数为2(1+2+...+N)~N^2。
3 加权 quick-union 算法
只需简单修改quick-union算法就能保证像这样的最坏情况不会出现。与其在 union() 中随意将一棵树连接到另一棵树，现在记录每棵树的大小并总是将较小的树连接到大数上。此时需添加一个数组来记录树中节点数，将这种算法称为加权 quick-union 算法。该算法构造的树的高度也远远小于未加权版本构造的树的高度。
代码
public class WeightedUnionUF{
private int[] id;
private int count;
private int[] sz;
public WeightedUnionUF(int N){
id = new int[N];
count = N;
for(int i = 0; i < N; i++){
id[i] = i;
sz[i] = 1;
}
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot){
return;
}
//比较树大小，小树指向大树，修改大树大小
if(sz[pRoot] < sz[qRoot]){
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}else{
id[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
count--;
}
public int find(int p){
while(p != id[p]){
p = id[p];
}
return p;
}
public boolean connected(int p, int q){
return find(p) == find(q) ;
}
public int count(){
return count;
}
}
分析
命题H：对于N个触点，加权quick-union算法够早的森林中的任意节点的深度最多为lgN。
推论：对于加权quick-union算法和N个触点，在最坏情况下find()、connected()和union()的成本增长数量级为logN。
命题H和推论的意义在于加权quick-union算法是三种算法中唯一可以用于解决大型实际问题的算法。加权quick-union算法处理N个触点和M条连接时最多访问数组cMlgN次，c为常数，比quick-find（和某些情况下的quick-union）需要访问数组至少MN次形成鲜明对比。
4 最优算法——基于quick-union 算法进行路径压缩
理想情况下，我们希望每个结点都直接链接到它的根节点，但又不想像quick-find那样通过修改大量链接实现，实际实现很简单——在检查节点时将它们直连到根节点。
public int find(int p){
while(p != id[p]){
//若当前节点非根节点
//则使当前节点指向父节点的父节点/或直接指向根节点find(index)
id[p] = id[id[p]];
p = id[p];
}
return p;
}
所得到的结果几乎是完全扁平化的树，即路径压缩的加权quick-union算法是最优的算法
