算法（第四版）第一章笔记
第一章 基础
1.1 基础编程模型 4
1.1.1 Java程序的基本结构 4
1.1.2 原始数据类型与表达式 6
1.1.3 语句 8
1.1.4 简便记法 9
1.1.5 数组 10
1.1.6 静态方法 12
1.1.6.4 递归
编写递归代码最重要的要点在于以下几点：
- 每个程序都必须包含一个或多个函数或过程。
- 在编写任何函数或过程时，请确保它们能够完成一项特定的任务。
- 每个函数必须包含至少一条return语句作为终止条件。
- 每个函数都应该处理比当前问题规模更小的问题。
- 确保每个函数都有明确的目标，并将目标逐步细化为更小的任务。
- 避免将相同的问题多次处理以提高效率
1.1.7 API 16
1.1.7.4 你自己编写的库
API的设计初衷是为了将使用与实现区分开来：除API所明确提供的信息外,调用者无需关心具体实施细节,而具体实施时也不应针对特定应用场景进行特殊处理。- 从职责划分的角度来看,程序员可以将API视为调用方与实现方之间的明确协议,它指明了各方的责任与功能。- 实现方则需确保所有操作均能按协议规范执行,从而保障系统的整体一致性。- 这种设计使得接口具有高度的可重用性,同时也降低了维护成本。- 各方只需专注于自己的职责即可
1.1.8 字符串 20
1.1.9 输入输出
改写说明
1.1.9.4 标准输入
标准输入流的一个显著特点是这些值在被程序读取之后不再可用；一旦一个值被程序读取后就无法回退并再次获取该值。
1.1.9.5 重定向与管道
1.1.10 二分查找 28
1.1.11 展望 3
1.1答疑：
-
1 / 0 与 1.0 / 0.0 的结果是什么？
- 1.0 / 0.0 = INFINITY
- 1 / 0编译出错 除零异常 ，
java.lang.ArithmeticException: / by zero-
一个for循环 和 while形式有什么区别？
- 答：while 循环中的 “递增变量” 在循环结束后还可以继续使用 。
习题1.1.25 使用数学归纳法证明欧几里得算法
-
欧几里得算法的核心在于其正确性
-
命题：对于任意整数a,b，有gcd(a, b)=gcd(b,a mod b)
-
设k，r为整数。设r = a mod b ,则a可表示为 a = r + k*b
-
-
设d为a与b的最大公约数，则d必能分别整除a与b（即d\mid a且d\mid b）。进一步地r = a - k \cdot b；由此可得r也被d所整除（即d\mid r），因此同样地，在考虑由b与r组成的集合时。
-
假设存在一个正整数d_1能同时整除b_1=r_1 + k \cdot b_2 与b_2, 则该数值同样能够分别分割开这两个元素（即d_1\mid b_1 且d_1\mid b_2 ）。进而我们可以得到等式： a = (r + k \cdot b) 其中r = a - q \cdot b
-
由此可见，在分析两个不同的变量集合时\left\{\begin{array}{l}\textit{{第一个}}\\ \textit{{第二个}}\end{array}\right.其共同的因素不会发生任何变化（即它们的最大值实际上相等）。特别值得注意的是这两个最大值实际上相等。
1.2 数据抽象
数据类型 指代一组值以及对其执行操作的方式。
- Java编程的基础主要通过class关键字构建的是被称为 引用类型 的数据类型。
- 其本质是一种能够隐藏表示的数据类型的ADT。
1.2.1 使用抽象数据类型
1.2.1.4 对象
- 对象是能够承载数据类型的值的实体。
- 所有对象都有三大特性 ：
- 属性：即表示该类型的实例变量。
- 唯一标识符：具有将不同对象区分开的独特属性。可以认为每个对象都有一个独特的唯一标识符（每个类都必须提供一个构造函数以生成该对象的唯一标识符）。
- 操作：数据类型的基本功能或操作（如初始化、读取、写入等）。
- 引用：它是访问特定对象的方式之一（通过调用相关的方法或函数来获取所需的数据）。
1.2.2 抽象数据类型举例
1.2.3 抽象数据类型的实现
1.2.3.5 API 用例与实现
我们思考的重点并不是如何通过行动去实现某个计算性目标 而是基于用例的设计需求 采用下面三步走的方式利用抽象数据类型去满足这些需求
- 用例通常涉及哪些操作？
- 什么样的数据类型及其值能够最佳地支持这些操作？
创建一个API接口：该接口的主要作用是将 功能与实现区分开来 ，从而促进模块化设计并提高系统的可维护性
1.2.4 更多抽象数据类型的实现
1.2.4.2 维护多个实现
同一份API拥有多种不同的实现方案。
通常会采用一种 非标准化的命名方式来标识同一份API的不同功能模块。
建议保留一个无前缀的标准实现作为基准。
1.2.5 数据类型的设计
抽象数据类型是一种向用例隐藏内部表示的数据类型。
我们所遵循的编程范式强调将大型软件系统分解为可独立运行并易于维护的小模块（这种做法也增强了代码重用性）。
Java系统的新版本通常引入了多种数据类型或静态方法库的更新,而这些修改并未影响其API接口.
1.2.5.8 等价性
equals 模板
@Override
public boolean equals(Object obj) {
//如果引用相同，直接返回true 不需要其他测试工作
if (this == obj) {
return true;
}
//对象为空直接返回false
if (obj == null) {
return false;
}
//两个对象的类不同
if (obj.getClass() != this.getClass()) {
return false;
}
// //书上没这么用，还是直接getClass比较好
// if (!(obj instanceof Date)) {
// return false;
// }
//强制类型
Date that = (Date)obj;
if (that.day != day) {
return false;
}
if (that.year != year) {
return false;
}
if (that.mon != mon) {
return false;
}
return true;
}1.2.5.10 不可变性
Immutable data types, the values of objects of such types cannot be altered once created (final modifier).
* eg：String-
可变数据类型，能够操作并改变对象中的值
- eg：数组
1.2.5.13 断言
契约式设计 的编程模型主要体现的是断言思想的应用。
数据类型的定义者需要明确说明前置条件（即调用某个函数或方法时必须满足的前提条件）。例如，在二分查找算法中，必须确保输入数组是有序的才能实现有效的查找操作。
此外，在实现这些功能时还需要阐述后置条件（即在执行完该操作后必须满足的特定要求）。
需要注意的是，在编写代码时可能会导致某些潜在的副作用发生（即程序运行过程中可能导致对象状态发生变化），因此在设计函数时应尽量避免这些潜在问题。
答疑：
为了确保非静态字段的数据类型保持不可变，并且在每次对象生命周期变化时能够保持一致性, 必须实现本地副本获取机制. 该机制通常被称为 protected copy.
1.3背包、队列和栈
1.3.1 API
1.3.1.4 背包
该集合数据类型不允许从其中删除元素——其主要功能是为用例收集和遍历各种元素。（当然也可以查询该集合是否为空以及获取其中元素的数量）
-
进出栈的顺序
- 进栈的顺序的已经定死了
- abc 依次进。—— a进 … b 进 … c 进 …
那么差别仅在于进栈期间的出栈元素。
如果被后面的元素已经出栈（这里有一个隐含条件即前面的元素已入栈），那么前面未出栈的元素一定是逆序出栈。
后续元素进入了系统之后，在前一阶段已经完成了进入操作（但尚未确认是否已退出系统）。
入队列与出队列的操作均需遵循一定的顺序规则。
采用Collection接口提供的Iterator属性，在处理Vector、ArrayList和LinkedList等集合时更加便捷。与传统的方法相比，在传统的get()方法遍历中单独编码每个对象时效率较低。
* 迭代器模式1.3.2 集合类数据类型的实现
参考链接：https://www.zhihu.com/question/20928981
当前无法创建 泛型数组 ，由于Java的类型系统设计并未包含显式的数组类型构造机制。
List<String>[] l = new ArrayList<String>[10];//错误
List<String>[] l = (ArrayList<String>[] )new Object[10];
Item[] a = (Item[]) new Object[N];//正确1.3.2.3 调整数组大小
以栈为案例：
- push()中，在判断数组是否足够空间时发现不足后，则会重新扩展数组。
if(N == a.length){
resize(a.length * 2);
}-
pop()中， 首先删除栈顶元素。然后数组太大就将它的长度减半。
- 检测条件为栈的大小是否小于数组的四分之一。
Item item = a[--N];
a[N] = null;//防止游离
if(N > 0 && N == a.length / 4){ // 另一条件N > 0 勿忘
resize(a.length / 2);
}
return item;调整数组的函数实现
private void resize(int size){
Item[] tmp = (Item[]) new Object[size];
for(int i = 0 ; i < N; i++){
tmp[i] = a[i];
}
a = tmp;
}1.3.2.4 对象游离
以数组实现栈的例子说明：
- 在pop操作过程中, 弹出的操作数其引用不再存在于数组中, 应该将其设为null
1.3.2.5 迭代
该集合数据类型必须具备的功能包括：
- 通过遵循Iterable接口协议
- 重写iterator方法以生成Iterator对象
- 创建一个嵌套类并使其遵循Iterator协议
- 重写hasNext方法以返回布尔值
- 重写next方法以获取下一个元素
- remove方法可以选择性地移除元素或抛出异常
数组实现的迭代 栗子：
@Override
public Iterator<Item> iterator() {
return new ReverseArrayIterator();
}
private class ReverseArrayIterator<Item> implements Iterator<Item>{
private int i = N;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
return (Item) a[--i];
}
public void remove(){
}
}链表实现的迭代栗子：
private class Itr implements Iterator<Item> {
Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item i = current.item;
current = current.next;
return i;
}
@Override
public void remove() {
}
}1.3.3 链表
链表作为数据结构的基础模型，在其构造中遵循自身定义的方式进行扩展；它要么为空状态存在与否的状态描述；要么则包含指向下一个节点的引用部分；每个节点内部存储一个通用类型的元素，并且通过引用连接到另一个链表的部分。
1.3.4 综述
- 通常情况下，在链状结构中进行操作时会从特定位置开始。
- 数组具备按索引快速定位和获取数据元素的能力。
当我们深入研究一个新的应用领域时，在这个过程中我们会按照以下步骤识别目标并关联相关问题，并利用数据结构对象来解决这些问题。具体来说：
- 明确API接口。
- 针对具体应用场景编写示例代码，并进一步明确客户的具体使用需求。
- 详细说明一种数据结构及其表示形式，并将其应用于API实现过程中的相应部分。
- 详细阐述算法的设计与实现逻辑，在该算法的基础上完善类中的相关方法。
- 评估算法的优势与适用场景。
1.4 算法分析
时间 空间
1.4.1 科学方法
- 所设计的实验必须是 可重现的
- 所有的假设必须是 可证伪的
1.4.2 观察
1.4.3 数学模型
D.E.高德纳的基本见解在于：
一个程序运行的时间主要取决于两个因素：
- 每个指令所需的时间
- 受计算机硬件、Java编译器以及操作系统的共同影响
- 指令被执行的频率
- 与程序的设计以及输入的数据密切相关
定义为~f\left(n\right), 它是当n趋向于无穷大时被f\left(n\right)所除且结果趋向于1的一种函数。定义为g\left(n\right)~f\left(n\right), 它是当n趋向于无穷大时\frac{g}{n}与\frac{f}{n}之比值趋于1。
执行最频繁的指令决定了程序执行的时间，称这些指令为 内循环 。
本书中
- 属性 可以通过实验验证来证明假设
- 定理 描述了该算法在特定成本模型下的数学特性。
附： 循环计算
1. 复杂度是线性级别的循环体
- 如果某个循环结构按照线性规律进行n次迭代，并且单次操作的时间复杂度均为O(1), 则该循环的整体时间复杂度为O(n).
-
即使该循环忽略若干常数项的操作,而忽略的部分呈线性变化,其时间复杂度依然保持在O(n)水平。
- 下面第二个栗子 以线性方式运行 N/2 次数
-
for(int i = 0; i < N ; i++){
//一系列复杂度为O(1)的步骤....
}
for(int i = 0; i < N ; i+=2){
//一系列复杂度为O(1)的步骤....
}2. 复杂度是对数级别的循环体
for(int i = 0; i < N ; i*=2){
//一系列复杂度为O(1)的步骤....
}- 关键概念
- 循环的时间复杂度等于该循环体的复杂度 乘以循环的次数 …
3. 嵌套循环复杂度分析
首先计算内部循环的时间复杂度；接着将内部循环的复杂度乘以外部循环的数量。
3. 方法调用的复杂度分析
先计算方法体的的时间复杂度.
1.4.4 增长数量级的分类
各种级别的对应的经典算法是什么
1.4.4.1 常数级别
普通语句 两个数相加
1.4.4.2 对数级别
对数的底数和增长的数量级无关（因为不同底数仅相当于一个常数因子）
1.4.4.3 线性级别
一维数组找出最大元素
1.4.4.4 线性对数级别
归并排序
1.4.4.5 平方级别
检查所有元素对
1.4.4.6 立方级别
检查所有三元组
1.4.4.7 指数级别
检查所有子集
1.4.5 设计更快的算法
sum2用于统计数组中所有互不相同的整数对之和等于零的情况数目。
首先将数组进行排序。
接着，在排序后的数组中使用二分查找技术寻找满足条件的元素对。
如果二分查找未能找到符合条件的元素对，则计数器数值不变。
当j索引大于i索引时（即找到一对满足条件的元素），计数值增加1。
对于那些j索引位于0到i之间的位置的情况（即存在另一侧可能存在的相同情况），由于我们已经考虑过这些情况了，在后续遍历过程中不会再次统计这些配对以避免重复计数。
算法的时间复杂度主要由排序操作决定为\mathcal{O}(N \log N), 而每次查询的时间复杂度则为\mathcal{O}(\log N).
public int twoSumFast(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;
}3sum问题快速解法
- (假设所有元素各不相同)
- 复杂度 N^2logN
public int threeSumFast(int[] a){
Arrays.sort(a);
int cnt = 0;
for(int i = 0; i < a.length; i++){
for(int j = i+1; j < a.length; i++){
if(Binarysearch.rank(-(a[i] + a[j]), a) > j) {
cnt++;
}
}
}
return cnt;
}本书中会尝试按照以下方式解决各种算法问题：
- 探讨并实现一种直观且简单的解决方案（通常称为暴力解法）
- 深入研究现有算法的优化方向
- 通过实验验证新方法在性能上具有优势
1.4.6 倍率实验
开发一个输入生成器来产生实际情况下的各种可能的输入
- 例如使用循环，每次将问题的输入规模增长一倍，再调用方法
public static double timeTrail(int N) {
int MAX = 100000;
int[] a = new int[N];
for (int i = 0; i < N; i++) {
a[i] = StdRandom.uniform(-MAX, MAX);
}
Stopwatch stopwatch = new Stopwatch();
ThreeSum.count(a);
return stopwatch.elapsedTime();
}
public static void main(String[] args) {
double prev = timeTrail(125);
for(int N = 250 ; true; N+=N){
double time = timeTrail(N);
StdOut.printf("%6d %7.1f ", N , time);
StdOut.printf("%5.1f\n", time / prev);
prev = time;
}
}命题C（倍率定理）当T(N)近似于aN^b lg N时，则有T(2N)/T(N)近似等于2^b。
- 通常情况下，在预测性能的公式中对数项的影响相对较小。
1.4.7 注意事项
性能分析未能得出准确的结论
- 通常是由于我们的假设基于一个或多个假设并不完全正确所导致的。
1.4.8 处理对于输入的依赖
该系统需要对输入进行建模。其困难在于：构建输入模型并非易事，并且对输入数据的分析可能极其复杂。
1.4.8.2 对最坏情况下的性能保证
命题D表明，在基于链表实现的Bag、Stack和Queue数据结构中各种操作均具有O(1)的时间复杂度，在最坏情况下表现稳定
1.4.8.3 随机化算法
随机打乱输入
1.4.8.4 操作序列
例如栈结构。依次压入N个元素后立即进行弹出操作所得其性能表现与连续进行N次压入与弹出的操作序列所表现出的不同性能特征可能存在差异。
1.4.8.5 均摊分析
定理E。对于初始为空的数据结构，在执行任意的操作序列时，在最坏情况下的结果表明：该数据结构在基于可调整大小的数组实现下运行所需的平均访问次数均不超过某个常数；其证明过程可参考第125页。
1.4.9内存
| 类型 | 所占字节数 |
|---|---|
| 对象的引用 （一般是一个内存的地址） | 8 |
| 对象开销 | 16 |
| boolean | 1 |
| byte | 1 |
| char | 2 |
| int | 4 |
| float | 4 |
| double | 8 |
| long | 8 |
-
对象开销 包括
-
用于标识目标对象的类别名称（Mark term）
-
垃圾回收相关信息
-
同步相关信息
- 填充字节 用来填充字节数
-
HotSpot遵循8字节对齐规则，在处理对象大小时，任何未达到8个字节倍数的对象都会被填充至下一个可用的空间。
-
通常来说，在64位系统中，默认情况下每个内存单元会被填充至最接近的大写字节数。
-
当我们需要详细标注一个引用占用的具体内存时，我们会将其目标对象所需空间进行精确计算并予以标注。
1.4.9.2链表
嵌套的非静态（内部)类,还需额外的8个字节（用于一个指向外部类的引用）
1.4.9.3数组
分析时，画出图像，一个一个对应写出来。
| 数组 | 字节 |
|---|---|
| 对象开销 | 16 |
| int 数组长度 | 4 |
| 填充字节 | ？ |
| … | … |
eg：
| 数组 | 字节 |
|---|---|
| 对象开销 | 16 |
| int 数组长度 | 4 |
| 填充字节 | 4 |
| double | 8 |
| double | 8 |
| 。。。 | |
| double | 8 |
每个存储着原始数据类型的数组通常占用24字节的头部信息。
其中包含了16字节的对象开销。
其中使用4字节（整数类型）来存储数组长度。
剩下的部分是填充用的零字节数目共计为4个。
- 一个对象的数组（一个对象的引用的数组），一般需要24字节的头信息
小结
| 类型 | 字节数 | 近似 |
|---|---|---|
| int[] | 24+4N | ~4N |
| double[] | 24+8N | ~8N |
| long[] | 24+8N | ~8N |
| Date[] | 24+8N + 32N | ~40N |
| double[][] | 24+8M + (24+8N)*M | ~8MN |
1.4.9.4字符串对象
三个int值：
- 偏移量
- 计数器（字符串的长度）
- 散列值
//String对象
public class String{
char[] value;
int offset;
int count;
int hash;
....
||| 字符串对象 | 字节 |
|---|---|
| 对象开销 | 16 |
| 字符串的值（引用） | 8 |
| 偏移量 （int） | 4 |
| 字符串的长度（int） | 4 |
| 散列值 （int） | 4 |
| 填充字节 | 4 |
一个长度为N的String对象通常占用40字节的空间（用于存储String对象自身的信息），此外再占用（24+2N）字节的空间（用于字符数组的部分），合计占用总量为（64+2N）字节的空间
调用subString会导致创建新的String对象（占用40个字节），但该方法能够利用同一个value数组，并通过偏移量和长度来确定其范围（从而节省了40个字节的内存空间）。
1.4.10 展望
- 不要过早优化。
- 应该注重写出正确清晰的代码。
- 但是也不能完全忽略性能
1.5 案例研究：union-find算法 136
先绘制出流程图，并标注各步骤之间的连接线以直观展示逻辑关系，在编写相应的代码实现时能够更加清晰易懂
由此得到的 数据结构的图像表示 使我们 理解算法的操作 变得相对容易。
1.5.1 动态连通性 136
等价关系可将对象划分为多个等价类。
只有在两个对象被连接时才属于同一个等价类
动态连通性的应用场景
1.5.1.1 网络
此程序具备判断我们是否有必要在p和q之间架设一条新的连接以实现通信目标的能力，并且可以通过现有的连接完成p和q之间的通信连接。
1.5.1.2 变量名等同性
在程序中，可以通过定义多个引用来指代同一对象，并在此基础上构建动态连接图来识别哪些引用实际关联到同一个对象。
并查集的应用
对问题的建模
在建立模型时，请首先深入思考所要解决的核心问题是什么。
针对动态连接性这一场景而言，在实际应用中可能需要解决以下两类问题：
- 判断两个节点是否连通，并且如果连通则需提供具体的路径
- union-find 属于第一类
- 判断两个节点是否连通，并且如果连通则无需提供具体路径
- 采用基于深度优先搜索（DFS）的方法
1.5.1.3 数学集合
在更高层次上，我们可以将所有整数 视为不同的数学集合。
当处理一个整数对p和q时，在判断它们是否 属于同一个集合。
如果结果是否定的，则将p所属的集合与q所属的集合归并到同一个集合中。
- 将 整数对 称为 连接
- 将 对象 称为 触点
- 将 等价类 称为 连通分量 （简称 分量）
Union-Find 的成本模型分析。我们在研究实现 Union-Find API 的各种算法时关注的是数组的访问次数（包括读操作和写操作）。
对于动态连通图几种可能的操作
-
查找节点所属于的组
- 数组的位置对应值，即为组号
-
判断是否属于同一个组
- 两个组的组号是否相同
-
连接两个节点使之属于同一个组
-
分别获取两个节点各自的组号信息，在同一时间点完成操作；相反地，在不同时间点的情况下，则将其中一个节点的组号更新为另一个节点的当前组号
-
统计所有现有组合的数量
- 初始化为节点的总数。每次成功连接两个节点之后，递减1.
-
API
特别注意，在本系统中采用整数来表示各个节点。例如，在某些情况下，若采用字符串来表示节点信息时，请确保可以通过某种机制将其转换为相应的数值形式以便后续处理。具体来说，在这种情况下就可以利用哈希表实现这种映射关系，并且能够将输入的String对象转换为所需的Integer类型的数值代码。
1.5.2 实现 140
public boolean connected(int p, int q) {
return find(q) == find(p);
}
public int find(int p) {
return id[p];
}
// 第一种方法， 当且仅当id[p] 与 id[q]的值相等时，p和q是连通的。
// 即以id[]的值来区分不同的分量。值同就属于同一个分量，不同就属于不同的分量
public void union(int p, int q) {
// 将p和q归并到到相同的分量中
int pID = find(p);
int qID = find(q);
// 如果p和q在同一个分量之中，则不需要采取任何行动。
if (pID == qID) {
return;
}
// 将p的分量重命名为q的名称
for (int i = 0; i < id.length; i++) {
if (id[i] == qID) {
id[i] = pID;
}
}
count--; //前面“局部”操作完以后，需要对“全局”的统计量进行更改
}1.5.2.1 quick-find算法
在同一个连通分量中的所有触点的id[] 中的值必须全部相同。
1.5.2.2 quick-find算法分析
命题F陈述：在quick-find算法中进行find()操作时仅需访问数组一次；而合并两个组件时的操作则需要访问数组次数介于(N+3)到(2N+1)之间。
1.5.2.3 quick-union算法
值得思考的是为什么 quick-find 方法会导致"牵一发而动全身"的现象发生？其原因在于每个节点所在的集合信息是独立维护的，并未采取更有益的方式进行组织。在进行修改操作时，除了逐个通知并进行修改外，并无其他更为有效的解决方案。
那么我们面临的问题是如何更有效地组织这些节点。由于存在多种不同的组织方法，在众多可能的选择中挑选出最直观的方式至关重要。其中最直观的方式是根据相同的组号来分组。回想一下之前学习过的数据结构，在这些选项中哪些能够有效地管理这些节点呢？常见的选择包括链表、图或树等数据存储方式。然而，在这几种选择中哪种在查找和修改方面的效率最高呢？毫无疑问答案就是树结构。因此我们需要探讨如何通过树的方式来表示这种层级关系以及其中的节点分布情况。
Union-Find算法被称为"联合-查找"技术，在数据结构领域具有重要地位。为每个节点分配一个唯一的标识符数组id[]时，默认赋予每个节点不同的意义，在同一个组件内任意两个节点所对应的id[]元素都是彼此所属组件内的节点编号（可能就是自身）。
“根节点”作为连通分量的标识。
//建立链接，每一个触点所对应的id[]元素 都是同一个分量中另一个的触点的名称（也可能是自己）
public int quick_find(int p) {
//找出分量的名称
while (id[p] != p) {
p = id[p];
}
return p;
}
//
public void quick_union(int p ,int q) {
//p和q的根触点 （类似于树的根节点）
int pRoot = quick_find(p);
int qRoot = quick_find(q);
if (pRoot == qRoot) {
return;
}
id[pRoot] = qRoot;
count--;// 全局的统计量更改
}1.5.2.4 森林的表示
1.5.2.5 quick-union算法分析
定义：一棵树的 规模 是其节点数量
- 树中某节点的 层级 是从根节点到该节点路径上的边的数量（即路径上的节点数目减一）
命题G： quick-union算法中find()函数执行时所需时间等于1加上与之相关的节点所属树的高度之两倍。而union和connected函数每次调用所需时间则为两次find操作的时间（如果处理的是不同子树，则需额外增加一次查找时间）
1.5.2.6 加权quick-union算法
- 目的：控制树高。以减少find查询时间。
*引入一个数组并编写相应的代码以记录树中的节点数量。
将较小（数量较少）的树根连接到较大（数量较多）的树根上。
从而降低find操作所需的时间并提升算法的整体性能
1.5.2.7 加权quick-union算法的分析
public class WeightedQuickUnion {
private int[] id;// 父链接数组，由触点索引
private int[] sz;// (由触点索引的)各个根节点所对应的分量的大小
private int count;// 连通分量的 数量
public WeightedQuickUnion(int N) {
count = N;// 一开始每个节点分属不同的连通分量
id = new int[N];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
sz = new int[N];
for (int i = 0; i < sz.length; i++) {
sz[i] = 1;// 每一个连通分量都只有一个元素，因此均为1
}
}
public int count() {
return count;
}
public int find(int p) {
// 跟随链接找到 根节点
while (p != id[p]) {
p = id[p];
}
return p;
}
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[qRoot] = pRoot;
sz[pRoot] = sz[pRoot] + sz[qRoot];
}else if (sz[pRoot] < sz[qRoot]) {
id[qRoot] = pRoot;
sz[qRoot] = sz[pRoot] + sz[qRoot];
}
count--;//连通后，连通分量总数少1
}
}Proposition H. For a set of N nodes, the depth of any node in the forest constructed by the weighted union algorithm is at most lgN.
Corollary. In the worst case, both find-connected and union operations for the weighted quick-union algorithm with N nodes experience a cost growth rate of logN.
命题及其推论的核心作用体现在加权quick-union算法是三种方法中唯一能够实现大规模实际应用的技术
1.5.2.8 最优算法
数据结构中的路径压缩算法使所有节点都被直接连接至根节点以实现高效的查找操作
public int find(int p){
int root = p;
while(root != id[root]){
root = id[root];
}
while(p != root){
int newP = p;
id[p] = root;
p = newP;
}
return root;
}