Ch1 基础

在本章中, 我们将学习在随后的章节中用于实现, 分析和比较算法的基本原则与方法. 本书使用 Java 编程, 故在第一章中涉及了诸多关于 Java 语言的基本语法和面向对象程序设计的概念. 除此之外, 背包, 队列和栈 这三种基础的 抽象数据类型 也在该章节中被介绍. 最后, 本章介绍了一些分析算法性能的方法, 并通过对连通性问题解法的讨论引出了 并查集 这个数据结构的实现.

1.1 `Java` 程序设计模型和面向对象程序设计

我们首先回顾一些重要的 Java 语言特性和 OOP 概念.

定义: 数据类型和抽象数据类型

数据类型指的是 一组值 和 一组对这些值的操作的集合, 而 Java 程序设计的基础是使用 class 关键字构造称为 引用类型 的数据类型.

要使用一种数据类型, 我们不需要知道它是如何实现的. 如果我们将一种数据类型的数据表示方式隐藏起来, 那么这样的数据类型就被称为 抽象数据类型. 在实现抽象数据类型时, 我们只需要将注意力集中在它的 API 所描述的操作上而无需关注具体的细节.

API 常被用来描述 抽象数据类型 的行为. 其作用是列出该数据类型的所有 构造函数 和 实例方法.

定义: 对象

对象是 能够承载数据类型的值的实体. Java 中所有对象均具备三个特性: 状态, 即数据类型中的值; 标识, 用于将对象加以区分; 行为, 亦即数据类型的操作.

要完全了解一个数据类型, 我们就需要它的 API, 典型用例 和实现. 为了达成用例和实现的分离, 我们可以将用例独立成含有一个静态方法 main() 的类, 并将数据类型定义中的 main() 方法预留为一个测试用例. 同样的, 在开发数据类型时, 我们可以按照下列的顺序使用 抽象数据类型 满足用例的需求:

定义一份 API 实现编程的模块化.
编写一个 Java 类实现 API 的定义.
实现多个测试用例用于验证前两步的设计和完成情况.

面向对象程序设计的一大特征是 使用数据类型的实现封装数据. 封装使我们可以独立开发用例和实现的代码, 并且确保即使以后实现部分的代码被替换成改进的版本, 用例部分也不会受到影响. 在学习数据结构与算法时, 倘若开发出更好的算法, 只需要用抽象数据类型的, 改进的实现替换原有的旧实现, 就可以保证在不改变任何用例代码的前提下改善所有这些用例的性能.

定义: 接口和子类

接口规定了一系列需要实现的方法, 它可以使两个实现了这些公共方法的, 原本没有关联的类之间建立联系. 子类允许我们在不重写整个类的前提下就能改变它的行为或者添加新的功能, 其主要思想是定义一个新类来继承父类的所有 实例方法和实例变量, 其中子类可以包含比父类更多的方法, 也可以对父类中原有的方法进行重定义.

1.2 基础抽象数据类型: 背包, 队列和栈

背包, 队列和栈的不同之处只在于其删除或访问对象的顺序. 我们首先介绍这三种数据结构的 API:

背包

`public class`	`Bag<Item>`	`implements Iterable<Item>`
	`Bag()`	创建一个空背包
`void`	`add(Item item)`	添加一个新元素
`boolean`	`isEmpty()`	检查是否为空
`int`	`size()`	元素数量

队列 (先进先出)

`public class`	`Queue<Item>`	`implements Iterable<Item>`
	`Queue()`	创建一个空队列
`void`	`enqueue(Item item)`	添加一个新元素
`Item`	`dequeue()`	删除最近添加的元素
`boolean`	`isEmpty()`	检查是否为空
`int`	`size()`	元素数量

栈 (后进先出, 下压栈)

`public class`	`Stack<Item>`	`implements Iterable<Item>`
	`Stack()`	创建一个空栈
`void`	`push(Item item)`	添加一个新元素
`Item`	`pop()`	删除最近添加的元素
`boolean`	`isEmpty()`	检查是否为空
`int`	`size()`	元素数量

下面分别介绍三种数据类型.

背包

背包是一种 不支持从中删除元素 的 集合数据类型, 其作用是帮助用例收集并迭代遍历所有收集到的元素, 并且 迭代的顺序不确定且与用例无关.

队列 (先进先出)

先进先出队列, 或简称队列, 是一种基于先进先出 (FIFO) 策略的集合类型. 在用例使用高级循环语句 foreach 迭代访问队列的元素时, 元素被处理的顺序就是 它们被添加进队列中 的顺序. 通过在程序中使用队列数据结构, 我们可以在集合保存元素的同时 保存它们的相对顺序.

下压栈

下压栈, 或简称栈, 是一种基于后进先出 (LIFO) 策略的集合类型. 和队列不同, 当用例使用 foreach 迭代遍历栈中元素时, 元素的处理顺序恰好与它们被压入的顺序相反. 通过在程序中使用队列数据结构, 我们可以在用集合保存元素的同时 颠倒保存它们的相对顺序.

下面讨论对上述三种数据类型的实现. 首先考虑一种容量固定的抽象数据类型: 定容栈:

定容栈只能处理 String, 不支持迭代并且要求用例指定一个容量. 我们可以使用 String数组 作为定容栈的数据表示方式:

public class FixedCapacityStackOfStrings {
    private String[] a;     // stack entries
    private int N;          // size
    
    // constructor
    public FixedCapacityStackOfStrings(int cap) {
        a = new String[cap];
    }

    // check whether a is empty or not
    public boolean isEmpty() {
        return N == 0;
    }

    // return the size N
    public int size() {
        return N;
    }

    // push new elem 
    public void push(String item) {
        a[N++] = item;
    }

    // pop out item
    public String pop() {
        return a[N--];
    }

    // usage cases (tests)
    public static void main(String[] args) {
       FixedCapacityStackOfStrings s;
        s = new FixedCapacityStackOfStrings(100);
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) {
                s.push(item);
            } else if (!s.isEmpty()) {
                StdOut.print(s.pop() + " ");
            }
            StdOut.println("(" + s.size() + " left on stack)")
        }
    }
}

上述代码给出的实现最明显的问题之一就是只能处理 String 对象. 我们可以使用泛型重新实现这个数据类型, 使其可以对任何类型的对象进行处理:

public class FixedCapacityStack<Item> {
    private Item[] a;       // stack entries
    private int N;          // size
    
    // constructor
    public FixedCapacityStackOfStrings(int cap) {
        // java does not allow creating generic arrays directly
        // therefore we need conversions
        a = (Item[]) new Object[cap];   
    }

    // check whether a is empty or not
    public boolean isEmpty() {
        return N == 0;
    }

    // return the size N
    public int size() {
        return N;
    }

    // push new elem 
    public void push(Item item) {
        a[N++] = item;
    }

    // pop out item
    public Item pop() {
        return a[N--];
    }

    // usage cases (tests)
    // specify the type of 'Item' is 'String'
    public static void main(String[] args) {
       FixedCapacityStack<String> s;
        s = new FixedCapacityStackOfStrings<String>(100);
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) {
                s.push(item);
            } else if (!s.isEmpty()) {
                StdOut.print(s.pop() + " ");
            }
            StdOut.println("(" + s.size() + " left on stack)")
        }
    }
}

注意上下两个实现方式的区别.

在使用泛型对数据类型的实现方式进行改进使其适用于任何类型的对象后, 我们现在需要考虑解除定容限制需要使用什么样的优化方式. Java 数组一旦创建大小无法改变, 但这不影响我们在将要改变栈内容时, 一旦检测到剩余容量不足时将原数组中的所有内容迁移到一个更大的数组中.

具体来说, 我们所进行的修改如下:

// migrate the array to a new one with its size doubled
private void resize(int max) {
    Item[] temp = (Item[]) new Object[max];
    for (int i=0; i<N; i++) {
        temp[i] = a[i];
    }
    a = temp;
}

// check if the size is too small in push()
public void push(Item item) {
    if (N == a.length) {
        resize(2*a.length);
    }
    a[N++] = item;
}

// shrink a[]'s size into a half if stack's size < 1/4 * a.length 
// to ensure the stack never overflow.
// if the portion > 1/4: tends to do more migrations since less vacant space after shrinking
// if the portion < 1/4: tends to waste memory space since array is vacant
public String pop() {
    String item = a[--N];
    a[N] = null;    // prevent object loitering
    if (N>0 && N==a.length/4) {
        resize(a.length/2);
    }
    return item;
}

还又一个需要处理的改进是防止在 pop() 实现中, 被弹出元素的引用 仍然存在于数组中而无法被 Java 垃圾收集器回收, 造成对象游离. 实现这一优化的一个有效手段是将被弹出的数组元素值设为 null, 这将 覆盖无效的引用 (也就是清除掉对它的引用), 并使得系统在用例使用完被弹出的元素后 回收它占用的内存空间.

下一个需要处理的问题是实现 iterable 接口, 使这个数据类型支持迭代:

首先需要在类声明中加入 implements Iterable<Item>, 然后需要在类中实现方法 iterator() 并返回一个迭代器 Iterator<Item>:

// we name the iterator to 'ReverseArrayIterator'
// since we need to traverse it in reverse order
public Iterator<Item> iterator() {
    return new ReverseArrayIterator();
}

而迭代器本身又是一个 实现了 hasNext() 和 next() 方法的类 的对象:

public class ReverseArrayIterator implements Iterator<item> {
    private int i = N;
    public boolean hasNext() {
        return i>0;
    }
    public Item next() {
        return a[--i];
    }
    // leave it empty, we does not want to make it possible for 
    // editing data structure inside the iterations
    public void remove() {}
}

这样, 我们从定容栈出发, 完成了 Stack API 的一种能够 动态调整数组大小 的实现. 用例支持创建任意类型数据的栈, 并可调用高级循环 foreach 语句按照后进先出的顺序对全栈元素迭代访问. 这一实现还可以用作其他 集合数据类型 的实现的模板:

// for some reason, 'Iterator' is not contained in 'java.lang'
// so we have to import it manually
import java.util.Iterator;  
public class ResizingArrayStack<Item> implements Iterable<Item> {
    private Item a = (Item[]) new Object[1]; // stack elem array
    private int N = 0;                       // the num of elements
    
    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i=0; i<N; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }

    public void push(Item item) {
        if (N == a.length) {
            resize(2*a.length);
        }
        a[N++] = item;
    }

    public Item pop() {
        Item item = a[--N];
        a[N] = null;
        if (N>0 && N == a.length/4) {
            resize(a.length/2);
        }
        return item;
    }

    public class ReverseArrayIterator implements Iterator<item> {
        private int i = N;
        public boolean hasNext() {
            return i>0;
        }
        public Item next() {
            return a[--i];
        }
        public void remove() {}
}

1.3 基础数据结构: 链表

链表是一种非 Java 直接支持的数据结构, 需要我们从零开始手动实现. 它适用于在 集合类的抽象数据类型实现 中表示数据的合适选择.

定义: 链表

链表是一种 递归的数据结构, 任何一个链表或为空, 或是指向一个节点 (Node) 的引用, 且该节点包含一个 泛型的元素 和一个 指向另一条链表的引用.

根据递归定义, 我们只需要一个 Node 类型的变量就能表示一条链表, 并保证它的值为 null 或指向另一个 next 域也指向了另一条链表的 Node 对象:

private class Node {
    Item item;
    Node next;
}

链表所表示的是 一列元素, 下面我们讨论如何在链表中向序列 插入元素 或从序列中 删除元素.

在表头插入结点:

Node oldfirst = first; 
first = new Node();
first.item = "...";
first.next = oldfirst;

注意在链表开头插入一个结点的代码只需要几行赋值语句, 故其执行时间 和链表的长度无关.

从表头删除结点:
要从表头删除结点, 我们只需要将 first 指向 first.next 即可, 而如此操作后 原来的表头结点对象 由于无法再被访问到而成为了一个将被自动回收的孤儿, 因此也无需关心垃圾回收问题. 同样的, 这个操作的执行时间也 和链表的长度无关.
```
1
 first = first.next;
```

在表尾插入结点:
一般地, 我们只需要先保存指向尾结点的链接, 创建新的尾结点并将原来的尾链接指向这个新的结点即可完成操作. 不过需要注意的是, 这一步骤不适用于链表为空的情况, 故需要额外的判断:

 Node oldlast = last; 
 last = new Node();
 last.item = "...";
 oldlast = last;

可见对于链表, 在表头插入, 删除结点和从表尾插入结点都不困难. 但是, 如果我们需要删除指定的结点和在指定结点前插入一个新结点则必须 遍历整个列表. 一个棘手的例子是, 我们必须便利整条链表并找到指向尾结点的结点才能将链表的尾结点删除, 而这种解决方案所需要的时间和链表的长度成正比.

实现对链表节点的任意插入和删除操作的标准解决方式是使用 双向链表, 其每个节点都含有两个 分别指向不同方向 的链接, 其具体实现就是单链表的简单扩展, 在此不多赘述.

要遍历链表, 我们只需将循环的索引变量 x 初始化为链表的首结点, 然后通过 x.item 访问与 x 相关的元素, 再将 x 设为 x.next 访问链表中的下一结点, 循环往复直到 x 为 null 为止:

for (Node x=first; x!=null; x=x.next) {
    // process x.item(s)
}

使用链表实现 `Stack API`

将栈保存为一条链表, 将表头视为栈顶, 实例变量 first 指向栈顶, 这样在向栈内 压入元素 时, 该元素会添加在表头, 而 弹出元素 时该元素会从表头删除.

要实现 size() 方法, 只需使用一个实例变量 N 保存元素的个数, 并在 压入或弹出 元素时同步更新. 而实现 isEmpty() 方法的方式就是检测 N 是否为 $0$:

public class Stack<Item> implements Iterable<Item>{
    private Node first;     // top of the stack
    private int N;          // length of the stack

    // a nested class defining node
    private class Node {
        Item item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return N;
    }

    public void push(Item item) {
        Node oldfirst = first; 
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }

    public Item pop() {
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
    
    // we will talk about the implementation of iterator later...
}

使用链表实现 `Queue API`

将队列表示为一条从 最早插入的元素 到 最近插入元素 的链表, 其中实例变量 first 指向 队列的开头, 实例变量 last 指向 队列的结尾.

要将一个元素入列, 就需要将其添加到表尾, 但是注意, 在链表为空时所新添加的元素 既为队首又为队尾, 因此我们需要将两个实例变量 first 和 last 同时指向它.

要将一个元素出列, 只需要删除 表头的结点, 而在 出列后链表为空 时需要更新 last 的值:

public class Queue<Item> implements Iterable<Item>{
    private Node first;     // first node of the queue
    private Node last;      // last node of the queue 
    private int N;          // length of the queue

    // a nested class defining node
    private class Node {
        Item item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return N;
    }

    public void enqueue(Item item) {
        Node oldlast = last; 
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) {
            first = last; 
        } else {
            oldlast.next = last;
        }
        N++;
    }

    public Item dequeue() {
        Item item = first.item;
        first = first.next;
        if (isEmpty()) {
            last = null;
        } 
        N--;
        return item;
    }
    
    // we will talk about the implementation of iterator later...
}

使用链表实现 `Bag API`

只需对 Stack API 的链表实现进行简单改动即可实现 Bag API:

public class Bag<Item> implements Iterable<Item>{
    
    // actually we don't care the order of adding items to the bag
    // since it's orderless
    private Node first;     // top of the bag
    private int N;          // length of the bag

    // a nested class defining node
    private class Node {
        Item item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return N;
    }

    public void add(Item item) {
        Node oldfirst = first; 
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    
    // we will talk about the implementation of iterator later...
}

下面考虑迭代的实现. 我们首先需要引用 Java 的 Iterator 接口 并在类定义中加入对 Iterable 接口的实现声明:

import java.util.Iterator;

随后我们提供 iterator() 方法:

public Iterator<Item> iterator() {
    return new ListIterator();
}

然后实现 ListIterator(), 这个类需要提供 hasNext(), next() 和 remove() 方法供 用例的 foreach() 语句使用:

private class ListIterator implements Iterator<Item> {
    private Node current = first;
    
    public boolean hasNext() {
        return current != null;
    }

    public void remove() {
        // intentially left blank to prevent data modification inside the `foreach` loop
    }

    public Item next() {
        Item item = current.item;
        current = current.next;
        return item;
    }
}

1.4 算法分析

进行算法分析的目的是 研究计算机程序的运行时间. 其研究基础是 科学方法, 这一被科学家用来理解自然世界的方法对于我们研究计算机程序的运行时间同样有效:

细致地观察真实世界的特点, 伴随精确的测量.
根据观察结果提出假设模型.
根据模型预测未来的事件.
继续观察, 并核实预测的准确性.
如此反复, 直到确认预测与观察一致.

我们下面介绍用于算法分析的 数学模型:

我们可以构造出一个数学模型描述任意程序的运行时间, 即使实际上程序的运行时间受许多复杂的因素影响. 我们认为, 一个程序运行的总时间主要和两点有关:

执行每条语句的耗时.
执行每条语句的频率.

前者取决于计算机, 编译器和操作系统, 而后者取决于程序的本身及其输入. 在对程序的所有部分而言我们都知道了这些性质之后, 我们可以将其相乘并将程序中所有指令的成本相加, 即得到了 总运行时间.

基于上述规则的频率分析可能会产生复杂的数学表达式, 因此我们需要将其简化. 一般地, 我们可以直接忽略表达式中那些 非常复杂 但是 幂次较低, 且对最终结果的贡献 无关紧要 的项:

定义: 近似

记所有随着 $N$ 的增大而使得其除以 $f(N)$ 所得最终趋向于 $1$ 的所有函数为 $\sim f(N)$. 用 $g(N) \sim f(N)$ 表示 $\frac{g(N)}{f(N)}$ 随着 $N$ 的增大趋近于 $1$.

定义: 程序内循环

对于大多数程序而言, 其中执行最频繁的指令决定了程序执行的总时间, 我们称这样的指令为程序的 内循环.

定义: 成本模型

定义了我们所研究的算法中的 基本操作 的模型称为 成本模型, 我们使用成本模型来评估算法的性质.

对于大多数程序, 得到其运行时间的数学模型需要如下的步骤:

确定 输入模型, 定义问题的规模.
识别程序的 内循环.
根据内循环中执行的操作确定程序的 成本模型.
对于给定的输入, 判断这些操作的执行频率.

我们下面给出一些算法分析的常见函数和常用近似函数:

算法分析的常见函数:

描述	记号	定义
自然对数	$\ln(N)$	$x = \log_{e}(N), ~~ e^{x} = N$
以 $2$ 为底的自然对数	$\lg(N)$	$x = \lg_{2}(N), ~~ 2^{x} = N$
以 $2$ 为底的整型对数	$\lfloor \lg(N) \rfloor$	不大于 $\lg(N)$ 的最大整数
调和级数	$H_N$	$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{N}$

算法分析中常见的近似函数: |描述|近似函数| |:-|:-| |调和级数求和|$H_N \sim \ln(N)$| |$\text{Stirling}$ 公式|$\lg(N!) \sim N \lg(N)$| |指数函数|$(1-\frac{1}{x})^x \sim \frac{1}{e}$|

我们再总结一下 增长数量级 的分类:

常数级别

运行时间增长数量级为常数的程序完成其指定任务所需的操作次数固定, 运行时间不依赖任何变量.

对数级别

运行时间增长数量级为对数的程序比常数时间的程序稍慢, 一个经典的例子是 二分查找.

线性级别

使用 常数时间 处理数据中的所有元素或基于单个 for 循环的程序增长的数量级就是线性的, 其运行时间和 $N$ 成正比.

平方级别

运行时间的增长数量级为 $N^2$ 的程序一般含有两个嵌套的 for 循环.

立方级别

和平方级别程序类似, 一个运行时间增长数量级为 $N^3$ 的程序一般含有三个嵌套的 for 循环.

指数级别

这样的程序运行时间和 $2^N$ 或更高级别的函数成正比.

1.5 案例研究: 并查集

下面我们通过一个基础的计算性问题说明设计和分析算法的基本方法.

首先对问题进行说明: 问题的输入是 一列整数对, 其中每个整数都表示一个某种类型的对象, 一对整数 $p, q$ 可被理解为 $p, q$ 是相连的. 并且, 我们假设 “相连” 是一种 等价关系, 这意味着它同时具备 自反性, 对称性和传递性.

等价关系能够将对象分为 多个等价类, 在我们的问题中, 两个对象当且仅当它们相连时才属于同一个等价类. 而我们的目的是编写程序过滤掉序列中所有 无意义的 整数对, 也就是那些 两个整数同属一个等价类 的整数对.

为了达到所期望的效果, 我们需要设计一个数据结构用于保存程序已知的 全部整数对 的 足够多的信息, 并使用这些信息来判断一对新对象是否是相连的. 这个问题一般被称为 动态连通性问题, 它在网络 (计算机网络, 社交网络, 集成电路网络等), 物理学等方面均有广泛的应用.

我们同时规定使用网络方面的术语以限定话题. 我们将 “对象” 称为 “触点”, 将一个整数对称为 “连接”, 将等价类称为 “连通分量” 或是 “分量”. 并且用 $0$ 到 $N-1$ 标记这 $N$ 个触点.

为了 精确的定义问题, 我们将设计一份 API 封装所需的基本操作: 初始化, 连接两个触点, 判断包含某个触点的分量, 判断两个触点是否处于同一分量之重, 以及返回所有分量的数量.

`public class UF`
	`UF(int N)`	以整数标识初始化 $N$ 个触点
`void`	`union(int p, int q)`	连接 $p$ 和 $q$
`int`	`find(int p)`	返回$p$ 所在的分量的标识符
`boolean`	`connected(int p, int q)`	检测 $p$ 和 $q$ 是否在同一个分量中
`int`	`count()`	返回连通分量的数量

若两个触点在不同的分量中, union() 操作会将两个分量归并. find() 操作会返回给定触点所在的连通分量的标识符, connected() 操作能判断两个触点是否存在于同一个分量中, count() 方法会返回所有连通分量的数量.

对这份 API 的实现等价于解决所提到的动态连通性问题. 所有的实现都应该:

定义一种表示 已知连接 的数据结构.
基于此数据结构实现高效的 union(), find(), connected(), count() 方法.

我们首先使用一个以触点为索引的数组 id[] 作为基本数据结构, 实现该 API:

public class UF {
    private int[] id;   // the id of the components
    private int count   // the number of the components

    // constructor responsible for initialization
    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) {
        // we will implement it later...
    }

    public void union(int p, int q) {
        // we will implement it later...
    }
}

Union-Find 的成本模型是: 数组的访问次数 (访问任意数组元素的次数, 无论读写均算在内).

下面, 我们将讨论三种均根据以触点为索引的 id[] 数组确定两个触点是否存在于相同的连通分量中的不同实现:

`quick-find` 算法

一种方法是, 保证 当且仅当 $\text{id}[p] = \text{id}[q]$ 时 $p$ 和 $q$ 相通. 也就是说, 位于同一个连通分量中的触点在 $\text[id][]$ 中的值必须 全部相同. 在此基础上, 我们有:

对于 connected(p, q), 它只需判断 id[p] == id[q], 当其为真时才返回 true.
对于 union(p, q), 首先需要检测 p 和 q 是否已经位于同一分量中, 若不是的话, 他就需要 遍历数组 将一类分量中所有的触点对应的值修改为另一分量对应的值.

基于这一原则的实现如下:

public int find(int p) {
    return id[p];
}

public void union(int p, int q) {
    int pID = find(p);
    int qID = find(q);

    // check whether p and q are already "identical"
    if (pID == qID) {
        return;
    }

    // if not, modify p's component into q's value
    for (int i=0; i<id.length; i++) {
        if (id[i] == pID) {
            id[i] = pID;
        }
    }
    count--;    // merged, num of components -1
}

算法分析:

find() 操作显然是极快的, 因为它只需要访问一次 id[] 数组. 但由于对于每一对输入, union() 都需要扫描整个 id[] 数组, 因此它并不适用于大型问题.

命题 1.1

在 quick-find 算法中, 归并两个变量的 union() 操作访问数组的次数在 $(N+3)$ 到 $(2N+1)$ 之间.

证明

归并两个分量的 union() 操作首先需要调用两次 find(), 而显然每调用 find() 一次, 智慧访问一次数组; 然后 union() 操作要检查 id[] 数组中的所有元素, 并改变它们中的最少 $1$ 个, 最多 $N-1$ 个的值. 因此访问次数在 $2+N+1 = N+3$ 到 $2+N+(N-1) = 2N+1$ 之间. $\blacksquare$

假如我们使用 quick-find 算法解决动态连通性问题并最后只得到了一个连通分量, 则这至少需要调用 $N-1$ 次 union(), 也就是至少 $(N+3)(N-1)$, 即近似于 $N^2$ 次数组访问. 因此, 我们可以立刻猜想得到, 该算法的复杂度是 $n^2$ 级别的. 为了提高 union() 的速度, 我们需要继续改进.

`quick-union` 算法

下面我们讨论的重点是提高 union() 的速度. 该算法和 quick-find 互补, 也基于相同的数据结构: 以触点作为索引的 id[] 数组. 但在该算法中, 我们定义每个触点所对应的 id[] 元素均为 同一个分量中另外一个触点 (也可能是它本身) 的名称, 并且我们将这种联系称为链接.

在实现 find() 方法时, 我们从给定的触点开始由其链接得到另一个触点, 并如此继续就可以顺藤摸瓜直到到达一个指向其自身的 根触点, 而如果两个触点存在于同一个连通分量中, 那么由它们开始一定可以分别最终到达 同一个根触点.

这一特性需要小心的实现 union() 方法来保证. 在合并分量 (union(p, q))时, 我们需要由 p 和 q 的链接分别找到它们的根触点, 然后将一个根触点链接到另外一个上就可以将两个分量合二为一.

private 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;
    }
    id[pRoot] = qRoot;
    count--;
}

算法分析:

看上去 quick-union 算法比 quick-find 要快, 因为它并不需要为每对输入 遍历整个数组. 在最坏情况下, fund() 需要 $2N-1$ 次数组访问才能得到一个触点所在的分量标识, 而在最好情况下只需要 $1$ 次. 由于我们完全可以构造一个最坏情况的输入使得其运行时间为 $n^2$ 级别, 因此它并不能在所有情况下都取得比 quick-find 算法更好的表现.

加权 `quick-union` 算法

对 quick-union 算法进行简单的修改就能显著地提升它的性能. 不同于 quick-find 的union() 实现, 我们现在会在将两个分量合并前记录每一个分量所对应的链接树的大小, 并总是将 较小的树连接到较大的上.

public class WeightedQuickUnionUF {
    private int[] id;   // father-links array (node index)
    private int[] sz;   // each root-node's corresponding components' size
    private int count;  // num of components

    public WeightedQuickUnionUF(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;
        }
    }

    public int count() {

        return count;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    private int find(p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    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--;
    }
}

命题 1.2

对 $N$ 个触点, 加权 quick-union 算法构造的森林中任意节点的深度最多为 $\lg(N)$.

证明

下面通过证明一个更强的命题解决这个问题: 森林中大小为 $k$ 的树高度最多为 $\lg(k)$.
初始情况: $k=1$ 时树的高度为 $0$.
归纳假设: 大小为 $i$ 的树高度最多为 $\lg(i)$, 其中 $i \leqslant k$.

设$i \leqslant k$ 且 $i+j=k$. 而当我们将大小为 $i$ 和 $j$ 的树合并时, 较小的树中所有节点的深度增加了 $1$, 而合并后的树大小为 $i+j=k$. 而 $1 + \lg(i) = \lg(2i) = \lg(i + i) \leqslant \lg(i+j) = \lg(k)$ 故性质成立. $\blacksquare$

推论

对于 加权 quick-union 算法 和 $N$ 个触点, 在最坏情况下 find(), connected() 和 union() 的成本增长数量级为 $\log(N)$.

证明

在森林中, 对于从一个结点到它的根结点的路径上的每个结点, 每种操作最多只会访问数组常数次. 由上述命题得: 随着树的增长, 各种操作对数组的访问次数和树的高度呈线性关系, 故推论成立. $\blacksquare$

由上述命题和推论可知, 加权 quick-union 算法 处理 $N$ 个触点和 $M$ 条连接时最多访问数组的次数为

\[cM \cdot \lg(N)\]

其中 $c$ 为常数, 而 quick-find算法和 quick-union 算法的最坏情况需要访问数组

\[N \cdot M\]

次.

因此, 加权 quick-union 算法是三种算法中唯一可以解决 大型实际问题 的算法.

在 加权 quick-union 算法 的基础上, 我们可以使用 路径压缩 进一步地优化算法的性能. 理想情况下, 我们希望每个结点都直接链接到它的根结点上, 而同时不能像 quick-find 算法一样通过大量修改链接实现这一点. 为了接近这种理想状态, 我们可以在 检查节点的同时将它们直接链接到根节点. 要实现 路径压缩, 我们只需要为 find() 添加一个循环以将在路径上遇到的所有节点都链接到根结点上.

普林斯顿算法4-Ch1 基础

Basics and Union Find Set

Ch1 基础

1.1 `Java` 程序设计模型和面向对象程序设计

1.2 基础抽象数据类型: 背包, 队列和栈

背包

队列 (先进先出)

下压栈

1.3 基础数据结构: 链表

使用链表实现 `Stack API`

使用链表实现 `Queue API`

使用链表实现 `Bag API`

1.4 算法分析

常数级别

对数级别

线性级别

平方级别

立方级别

指数级别

1.5 案例研究: 并查集

`quick-find` 算法

`quick-union` 算法

加权 `quick-union` 算法

CATALOG

FEATURED TAGS

FRIENDS

Ch1 基础

1.1 Java 程序设计模型和面向对象程序设计

1.2 基础抽象数据类型: 背包, 队列和栈

背包

队列 (先进先出)

下压栈

1.3 基础数据结构: 链表

使用链表实现 Stack API

使用链表实现 Queue API

使用链表实现 Bag API

1.4 算法分析

常数级别

对数级别

线性级别

平方级别

立方级别

指数级别

1.5 案例研究: 并查集

quick-find 算法

quick-union 算法

加权 quick-union 算法

CATALOG

FEATURED TAGS

FRIENDS

1.1 `Java` 程序设计模型和面向对象程序设计

使用链表实现 `Stack API`

使用链表实现 `Queue API`

使用链表实现 `Bag API`

`quick-find` 算法

`quick-union` 算法

加权 `quick-union` 算法