COMP26120 REVISION

1. 算法设计与复杂度分析

定义 1.1 (算法)

称一系列精确定义地, 用于解决特定计算问题的步骤和流程为算法.

定义 1.2 (抽象数据类型, Abstract Data Type, ADT)

称一个对 抽象化的数据对象本身 , 数据对象之间的关系 和 可对数据对象进行的基本操作 的需求 (定义) 为 抽象数据类型, 本质上描述了一个数据模型与定义在这个模型上的一组运算.

定义 1.3 (数据结构)

数据结构是对 某种抽象数据类型 的具体实现.

举例来说, 字典, 数组, 栈, 队列都是抽象数据类型, 而动态表 (Dynamic Array), 链表, 二叉树, 哈希表, 堆等都属于数据结构.

1.1 算法时间复杂度分析的基本方法和基本定义

1. 算法时间复杂度的粗略分析: 以冒泡排序为例

冒泡排序核心部分的伪代码如下:

for(i=0; i<N-1; i++) {
    for(j=0; j<N-1; j++) {
        if (a[j] > a[j+1]) {
            t = a[j];
            a[j] = a[j+1];
            a[j+1] = t;
        }
    }
}

我们的任务是对这段代码片段进行粗略的复杂度分析. 可见在上述代码片段中, 共有 $2$ 个嵌套的循环, 每个循环执行 $n-1$ 次. 由此可以直接判断, 该代码片段的空间复杂度为 $O(n^2)$,

同时注意冒泡排序的核心逻辑: 内层循环的作用是将数组中的最大 (或第二大, 第三大,…) 元素从原始位置挨个和后面的元素比较, 将其对换 (“冒泡”) 到数组末尾, 而为了确保数组所有位置上的元素都能被这样检查一遍, 需要将内层循环执行 $n-1$ 次.

2. 算法的渐进性能: 以线性查找和二分查找为例

下面以 线性查找 与 二分查找 为例分析并对比两种查找算法的渐进性能:

定义 1.4 (渐进性能)

算法的 渐进性能 指在给定输入的大小无限逼近于无穷大时, 算法的 运行时间, 存储和内存占用 等系统资源消耗情况等指示算法性能指标的变化情况.

首先以 线性查找 为例:

j=1;

while (j <= A.length && A[j] != q) {
    j++;
}

if (j < length(A)) {
    return j;
} else {
    return null;
}

显然在最坏情况下, 循环需要执行 $n$ 次才能找到需要的元素, 在最好情况下只需要执行 $1$ 次, 而在一般情况下需要执行 $\frac{n}{2}$ 次. 考虑最坏情况, 线性查找的时间复杂度为 $O(n)$.

然后以 二分查找 为例:

l = 1;
r = A.length;
while (l <= r) {
    j = l + (r - l)/2;
    if (A[j] == target) {
        return j;
    } else if (A[j] > target) {
        r = j - 1;
    } else {
        l = j + 1;
    }
}
return null;

注意二分查找的前提是: 假设待查找的数组已经是经过排序的. 在这一情况下, 二分查找每次都会将数组内的搜索范围折半 , 结合一些简单的数学知识可知二分查找的时间复杂度为 $O(\log(n))$.

下面说明我们进行复杂度分析所依赖的计算机简化模型: 在该模型中我们认为:

对 任何内存地址的访问 消耗的时间和其他资源相同.
不考虑指令并行执行的情况.
除了对函数的调用以外, 所有的指令执行时间相同.
除非特殊指定, 否则规定字长 (word size) 为某个常数.

换言之, 在计算运行时间时, 我们本质上进行的是对 基础指令条数 (Number of primitive steps) 的计数.

而我们所得出的, 表示 最坏情形 的结果提供了一个清晰明确的, 对算法运行可能消耗的时间的上界, 它相当于某种 绝对保证: 不存在任何情况, 使得算法的运行时间超过它.

而表示 一般情形 的结果所提供的是 算法运行时间的数学期望, 但需要注意, 随着我们对 “一般” 概念定义的变化, 所得到的结果也会有所不同, 它并不一定能满足真实的情况.

3. 研究算法的时间复杂度: 以插入排序为例

我们首先给出插入排序的伪代码:

InsertionSort(A, n) {
    for (i=2; i<n; i++) {
        key = A[i];
        j = i-1;
        while (j>0 && A[j] > key) {
            A[j+1] = A[j];
            j -= 1;
        }
        A[j+1] = key;
    }
}

插入排序的循环不变量是: 始终认为数组片段 $A[0:i-1]$ 是 顺序排列 的, 而每次循环都是一次将新元素 $A[i]$ 插入到这个子数组中同时维护子数组顺序的过程.

我们对插入排序资源消耗的分析如下:

20220106173409

其中 $t_i$ 就是在第 $i$ 次循环中, 内层 while 的执行次数, 本质上就是 $A[j]$ 和 key 的比较次数.

在最好情况下, 内层循环无需执行; 而在最坏情况下, 所有的内层循环都需要执行. 此时可知:

20220106173705

也就是说, 插入排序的时间复杂度为 $O(n^2)$.

4. 对基本记号和概念的定义

最后给出复杂度分析中基本记号和概念的定义:

定义 1.5 (Big-O)

记 $O$ 表示函数具有 渐进上界 (Asymptotic upper-bound):
\[O(g(n)) = \{f(n) ~:~ \exists c > 0, n_0 > 0, ~\text{s.t.} ~ \forall n \geqslant n_0; 0 \leqslant f(n) \leqslant c \cdot g(n)\}.\]

定义 1.6 (Big-Omega)

记 $\Omega$ 表示函数具有 渐进下界 (Asymptotic lower-bound):
\[\Omega(g(n)) = \{f(n) ~:~ \exists c > 0, n_0 > 0, ~\text{s.t.} ~ \forall n \geqslant n_0; 0 \leqslant c \cdot g(n) \leqslant f(n)\}.\]

定义 1.7 (Big-Theta)

记 $\Theta$ 表示函数具有 渐进紧确界 (Asymptotic tight-bound):
\[\Theta(g(n)) = \{f(n) ~:~ \exists c_1, c_2 > 0, n_0 > 0, ~\text{s.t.} ~ \forall n \geqslant n_0; 0 \leqslant c_1 \cdot g(n) \leqslant f(n) \leqslant c_2 \cdot g(n)\}.\]

20220106174441

若 $f(n)$ 以 $g(n)$ 为 渐进紧确界, 当且仅当 $f(n)$ 同时以 $g(n)$ 为 渐进上界 和 渐进下界.

我们再给出其他的一些不常用的渐进符号定义:

20220106174603

需要注意, 在遇到类似于 “求证某个函数具有渐进上/下界或具有渐进紧确界” 的问题时, 解决问题的基本流程是基于求证假设构建不等式, 通过代数变型求得常数 $c$ (或 $c_1, c_2$) 的取值范围. 若的确可以找到这样的常数, 则说明假设得证. 比如:

20220116111702

20220116111911

1.2 分治

定义 1.8 (分治法)

分治法是一种通过将给定问题递归地分划为规模更小的子问题, 并逐一解决这些子问题从而解决给定问题的算法设计思想. 使用分治法思想设计的算法包含三个部分:

分划 (Divide): 将原问题拆分成规模更小的子问题.

解决 (Conquer): 递归地解决这些拆分出来的小问题.

联合 (Combine): 将解决的小问题联合从而形成对原问题的一个解.

分治问题的复杂度表达式一般形如:

20220106175014

其中 D(n) 为 问题分划消耗的时间, aT(b/b) 为 划分的 $a$ 个子问题, C(n) 为 将解决的子问题重新组合消耗的时间.

我们下面以 归并排序 (Merge Sort) 为例探讨分治法的运作过程. 归并排序的伪代码如下:

MergeSort(A, l, r) {
    if (l < r) {
        mid = l + (r-l)/2;
        MergeSort(A, l, mid);
        MergeSort(A, mid+1, r);
        Merge(A, l, r, mid);
    }
}

Merge(A, l, r, mid) {
    // take 2 sorted subarrays of A and merge them into 1 single sorted array
    n1 = mid-l+1
    n2 = r-mid

    for (i=0; i<n1; i++) {
        L[i] = A[l+i];
    }
    for (j=0; j<n2; j++) {
        R[j] = A[mid+1+j];
    }
    L[n1], R[n2] = +infty;
    i, j=0;
    for (k=l; k<r+1; k++) {
        if (L[i] <= R[i]) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
        }
    }

}

可见归并排序的原理是递归地将给定的数组拆分成大小相同的左右两个子数组, 然后对这两个子数组递归地调用自身 (实际上就是对子数组再次进行拆分), 直到将数组拆成只由一个元素组成, 无法再拆为止. 然后再使用 Merge() 方法, 将这些被拆分的数组两两结合成较大的, 保持顺序的数组, 同样递归地最终合成为原数组的已排序形式.

对归并排序资源消耗的分析如下:

20220106175936

显然有:

20220106180024

这是一个 递归表达式. 我们再举一个例子: 二分查找算法:

BinarySearch(A, target) {
    if (A.length == 1) {
        return A[0] == target;
    }

    mid = A.length/2;
    if (target < A[mid]) {
        BinarySearch(A[0 : mid-1], q);
    } else {
        BinarySearch(A[mid :], q);
    }
}

显然二分查找的递归表达式可以记为:

20220106180412

我们将在下一节中介绍求解递归表达式的一般方法: 替代法 (Substitution Method), 递归法 (Iteration Method) 和 主方法 (Master Method).

1.3 求解递归表达式

替代法 (Substitution Method): 基本原理是 猜测正确答案的形式 (猜测给定递归表达式的时间复杂度), 然后使用 数学归纳法 (Induction) 证明这个猜测成立.

值得注意的是, 在替换法中, 有时我们可以使用适当的技巧简化问题. 如:

在上面的例子中, 我们 通过将递归表达式右侧式子中的函数项和加号右侧的代数项替换为正常形式, 成功地将问题转换为我们可以解决的形式.

而在考虑 “将什么变量替换成什么形式” 的问题时, 可以优先考虑将等号右侧加号右边的项替换为一个 一次项, 如将 $\log(n)$ 替换为 $m$. 在此基础上, 再检查经过这样替换后的递归公式是不是被简化成了我们已知的一些常见形式. 如果是的话, 就可以使用替代法求解.

我们再附上一些指数, 对数, 阶乘和级数的常用性质:

此外, 我们还可使用定积分近似某个求和表达式:
递归法 (Iteration Method) 递归法的基本原理是: 给定某个算法的递归表达式, 利用表达式自身循环定义的特性, 不断地将等式右侧的表达式使用递归定义 “解压缩”, 直到展现出某个明显的规律为止.

然后, 尝试将等号右侧已经表现出一定规律的式子中左边函数定义的那部分中的变量进行替换或变形, 从而使该变量等于函数递归表达式定义中 Base Case 对应的变量值. 这样, 我们就可以将函数定义的那部分直接替换为 Base Case 对应的式子 (但一般都是个数值), 从而可以直接看出表达式的时间复杂度.

举例:
使用主定理 Master Theorem

下面给出一些常用结论:
\[\begin{aligned} T(n) &= T(n-1) + O(1) ~~~ \rightarrow \Theta(n) \\ T(n) &= 2T(\frac{n}{2}) + O(1) ~~~~~~~\rightarrow \Theta(n) \\ T(n) &= T(\frac{n}{2}) + O(1) ~~~~~~~~~\rightarrow \Theta(\log(n)) \\ T(n) &= T(\frac{n}{2}) + O(n) ~~~~~~~~~\rightarrow \Theta(n\log(n)) \end{aligned}\]

1.4 算法性能的均摊分析

考虑算法在 最坏情况下的时间复杂度 可以给我们算法运行耗时的上限, 但在实际情况下这样的分析往往会 低谷算法在平均状态下的性能. 为了从另一个角度对算法的时间复杂度进行评估, 我们引入了 均摊分析 的概念.

在 均摊分析 (Amortised Analysis) 中, 我们根据具体要求 构造出一个由一系列操作组成的指令序列 (sequence), 然后通过计算和讨论这个序列执行耗时的方式研究给定算法在这种情况下的性能.

20220116125032

常用的均摊分析方法有三种:

Aggregate Method 聚合法.
Accounting Method 审计法.
Potential Method 势能法.

在本课程中, 我们只介绍第一种方法. 聚合法单纯计算序列中每个操作消耗的平均时间, 忽视操作之间可能存在的区别.

(后面提到的, 关于动态增删数组, 栈操作和二进制加减法的例子建议直接看 Slides, 此处省略)

20220116125609

2. 基本数据结构

从本节开始我们将讨论一系列的基本数据结构. 首先回顾 抽象数据类型 的基本概念:

20220107155651

而 数据结构 是对 抽象数据类型 的 具体实现:

20220107155739

基于这个定义, 动态数组 (Dynamic Array) 可被定义为由以下的 API 组成的抽象数据类型:

20220107155919

链表 (Linked List) 可被定义为由以下的 API 组成的抽象数据类型:

20220107155948

2.1 哈希表

哈希表本质上是称为字典的 ADT 的一种实现, 是 数据结构. 我们首先阐述哈希表数据结构需要满足的 API:

20220107160749

哈希表的基本工作原理是:

在将数据插入表中时, 使用经过精心设计的 哈希函数, 基于被插入数据本身的特性得到一个索引, 然后将数据存到实际负责数据存储的数组的索引位置上.
如果数组的索引位置上已经有数据存储, 也就是发生了 “数据碰撞” (Collision), 则需要再基于某些规则重新生成一个新的索引, 把数据存到别的位置上去从而避免碰撞.
在从表中提取数据时, 同样需要使用哈希函数算出索引, 然后按图索骥从数组中找到所需要的数据.
在实际负责数据存储的数组剩余空间不足时, 需要将其扩容并将原数组中存放的所有元素全部重哈希到更大的新表中.

哈希表在理想状态下的读/写性能均为 $O(1)$, 这样的性能优化得益于哈希函数. 在最好情况下, 数据碰撞不会发生, 因而只要计算一次哈希函数就可得到索引.

下面讨论几个哈希表实现中的问题:

什么是合理的哈希函数?

合理的哈希函数应当具有以下性质:

给定一个映射范围 $n$ 和被映射元素集合 $U$, 哈希函数 $f$ 应该能将 $U$ 中的每个元素 均匀地 映射到 $[0, n)$ 的范围上.

能够正确区分性质相似的数据, 如包含相同元素而排列顺序不同的字符串.
我们无法避免数据碰撞的发生. 一旦发生数据碰撞, 有哪些可行的方法解除数据碰撞?
- Separate Chaining: 若多个数据被哈希函数映射到数组的同一个位置上, 则在数组的该位置上存储一个链表, 将这些数据按照插入的先后顺序挂到链表上.
  
  在实际应用中, 只要哈希函数的选取和重哈希策略得当, 在数组中即使存在数据碰撞, 该位置上的链表也不会很长.
- Open Addressing: 开放寻址, 在确定出现数据碰撞后使用预定义的规则再生成新的位置, 直到生成的新位置上不存在数据碰撞为止.
  
  在实际应用中, 如果规则定义不当, 就容易在哈希表中出现数据堆积的情况.
  
  开放寻址的实现方式一般又有三种:
重哈希的策略是什么? 何时需要重哈希?

重哈希的策略是: 首先调整在哈希函数中涉及到的变量: 存储数组的预期大小, 然后新建一个大小为预期尺寸的, 比原数组更大的空数组.

然后, 基于这个 修改过的哈希函数 (哈希函数中取模时依赖的, 存储数组的预期大小变大了) 将原数组中的所有元素全部重哈希到新数组中.

丢掉原数组, 将更大的新数组视为哈希表的存储数组.

我们使用反映哈希表的存储数组的利用率的变量 负载常数 (Load Factor) 检测哈希表的使用率, 从而控制何时执行重哈希.

一般而言, 我们会选定重哈希阈值为 $0.75$.

如果阈值选定不当, 会导致哈希表的存储数组中可用的剩余空间过少, 以至于在查询和插入数据时哈希函数的数据碰撞次数显著增大, 在最坏情况下对哈希表的搜索操作会退化为线性搜索, 而在一般情况下搜索的时间复杂度仅为 $O(1)$.

2.2 搜索树

我们称形如现实生活中的树木的, 由某一个单一的 (根) 结点向下扩展的, 具有树状拓扑结构的数据结构为树.

一棵 (抽象的) 树由一个 根结点 , 数个 叶子结点 和在此之间的 内部节点 构成, 除了根结点外, 每个节点都有一个与之对应的 父节点; 而除了叶子结点外, 每个节点都有至少一个 子节点.

常见的树有:

20220107203637

注意:

Proper Binary Tree/Full Binary Tree (满二叉树) $\Rightarrow$ 每个节点的度或为 $0$ 或为 $2$.
Complete Binary Tree (完全二叉树) $\Rightarrow$ 叶子结点只出现在 最下层或次下层, 且 最下层的叶子结点集中出现在树的左部 (除了最后一层外, 其他各层节点数都达到最大, 且最后一层的节点都连续集中在最左边).
Perfect Binary Tree (完美二叉树) $\Rightarrow$ 在满二叉树的基础上, 所有叶子结点深度均相同.

而 二叉树 的 API 表示如下:

20220107203725

我们可以使用数组和链表来表示二叉树:

若用数组的形式来构建二叉树, 则节点存在数组中, 节点在数组中的位置对应它在树中的位置, 下标为 $0$ 的节点为根节点, 下标为 $1$ 是根的左节点, $2$ 为根节点的右节点, 依次类推, 从左到右的顺序存储树的每一层, 包括空节点.

给定某个节点的索引值为 $x$, 则其左子节点和右子节点的索引值分别为 $2 \cdot x + 1$ 和 $2 \cdot x + 2$, 而其父节点的索引为 $(x-1)/2$.

这种表示方法只有在存储 完全二叉树 时效率才会达到最高, 如果用于存储普通二叉树, 由于数组中会包含大量空节点, 因此实际上浪费了存储空间.

若用链表的形式来构建二叉树, 则树的每个节点都是一个链表节点, 依据树中的连接关系而相互链接. 链表法确保不存在任何空节点, 同时在执行插入和删除操作时也有很高的效率, 但是在树中检索的困难度相比数组法高了很多.

注意:

二叉树的 外部节点 (Exterior Node) 指他的叶子结点.
二叉树中结点所拥有的子树个数称为结点的度 (Degree).
二叉树的高度为树中所有节点深度的最大值, 也就是从叶子结点到根节点所需要经过的边的 最大值, 从 $0$ 起算.
二叉树中节点的深度为从该节点到树的根节点所需经过边的数量, 也是从 $0$ 起算.

再来看二叉树的插入和删除规则:

二叉树节点的插入: 只需基于给定的被插入值大小沿着树遍历, 直到在保持不变量基础上, 左子节点 (或对应的, 右子节点) 为空的节点, 然后将新节点作为该节点的左子节点/右子节点插入即可.

二叉树节点的删除:

case 1: 若要被删除的结点为叶子结点或左右子节点均为空, 则直接删除节点的父节点中, 对应指向该节点的指针.
case 2: 若要被删除的节点有一个子节点 (左子节点或右子节点), 则将该节点的父节点中, 对应的指针指向它的子节点即可.

case 3: 若要被删除的节点有两个子节点, 就需要从这个被删除节点开始执行 中序遍历 来找到它的 后继节点 $p$ (一般是左子树中的最大值所在的节点或右子树的最小值所在的节点).

然后将被删除节点和 $p$ 的值调换, 递归地执行对节点 $p$ 的删除操作, 这也是删除根节点所对应的状况:

   TreeNode delNode(TreeNode root, int key) {
            
       // 先遍历到目标节点位置上, 若找不到目标节点则直接返回当前所在节点不改动树
       if (! root) {
           return root;
       } else if (root.val > key) {
           root.left = delNode(root.left, key);
       } else if (root.val < key) {
           root.right = delNode(root.right, key);
       } 
            
       // 定位到节点后开始删除
       else {
           // case 1, 2: 直接删除, 子树提升一级
           if (root.left == null || root right == null) {
               root = root.left? root.left: root.right;
           } else {
           // case 3: 找到右子树中被删除节点的后继, 交换值后递归删除后继
               TreeNode current = root.right;
               // 中序遍历找后继
               while (current.right) {
                   current = current.left;
               }
               // 交换节点值
               root.val = current.val;
               // (递归) 删除后继, 或者后继的后继, ....
               root.right = delNode(root.right, root.val);
           }
       }
       return root;
   }

一般对二叉树的检索 (遍历) 方法有三种: 前序, 中序与后序遍历:

20220107204458

20220107204519

20220107204530

而对树的搜索方式也有两种: 优先沿着子节点检索每一条路径的深度优先搜索 和 优先检索同深度下的其他节点, 然后再检索更高深度下子节点的广度优先搜索.

20220107204700

20220107204717

二叉搜索树相比二叉树, 限定了每个节点和其子节点之间, 节点值大小的相对关系, 使其可以用于表示经过排序的数组, 在二叉搜索树中搜索任意数据在一般情况下可以获得 $O(\log(n))$ 的时间复杂度.

二叉搜索树中的不变量为: 对任何节点, 左子节点的值小于等于父节点的值小于右子节点的值. 在二叉搜索树中检索某个变量的值, 实际上等价于在一个经过排序的数组中执行二分查找.

但是二叉搜索树的性能受其结构的影响很大. 在一般情况下, 其插入, 检索和删除操作的时间复杂度均为 $O(\log(n))$, 若树是 不平衡的, 如: 每个节点的左子树大小远大于右子树, 则在遍历每个节点时都无法有效地剪枝, 因而搜索次数增加, 搜索操作消耗的时间也相应增加. 在最坏情况下, 二叉搜索树的性能可能退化到和线性搜索相当的地步, 三种操作的时间复杂度全部退化为 $O(n)$.

AVL 树 (自平衡二叉树) 是为了解决这一问题而设计出的数据结构. 其主要特征 (也是解决二叉树不平衡导致的性能衰减问题的手段) 是, 它维护了另一个不变量: 节点的平衡度.

在 AVL 树中, 节点的平衡度被定义为: 该节点左右子树高度差的绝对值, 而 AVL 树相比二叉搜索树, 所维护的第二个不变量就是, 对树中的任何节点而言, 它的平衡度必须 小于等于 $1$, 该属性也被称为 高度平衡属性 (Height-Balance Property).

对平衡度的维护确保在 AVL 树中, 每个节点的所有子树都基本平衡, 而维护平衡度的方式为: 在对 AVL 树执行每一次插入和删除操作时, 都需要执行 旋转操作 以维护该节点的平衡度.

下面考虑 AVL 树中对节点的旋转操作:

AVL 树的旋转分为 单旋转 和 双旋转, 任何旋转操作都有两个属性: 旋转轴 和 旋转方向. 旋转轴本质就是 旋转之后的子树的节点.

在单旋转中, 旋转轴为 不满足高度平衡属性的最小树 的 根节点对应的子节点 (儿子节点).

在双旋转中, 旋转轴为 不满足高度平衡属性的最小树 的 根节点对应的子节点的子节点 (孙子节点).

左旋

如果观察到某个节点 不满足高度平衡属性 且它的 右子树 高于左子树, 则需要对该节点执行 左旋操作:
1. 将指向该节点的指针改为指向它的右子树.
2. 将该节点右子树改为它的 右子树的左子树:
在完成旋转操作后:
1. 根节点从原节点变为它的右子节点.
2. 原节点从根节点变为根节点的左子节点.
3. 根节点的右子节点的左子节点变为根节点的左子节点的右子节点.
右旋

如果观察到某个节点 不满足高度平衡属性 且它的 左子树高于右子树, 则需要对该节点执行 右旋操作:
1. 将指向该节点的指针改为指向它的左子树.
2. 将该节点左子树改为它的 左子树的右子树:
在完成旋转操作后:
1. 根节点从原节点变为它的左子节点.
2. 原节点从根节点变为根节点的右子节点.
3. 根节点的左子节点的右子节点变为根节点的右子节点的左子节点.
左-右旋

如果观察到某个节点 不满足高度平衡属性 且它的右子节点呈现出 “左重右轻” 的特点, 也就是该节点有一个 Left-heavy Right subtree, 则需要执行左-右旋: 先以右子节点为轴执行一次右旋让右子结点从 “左重右轻” 变成 “左轻右重”, 然后以原节点为轴执行一次左旋.
右-左旋

如果观察到某个节点 不满足高度平衡属性 且它的左子节点呈现出 “右重左轻” 的特点, 也就是该节点有一个 Right-heavy Left subtree, 则需要执行右-左旋: 先以左子节点为轴执行一次左旋让左子结点从 “右重左轻” 变成 “左重右轻”, 然后以原节点为轴执行一次右旋.

需要注意的是, 具有 $n$ 个节点的 AVL 树高度为 $O(\log(n))$.

2.3 二叉堆, 优先序列, 跳跃表和并查集

二叉堆 是一种特殊的完全二叉树 (注意它不是二叉搜索树), 它在 作为完全二叉树 的基础上保持了另一个不变量: 堆序性质:

20220108132915

在构造二叉堆时, 由于二叉堆本身是完全二叉树, 因此可以使用数组实现它而 基本忽略空间浪费, 因为完全二叉树的定义决定它除了最后一层以外, 其余的所有节点度或为 $0$ 或为 $2$, 不构成空间浪费. 二叉堆的构造的时间复杂度最坏情况下为 $O(n\log(n))$.

下面考虑最大堆的插入, 删除和创建:

向堆中插入元素 (本质是新节点的上浮)

在向现存的二叉堆插入元素时, 我们需要 将元素添加到表示堆的数组的末尾, 形式上就是: 将新节点 作为倒数第二层中, 从左往右数第一个度不为 $2$ 的节点的子节点.

在将元素插入后, 我们需要对 整个堆 都重新维护它的 堆序性质:我们需要 自底向上 地依次检查子树的堆序, 直到检查指针上浮到根节点为止.

记堆包含 $n$ 个元素, 则它是一棵高为 $\log(n)$ 的二叉树, 因此插入函数的时间复杂度为 $O(\log(n))$.
从堆中删除元素 (本质是最大堆的最后一个节点的下沉)

我们只能 从最大堆中移除最大值. 在删除根节点后, 堆被拆分成了两棵树. 此时我们需要取 子树的最后一个节点 充当树的根节点. 在此之后, 自顶向下 地递归维护树的 堆序性质, 不难看出删除函数的时间复杂度也为 $O(\log(n))$.
创建最大堆的本质就是 自底向上 地维护某棵二叉树.

优先序列 可以表示为某个最大堆, 我们人为规定 堆中值最大的元素即为优先级最高的元素. 而 向优先序列中插入数据 或 从优先序列中删除数据 的方法与 最大堆中对数据的插入和删除 是一致的.

优先序列 / 最大堆是基于完全二叉树基础上改进而来的数据结构, 而跳跃表则基于链表 (Linked List) 基础上改进而来的, 其本质是可以快速查找的 有序链表.

对于普通的链表而言, 我们只能从表头开始一个个地遍历查找. 而 有序链表 在链表基础上做的改进就是给链表加上了不同层级的索引, 使我们可以沿着不同层级的索引基于要搜索的值和当前索引节点的值, 快速地跳过中间节点从而接近目标节点. 在存储的数据够多的情况下, 还可以继续构造第二层, 第三层, 甚至更高层的节点, 确保 每一层节点数是上一层节点数的一半.

20220108192116

向跳跃表中插入节点的流程有以下几步:

将新节点插入到原链表中.
对这个新节点, 使用 抛硬币 (Coin Flipping) 的方式决定它将被提升为哪一级的索引:连续 “抛硬币” (模拟抛硬币), 直到抛出 $0$ 为止, 在此之前抛出了多少个 $1$ 就将这个节点提升为哪一级的索引.

而从跳跃表中删除节点的流程就相对简单: 从最高级别的索引开始, 依次查找要被删除的目标节点, 并 逐层找到每一层对应的节点, 删除每一层中查找到的目标节点. 若该层没有目标节点则在下一层寻找, 若该层只剩下这一个节点则删除这一整层 (除非这一层已经是链表层了).

注意:

跳跃表的索引是在 每一次插入新数据和删除旧数据时 都被维护的.
在一般情况下, 跳跃表的插入与删除的时间复杂度均为 $O(\log(n))$, 而跳跃表的空间复杂度 (所占空间) 为 $O(N)$ (实际上由于每个元素的期望高度为 $2$, 其实际占用空间应该是2N).

并查集是一种树状的数据结构, 用于处理一系列 不相交集合 的查询与合并问题.

并查集可以用 AVL 树与哈希表实现, 但唯一切合实际的实现方式是构造两个大小相同的数组: 第一个数组存储实际的数据, 而第二个数组存储每个索引对应的父节点, 拥有相同父节点的所有索引被视为属于同一个集合中, 这个集合用父节点表示. 这样可以在执行 查询操作 和 插入操作 时提供最高的效率.

并查集的 API 表 (ADT 定义) 如下:

20220109190712

由于并查集本质是是 树状结构 的, 因此若在结构中出现某棵子树过高的情况时, 就有可能明显增加查询时间从而降低数据结构的性能. 这一问题有两种常见的解决方案:

Path Splitting:

对某并查集的某个元素执行 Path Splitting 时, 我们将无差别地将 从该元素到根节点的路径上每个节点的父节点都替换为它的祖父节点.
Path Halving:

对某并查集的某个元素执行 Path Halving 时, 我们只考虑 从该元素到根节点的路径上 以该元素起算的第 $1, 3, 5, …$ 个节点 (也就是该元素, 该元素的祖父节点, 该元素祖父节点的祖父节点, …), 只将它们的父节点都替换为它们的祖父节点.
Path Compression:

对某并查集的某个元素执行 Path Compression 时, 我们将 从该元素到根节点的路径上经过的每个节点 的父节点都替换为根节点.

3. 算法设计技术

算法的存在意义是用于解决各种现实问题. 一般而言, 我们需要解决的问题可以被划分为下列五类:

决策性问题: 给定输入, 算法需要给出非黑即白的答案.
功能性问题: 给定输入, 算法需要给出一个解, 但解的结构按照具体问题不同而变化.
搜索问题: 给定输入或条件, 算法需要从某个解空间中找出适合的答案.
计数问题: 算法需要统计解空间中有多少个可行解.
优化问题: 算法需要从解空间中找出相对最好的解.

1. 问题分解: 动态规划与分治

分治法的定义已经在前文中描述过, 其典例即为二分查找问题.

动态规划和分治算法类似, 也是通过将原问题拆分为多个子问题来将其解决的, 但区别在于, 分治算法的子问题 彼此无关, 而动态规划拆分的子问题之间彼此又有共同部分. 其核心即为: 通过将子问题之间共通部分的计算结果存储起来, 在下一次需要的时候直接调用而无需重复计算, 由此 “用空间换时间”.

分治和动态规划都可通过 (或者就是通过) 存储已被解决的子问题实现性能优化的. 而二者的最大差异在于, 分治对子问题的划分是 自顶向下 的, 而动规是 自底向上 的.

一般而言, 能够使用动态规划求解的问题具有下列的三个性质:

若问题的最优解包含的子问题的解也是最优的, 也就是说该问题具有 最优子结构.
在问题中, 任何状态下的决策都不会影响之前的状态.
子问题之间相互重叠, 一个子问题在下一阶段的决策中也可能被用到.

2. 解空间搜索: 深度优先, 分支定界, 贪心搜索和启发式搜索

称 需要在问题的解空间内对问题的解进行搜索 的问题为 解空间搜索问题, 例如 SAT 问题: 找出某个形为一系列子句的合取的谓词公式的一个解释.

若问题的解是可以通过某种逻辑或顺序依次生成 (generate) 的, 则也称这样的问题为列举 (enumeration). 一般地, 在解空间中对问题可行解的列举流程/路径会自然地形成树状结构, 每个叶子结点代表一个可行解, 而不同的路径对应不同解的生成过程. 因此, 对问题的求解就可被理解为在这个搜索树/决策树上的搜索问题.

需要注意: 若给定问题总共有 $n$ 个可能解, 则求解这个问题的列举操作的时间复杂度为 $O(n)$, 因为在最坏情况下使用列举法可能需要将它们全部遍历一遍才能最后找到唯一的可行解.

此外, 单纯的列举操作不需要对部分解进行判断 (这是回溯法的优化方向), 也不存在 “无需考虑全部解” 的情况 (这是分支定界的优化方向).

我们可以使用下列的任一种方式优化求解算法的性能:

回溯算法: 从根节点开始按照某种顺序一步步地构造可行解, 若使用某种组合构造出的解不可行则回退到上一步尝试其他方案, 并继续检查生成的新解. 重复这一过程, 最终只要原问题有解, 就必然可以得到一个可行解.
分支定界算法: 在回溯算法的基础上, 维护一个 “当前最优解” 并在作出分支选择 (构造解) 时不断比较, 舍弃那些确定无法得到更优解的决策分支 (也就是剪枝 Pruning).

上述的两种算法都具备相同的特征:

20220110014159

贪心算法 的显著特征是, 它在构造可行解时永远会选择 当前最优 的决策路径. 在一般情况下, 显然这样的策略不能保证算法一定可以找到 全局最优解, 但若我们需要解决的问题具有下列的属性, 则贪心算法是一个很好的选择:

该问题的全局最优解可以表示为多个局部最优解的组合.
或者该问题解的前部分不能被后部分所影响. (We can make a series of choices such that we never need to go back and change the choice later)

REFERENCE:

AVL树的旋转操作详解

最大堆（创建、删除、插入和堆排序）

Lecture 21: Amortized Analysis

Simple union-find techniques

数据结构与算法复习

REVISION