COMP2119A 问题集

与 OI 中间接接触到的各种 DS&A 知识相比，这门课的优势在于比较正统，严谨的理论分析；因此还是有必要记录一下的。这篇笔记将采用 problem-based 的形式，比较随性的收集一些 insights。

  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.

Recursion Problem

关于 Recursion Problem 有大概两种题型：

• 根据 recurrence equation 求 closed-form。
• 同时给出 recurrence equation 与 closed-form，证明它们是对应的。

第一种：比较容易的高中数列题。一般来说有两种做法：

• 根据 recurrence equation，不断将 $f(n)$ 拆成 $f(n-1)$，寻找一系列表达式之间的规律。
• 从 base case $f(1)$ 开始向 $f(n)$ 累加，累加的值可用等差/等比数列求和简化。

Ex1. perm(A, n, n) is a function outputting all permutations of array $A$ with a length of $n$. Define $f(n)$ to be the # swap() function get called. Prove that for $k>1$ we have $2k!\le f(k)\le 2ek!$.

void perm(int* A, int k, int n) {
    if (k == 1)    output(A);
    for (int i = 1; i <= k; ++i) {
        swap(A[i], A[k]);
        perm(A, k - 1, n);
        swap(A[i], A[k]);
    }
}
perm(A, n, n);

Ex2. Let $L(n)$ be the max # of regions formed by $n$ lines in a plane.

第二种：使用 mathematical induction (M.I.) 进行证明。

• Base case：证明在 $n$ 的最小值 $n_0$ 处成立。
• Induction hypothesis：列出归纳假设，即对于 $S(n_0),...,S(k)$ with $k\ge n_0$ 假设成立，则对于 $S(k+1)$ 同样成立。(一般来说直接归纳证明 $S(n_0+1)$ 成立)
• Induction step：用等号连接 $S(k+1)$ 的两种表示，证明 $LHS=RHS$。

Complexity Analysis

$T(n)=\mathrm{\Theta }(f(n))$，意味着：

• $T(n)$ is bounded by $f(n)$: $\mathrm{\exists }{c}_1>0,c_2>0,n_0>0$ s.t. $\mathrm{\forall }n\ge n_0,0\le c_{1}g(n)\le f(n)\le c_{2}g(n)$.
• $T(n)$'s time complexity is $f(n)$.
• $T(n)$'s order of growth is $f(n)$.
• $\underset{n\to \mathrm{\infty }}{lim}T(n)/f(n)=c$, $c$ is a constant.

在比较两算法 execution time $T_1(n),T_2(n)$ 的 time complexity/order of growth 时常采用取极限的方法：

• $\underset{n\to \mathrm{\infty }}{lim}{T}_1(n)/T_2(n)=\mathrm{\infty }$，$T_1$ 在渐进意义下比 $T_2$ 增长的更快。
• $\underset{n\to \mathrm{\infty }}{lim}{T}_1(n)/T_2(n)=c$ for some constant $c$，$T_1$ 与 $T_2$ 的渐进增长速度一致。
• $\underset{n\to \mathrm{\infty }}{lim}{T}_1(n)/T_2(n)=0$，$T_2$ 渐进意义下比 $T_1$ 增长的更快。

除 $\mathrm{\Theta }$ 之外，还有其他四种常见的 notation，每一种 notation 描述的是 a set of functions：

notations	description
Little-Oh $o(f(n))$	$f(n)>T(n)$, not-asymptotically-tight upper bound
Big-Oh $O(f(n))$	$f(n)\ge T(n)$, upper bound
Big-Theta $\mathrm{\Theta }(f(n))$	$f(n)=T(n)$, same order of growth
Big-Omega $\mathrm{\Omega }(f(n))$	$f(n)\le T(n)$, lower bound
Little-Omega $\omega (f(n))$	$f(n)<T(n)$, not-asymptotically-tight lower bound

关于 tractable / computationally hard problems:

• tractable: 存在 worst-case polynomial-time 的算法，i.e., $O(n^c)$ for some constant $c$.
• computationally hard: worst-case complexity is $O(r^n)$ for some $r>1$.

有关时间复杂度分析的几种题型：

• 比较一系列 total execution time 之间的渐进增长速度。
• 分析 recursive function 的时间复杂度。

第一种：相除后取极限进行比较。

• Ex1. 比较 ${\sqrt{\log n}}^{3.14\log n}$ 与 $2n^8+{\log }^{2}n+1$. (Ans $1>2$)
• Ex2. 比较 ${\log }_5(n!)$ 与 ${\log }_7(n^n)$. (Ans $1=2$, ${\log }_5(n!)={\log }_7(n^n)=\mathrm{\Theta }(n\log n)$ )
• Ex3. (midterm)

第二种：使用 Master Theorem 进行分析。关于 Master Theorem 见 貴方が私の Master Theorem か。

Amortized/Average Analysis

以 hash table 为例，讲下如何进行时间复杂度的均摊分析。

若 hash table 的容量为 $m$，储存了 $n$ 个元素，我们定义其 load factor $\alpha =n/m$。

• chaining (open hashing): # of trials $\approx 1+\frac{a}{2}$.
• probing (open addressing): # of trials $\approx \frac{1}{1-\alpha }$.

可以发现，对于 open addressing 实现的哈希表，我们需要控制 $\alpha <\frac{1}{2}$ 来保证常数级别的单次操作复杂度。这就牵扯到了均摊时间复杂度分析的问题：

• 当 # of elements $\le \frac{m}{2}$ 时，单次插入/查找的平均时间复杂度为 $O(1)$。
• 当 # of elements reach $\frac{m}{2}$，重建一个容量为 $2m$ 的哈希表，时间复杂度为 $O(m)$。

在所有插入操作中，只有极小部分会 trigger 哈希表的重建：我们考虑将代价较大的哈希表的重建操作均摊到所有插入操作的代价中。设插入一次的时间代价为 $c$，因为哈希表重建而均摊分配的单次时间代价为 $d$。

为了方便讨论，我们规定从 $n=m/4$ 开始，每次到下一次哈希表重建为止的所有插入操作将承担哈希表重建的代价。以第一次为例：

• 目前 $n=m/4$，再插入 $m/4$ 次就将触发哈希表重建；因此这 $m/4$ 次操作将承担重建的代价。

• 重建哈希表所需的时间代价为 $2mc$.

• 求出被均摊分配的时间代价 $d=\frac{2mc}{m/4}=8c$.

因此单次插入的均摊时间代价为 $c+d=9c$，$O(9c)=O(1)$，仍然是常数级别。

Insight: Building & Egg Problem

$n$ 层楼，$k$ 个鸡蛋：求鸡蛋破碎的 critical height。典中典，但确实是一个好问题。

站在复杂度分析的角度，我们定义 $T(n,k)$ 为 optimal # of probes in the worst case，即最坏情况下最优的时间；“最优”体现在存在一个最优的尝试位置，使得最坏时间尽量小。

base case:

• $k=1$ 时，$T(n,1)=n$.
• $k>1$ 时，$T(0,k)=0,T(1,k)=1$.

int T(int n, int k) {
    if (k == 1 || n == 0 || n == 1)  return n;
    if (t[n][k]) return t[n][k];
    
    int optimal_a = -1, minimal_cost = inf;
    for (int a = 1; a <= n; ++a) {
        int worstcase_cost = max(T(a - 1, k - 1), T(n - a, k)); // broken/not broken
        if (worstcase_cost < minimal_cost) {
            minimal_cost = worstcase_cost;
            optimal_a = a;
        }
    }
    pos[n][k] = optimal_a;
    return t[n][k] = minimal_cost + 1;
}

其中，每个 $T(n,k)$ 所对应的 optimal_a 就是在该情况下鸡蛋尝试的 optimal position。

一般来说，根据不同的情况，我们采取不同的策略：

• $k=1$：别无选择，只能采用 linear search。$\mathrm{\Theta }(n)$。
• $k>1$：由于有不止一个鸡蛋，可以采取 jump search 的策略；而其中最优的是 square-root search，即我们熟悉的分块策略。$\mathrm{\Theta }(\sqrt{n})$。
• $k\ge \log n$：此时鸡蛋的数量支持我们进行 binary search。$\mathrm{\Theta }(\log n)$。

以上的程序也能显示这一点。(issue: 并没有！准备去问一下 Hubert)

Radix Sort and Counting Sort

题目来自 2019 COMP2119 Final Exam Q4D (已解禁)。

Given an array of $n$ elements, where each element is an integer in $\{1,2,3,...,n^k\}$ for some small constant $k\le 2$. The task is to sort the elements with asymptotic running time strictly better than $O(n\log n)$. (You may use extra $O(n)$ space.)

• 条件 $1$: 优于 $O(n\log n)$，考虑 counting sort。
• 条件 $2$: Keys range from $\{1,2,3,...,n^k\}$ 但仅有 $O(n)$ extra space。考虑 counting sort 的进阶 - radix sort。

如何选取 radix？时刻记住，key range $m$ ($\{1,2,3,..,m\}$)，radix $k$ 与 # of digits $d$ 满足关系：$k^d=m$，radix sort 的时间复杂度为 $O(d(k+n))$。

• Key range $m$ 决定了键值数组的大小。
• Radix $k$ 决定了桶数组的大小。
• # of digits $d$ 决定了进行几轮 counting sort。

回到这道题，$k$ 已经保证了是一个 small enough constant，并且我们能使用的额外空间只有 $O(n)$；(桶数组大小) 这提示我们选取 $n$ 作为 radix。

• Key range: $n^k$
• Radix: $n$
• # of digits: ${\log }_n{n}^k=k$

复杂度 $O(k(n+n))=O(n)$ since $k$ is small.

Binary Search Tree

关于 BST 一些容易忘记的小细节。

Successor

BST 中某节点的后继：

• the minimum of $T_R$.
• $T_R$ 不存在：locate an ancestor $a$ that is a left child. the successor is $a$'s parent.

node* successor(node* x) {
    if (x->right != nullptr)
        return minimum(x->right);
    node* fa = x->parent;
    while ((fa != nullptr) && (x == y->right)) {
        x = fa;
        fa = fa->parent;
    }
    return fa;
}

前驱类似：

• the maximum of $T_L$.
• $T_L$ 不存在：locate an ancestor $a$ that is a right child. the successor is $a$'s parent.

Deletion

删除节点 $z$，分三种情况：

• $z$ has no children: delete $z$.
• $z$ has one child: splice out $z$.
• $z$ has two children: replace $z$ by its immediate successor $y$, and splice out $y$ ($y$ is the minimum of $T_R$ for sure, which means it has at most one child)

定义 splice out 操作为将某点的 children 连到其 parent 上。splice out 只适用于删除只有一个孩子的节点。

void delete(root* T, node* z) {
    node* y;    // y is the node to be spliced out
    if ((z->left == NULL) || (z->right == NULL)) {
        y = z;
    } else {
        y = minimum(z->right);
        z->key = y->key;    // replace z by y, then delete y
    }
    // now splice out y, we can guarentee y has at most one child x
    node* x;
    if (y->left != nullptr)
        x = y->left;
    else
        x = y->right;
    
    // if y has no parent, we need to update root
    if (y->parent == nullptr)
        root = x;
    else {
        if (y->parent->left == y)
            y->parent->left = x;
        else
            y->parent->right = x;
    }
}

Tree Height Analysis

Complexity of insertion and deletion: $O(h)$, and the best $h=\log n$.

保证树高为 $\log n$ 的重要条件是插入 keys 的随机性，与保证快速排序效率需要 keys 随机性的原理相同。详情见 Algorithms, Princeton 课程的 quicksort 与 BST 部分。

朴素的删除会影响树的结构。在执行若干次删除操作后树会逐渐左倾。

Self-Balanced Tree: Height Analysis

题目来自 2019 COMP2119 Final Exam Q3C (已解禁)。

Suppose in a binary tree with n nodes, at every node, the difference of heights of the left and the right sub-tree is at most $b$, where $b$ is some parameter that is at least $1$. Prove that the height of the tree is at most $O(b\log n)$.

我们熟悉的 AVL 树就是 $b=1$ 的高度平衡树。

证明来自 MIT algorithm 6.006-spring-2014.

$N(h)$, the minimum number of nodes in a tree with height $h$, root $r$. $n=N(h)$. Without loss of generosity we express $N(h)$ in terms of:

• $N(h-1)$, the minimum number of nodes in the left subtree of $r$
• $N(h-b)$, the minimum number of nodes in the right subtree of $r$

$$\begin{array}{}\text{(1)}& N(h)=1+N(h-1)+N(h-b)\end{array}$$

Since $N(h-1)>N(h-b)$, we can say that $$\begin{array}{}\text{(2)}& N(h)>1+N(h-b)+N(h-b)=1+2N(h-b)>2N(h-b)\end{array}$$ Solve the recurrence $N(h)>2N(h-b)$ and we get $N(h)>2^{h/b}$ $$\begin{array}{}\text{(3)}& N(h)>2^{h/b}⟺\log N(h)>h/b⟺h<b\log N(h)⟺h=O(b\log n)\end{array}$$ Proof completed.

Insight: Convert Linked List to BST

根据 sorted array 建 BST 很简单，这是因为它支持随机访问：$O(n)$ 足矣。那 sorted linked list 又如何呢？

朴素算法：模仿 sorted array 的建立方法，在链表中暴力遍历到根的位置。满足 $T(n)=2T(n/2)+O(n)$，根据 master theorem 推出时间复杂度为 $O(n\log n)$。

$O(n)$ 算法：很巧妙。想象这样一个过程：给一颗完全二叉树，我们对其进行中序遍历，并将得到的值序列逐个写在链表中；以下算法就是上述过程的逆过程。

随着 head 指针在给定链表中迭代，我们还原出以该链表为中序遍历的一颗二叉树。该二叉树的结构又被二分放所保证，其高度一定是接近于 $\log n$ 的 (其结构接近于完全二叉树)。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* sortedListToBST(ListNode* head) {
    if (head == nullptr)
        return nullptr;
    int len = 0;
    ListNode* curr = head;
    while (curr != nullptr) {
        ++len;
        curr = curr->next;
    }
    return buildBST(head, 0, len - 1);
}

TreeNode* buildBST(ListNode* head, int l, int r) {
    if (l > r)
        return nullptr;
    int mid = (l + r) / 2;
    TreeNode left = buildBST(head, l, mid - 1);
    TreeNode root = new TreeNode(head->val);
    root->left = left;
    head = head->next;
    root->right = buildBST(head, mid + 1, r);
    return root;
}

Bubble Sort: Average # of Swapping

一个小证明：冒泡排序平均会调用 swap() 函数多少次呢？

for (int i = n; i >= 2; --i) {
    for (int j = 1; j <= i - 1; ++j) {
        if (a[j] > a[j + 1])
            swap(a[j], a[j + 1]);
    }
}

对于长为 $n$ 的排列 $S$ (我们只关心排列，因为冒泡排序是 comparison-based sorting，基于元素间的大小关系而与具体数值无关)，答案应当是 $\frac{1}{n!}\sum _{I\in S}\mathrm{inv}(I)$，其中 $\mathrm{inv}(I)$ 是排列 $I$ 中的逆序对个数。

这个式子很难算。换个角度，考虑每一对逆序对对答案作出的贡献：选取两个数 $a,b(a<b)$ 作为逆序对，再选取两个位置 $i,j(i<j)$，将 $b$ 填入位置 $i$，$a$ 填入位置 $j$ ，这样的逆序对共有 $(C_n^2{)}^2$ 个。

每一个这样的逆序对会做出多少贡献？考虑一个逆序对 $(b,a)$，它们已经占据了 $n$ 个位置中的两个，那么这样的一个逆序对将会在 $(n-2)!$ 个排列中出现；也就是，它们对答案的贡献是 $(n-2)!$。

那么长为 $n$ 的排列平均拥有的逆序对为 $\frac{1}{n!}(C_n^2{)}^2(n-2)!=\frac{n(n-1)}{4}$。这就意味着冒泡排序将对长为 $n$ 的数组 (假设元素 distinct) 调用平均 $\frac{n(n-1)}{4}$ 次 swap() 函数。

Heap: Linear Heap Building

众所周知，堆有两种建法：

• 向空堆中插入 $n$ 次，复杂度 $O(n\log n)$
• heapify 方法，复杂度 $O(n)$

这里主要讲下线性建堆方法的复杂度证明 (以大根堆为例)。

void sink(int x) {
    while (x * 2 <= n) {
        int child = x * 2;
        if (child + 1 <= n && a[child + 1] >= a[child])
            ++child;          // right child > left child
        if (a[child] <= a[x])
            break;            // heap property is not violated
        swap(a[child], a[x]);
        x = child;
    }
}

void heapify() {
    for (int i = n; i >= 1; --i)    sink(i);
}

若堆高为 $h$，则高度为 $i$ 的节点最多需要被 swap $h-i$ 次。由于堆是二叉树，高度为 $i$ 的节点最多有 $2^i$ 个。

因此总 swap 次数为： $$\begin{array}{}\text{(4)}& T(n)=\sum _{i=1}^h{2}^i(h-i)=\sum _{i=1}^{h}i{2}^{h-i}=2^h\sum _{i=1}^h\frac{i}{2^i}\end{array}$$ 令 $x=\frac{1}{2}$，则 $L=\sum _i\frac{i}{2^i}$。我们有： $$\begin{array}{}\text{(5)}& \begin{array}{rl}\mathrm{①}& :L=x+2x^2+3x^3+...\\ \mathrm{②}& :xL=0+x^2+2x^3+...\\ \mathrm{①}-\mathrm{②}& :(1-x)L=x+x^2+x^3+...=x(1+x+x^2+...)=\frac{x}{1-x}\end{array}\end{array}$$ 解得 $L=x/(1-x{)}^2=2$。所以 $O(T(n))=O(2^{h}L)=O(2^h)=O(n)$.

Randomized Quicksort Analysis

众所周知，快排在序列 already sorted 或 reverse-sorted 时有最坏时间复杂度 $O(n^2)$，随机化使得这种情况出现的概率可以忽略不计。但是随机化快排的时间复杂度又怎么分析呢？

当然是取平均！由于随机化，partition 产生的两个子序列的长度可能是 $(0,n-1)$, $(1,n-2)$ ... $(n-1,0)$ 共 $n$ 种情况，且概率相等，均为 $\frac{1}{n}$。那么对长度为 $n$ 的序列排序所需的时间 $T(n)$ 为： $$\begin{array}{}\text{(6)}& T(n)=\frac{2}{n}\sum _{i=0}^{n-1}T(i)+cn\end{array}$$ 接下来我们要证明的是 $T(n)\le An\log n$，其中 $A$ 是某个常数。采用 induction method:

• base case
  • $T(0)=0,T(1)=1$
  • $T(2)=1+2c\le A\log 2$ (提示我们 $A$ 应该是一个 large enough constant)
• induction hypothesis: assume for $2\le i\le n-1$, $T(i)\le Ai\log i$

进行 induction： $$\begin{array}{}\text{(7)}& \begin{array}{rl}T(n)& =\frac{2}{n}\sum _{i=0}^{n-1}T(i)+cn\\ & \le \frac{2}{n}\cdot \sum _{i=0}^{n-1}Ai\log i+cn\\ & \le \frac{2}{n}A\frac{n(n-1)}{2}\log n+cn\\ & =An\log n-A\log n+cn\end{array}\end{array}$$ 可以发现还是没法证明 $T(n)\le An\log n$。重点在于常数 $A$ 的选取上。

我们尝试进行更加细致的放缩。由于 $$\begin{array}{}\text{(8)}& i\log i\le \{\begin{array}{c}\begin{array}{rl}i\log \frac{n}{2},i& =2,...,\frac{n}{2}\\ i\log n,i& =\frac{n}{2}+1,...,n\end{array}\end{array}\end{array}$$ 我们有 $$\begin{array}{}\text{(9)}& T(i)\le \{\begin{array}{c}\begin{array}{rl}A(i\log n-i),i& =2,...,\frac{n}{2}\\ Ai\log n,i& =\frac{n}{2}+1,...,n\end{array}\end{array}\end{array}$$ 通过对 $i$ 分类讨论，引入了新的一项 $-Ai$。我们用这个更加准确的式子进行放缩。 $$\begin{array}{}\text{(10)}& \begin{array}{rl}T(n)& =\frac{2}{n}\sum _{i=0}^{n-1}T(i)+cn\\ & \le \frac{2}{n}A\cdot (\sum _{i=0}^{n-1}i\log i-\sum _{i=0}^{n-1}i)+cn\\ & \le An\log n-A\log n-\frac{2}{n}A\cdot \frac{1}{2}(\frac{n}{2})(\frac{n}{2}+1)+cn\\ & =An\log n-A\log n-\frac{A}{2}(\frac{n}{2}+1)+cn\end{array}\end{array}$$ 为证明 $T(n)\le An\log n$，我们选取常数 $A$ 使得其能抵消 $cn$ 带来的影响。令 $cn\le \frac{A}{2}(\frac{n}{2}+1)$，发现取 $A=4c$ 能够满足要求。因此 $T(n)$ 的上界得证：$T(n)\le An\log n=4cn\log n=O(n\log n)$

Huffman Tree: Key lemma

Key lemma of Huffman tree.

Given a tree $T$, we can find a tree $T^{\prime }$, with the two minimum cost leaves as siblings, and $C(T^{\prime })\le C(T)$.

$C(T)$ 是 $T$ 的 total weighted path length (WPL)。给出一颗树 $T$，不断对其应用 key lemma，其总 WPL 会持续减小。最小 WPL 对应的是 optimal prefix tree， 即 Huffman tree。

Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Course info. Code: COMP2119, Lecturer: Hubert T.H. Chan.