算法数据结构和效率

有关算法效率分析的笔记，包括Big-Oh表示法、Master定理和部分算法与数据结构的算法分析。

---

介绍

原博客：点击跳转

本笔记着重于介绍使用理论知识分析算法和数据结构的效率，此外还会介绍一些算法和数据结构的抽象功能，以及对这些功能实现的效率分析。

本笔记主要分为下面五个部分：

• 一. 算法效率的评估
• 二. Big-Oh表示法和其家族
• 三. Master定理
• 四. 数据结构
• 五. 算法

一. 算法效率的评估

如何评估一个算法的效率？最直接的方式就是在程序输入后何时才能获得输出值。其中一种比较直观的方式是根据 程序的运行时间 来评估测量算法效率。

在同一个程序中，程序的运行时间往往会随着输入大小(input size)而增加。即使固定输入大小，实际运行时间通常也会有所不同，这取决于输入的详细信息。例如在最短路算法中，即使是相同数量的点和边，不同的连接方法也会导致运行时间不同 (关于SPFA，它死了) 。

由于你的时间非常值钱，因此我们需要一些方法来对算法的效率进行客观地评估，这些方法主要可以分类为两种：实验统计和理论分析。

---

方法一：Experiment 实验统计

实验统计是使用观察和控制变量的方法来对一种现象进行系统的测试和验证。

具体步骤如下:

• 写一个程序实施该算法
• 使用不同的输入大小和输入信息运行程序
• 记录实际运行时间
• 绘制并使用统计学分析（如回归分析）

在固定输入大小、不同输入信息中，统计中获得最佳运行时间、最差运行时间、平均运行时间，我们通常会关注最差的情况，主要原因是平均时间往往很难以去分析 (例如为什么在判断一个公司工资待遇往往不是使用平均值，更多的是最低工资)。

缺点 & 局限性

• 必须用程序实现该算法，可能会很耗时。
• 需要提供大量输入集或者选择合适的输入集来找到最差的情况，不然会导致结果的偏差。
• 效率的评估受到硬件/软件/语言环境的影响。

---

方法二：Theory 理论分析

理论分析是基于已有的知识和数据，运用逻辑和数学的方法来对一种现象进行解释和预测。

跟实验统计一样，我通常指关注最差的情况。

特点

• 具有一定的抽象性。
• 能够独立于硬件/软件/语言环境来评估算法的效率。
• 能够考虑所有可能的输入。

缺点 & 局限性

• 实施过程可能会比较困难，需要一定的知识基础。
• 在现实实施的时候可能有一些特殊情况导致与理论结果相差较大，使用理论解释这种情况可能会比较困难。

评估标准

在实验统计中，我们往往使用 程序的运行时间 来作为评估的标准，但是在理论知识中我们无法使用这个来作为评估标准。因为程序的运行时间往往受到环境的影响，因此理论难以测量出运行时间，所以我们使用另一种方法来作为理论分析中使用的评估标准：原始运算数量。

原始运算的定义

原始运算(primitive operations)是算法执行的基本运算。

在真实的计算机中，实际的运算应该是逻辑门的操作，但是很明显这个是很琐碎的，与算法的运算相差太远。因此我们需要去定义哪些运算属于原始运算以便于记数。一般来说，我们会将汇编代码、算数运算视作一个原始运算。

注意，原始运算的定义不是固定的，下面有更具体的说明。在这个笔记中，我们将这些操作视作一个原始运算：

描述	伪代码样例
变量赋值	a ← 0
数组索引	a[10]
变量比较	a == 10
算数运算	a + 1
函数调用	function()
函数返回	return 0

注意：

• 在本笔记中我们忽视了汇编中有关jump的指令，即本笔记中默认jump指令原始运算为0。
• 数组索引需要用到袁术运算是因为它需要在内存中进行索引。
• 函数调用属于原始运算是因为它需要在内存中进行索引。
• 在CPU中，浮点运算(如除法)实际上是一个非常复杂的算法。但在汇编语言中，它只是一个指令，因此我们也将其视作一个原始运算。

对于其他的运算，都可以拆分为这些原始运算：

描述	分析	操作数	伪代码样例
for循环，循环次数为$n$	要经历1次初始赋值；n次判断；n次叠加，每次叠加是两个原始运算(加法和赋值)	$1+n+2n = 3n+1$	for i ← 1 to n do
for循环，循环次数为$(n-1)$	要经历1次初始赋值；(n-1)次判断，每次判断是两个原始运算(减法和比较)；(n-1)次叠加，每次叠加是两个原始运算(加法和赋值)	$1+2(n-1)+2(n-1) = 4n-3$	for i ← 1 to (n-1) do
while循环，循环次数为$n$	每次循环只需要判断即可	$n$	while i > n
while循环，循环次数为$(n-1)$	每次循环都需要进行判断和减法	$2(n-1)$	while i > (n-1)
if then判断，then内部原始运算数为$k$	一个判断。由于我们是统计最差次数，因此我们需要将if里原始运算进行累加(默认触发)	$1 + k$	if ... then ...

:::details 一个计算原始运算数的例子: arrayMax(A, n)

一个返回数组最大值arrayMax(A, n)的伪代码：

Algorithm arrayMax(A, n)    # A为数组，n为数组大小，即数组从0开始，(n-1)结束。
  currentMax ← A[0]         # 原始运算数为2，分别是数组索引和赋值
  for i ← 1 to (n - 1) do   # (n-1)次数的循环运算，原始运算数为(4n-3)
    if A[i] > currentMax    # 每次循环原始运算数为2，分别是数组索引和判断，共(n-1)次循环，原始运算数为2(n-1)
      currentMax ← A[i]     # then内部运算。每次循环原始运算数为2，分别是数组索引和赋值，原始运算数为2(n-1)
  return currentMax         # 原始运算为1，函数返回

综上所述，这个算法的原始运算总数为 $2 + (4n - 3) + 2(n - 1) + 2(n - 1) + 1 = 8n - 4$

:::

原始运算的个数并不是固定的，例如在计算操作 $c \leftarrow A[i]$ 中，你也可以认为是$4$个原始运算：

• 获取$A$数组的指针储存在寄存器中。
• 获取$i$储存在寄存器中。
• 计算$A + i$作为$A[i]$的指针储存在寄存器中。
• 复制变量$c$的数值写在$A + i$指针的内存中。

当然在这个笔记中，你也可以认为只有$2$个原始运算：

• 根据$i$索引获取$A[i]$数组位置 (数组索引)。
• 将变量$c$的数值赋值给$A[i]$ (变量赋值)。

但是无论是$4$还是$2$，这个操作永远不可能会是$2n$，即它的增长率永远不可能会超过常数级(增长率的定义在下面)。

原始运算的个数只与算法的效率有关，与正确性无关。

使用原始运算估算运行时间

增长率(Growth Rate)指的是函数的因变量随着自变量的增加而增长的速率。

对于算法来说，假设它的最差情况的运行时间为$T(n)$，那么$T(n)$的增长率是该算法的固有属性，是不受硬件/软件环境影响的。

我们可以使用原始运算来估算运行时间，假设：

• 原始运算的个数为$P(n)$。
• 最快的原始运算所需要的时间为$a$，是一个常数。
• 最慢的原始运算所需要的时间为$b$，是一个常数。

可以得出：$$aP(n) \leq T(n) \leq bP(n)$$

由于a和b都是常数，那么我们认为[T(n)]和[P(n)]具有相同的增长率。很明显$T(n)$和$P(n)$的导数肯定是不同的，因此增长率并不等同于导数。

但是增长率有一种只可意会不可言传的感觉：这种增长率具体形式是什么样的？如何定义哪两个函数具有相同的增长率？那么就需要用到我们的Big-Oh表示法了。

二. Big-Oh表示法和其家族

基本知识

我们需要一种函数分类(Classification of Functions)来通过缩放的行为将函数分组在一起，同一组的函数具有这样的相似性：

• 删除不必要的细节。
• 相对快速、简单。
• 处理运行时可能会发生的“奇怪的”函数(例如分段函数)。
• 在数学上拥有明确的定义。

其中一种最佳的方法是使用Big-Oh表示法和其家族(Big-Oh notation and family)：

• $O$: Big-Oh
• $\Omega$: Big-Omega
• $\Theta$: Big-Theta
• $o$: little-oh
• $\omega$: little-omega

本笔记只集中于前四个的定义和Big-Oh的相关理论。

---

Big-Oh：O(n)

定义

假设有两个正函数$f(n)$和$g(n)$，如果我们称 $f(n) \ is \ O(g(n))$ ，当且仅当
$$\exists c > 0, \exists n_0 > 0, \forall n \geq n_0 : |f(n)| \leq c \ g(n)$$

注意:

• 量词顺序是 $\exists \ \exists \ \forall$
• $c$ 和 $n_0$必须是常数，不能随着$n$变化。不然这是没有意义的。
• 注意符号$>,\geq,\leq$的区分。相比之下是比较严格的(例如，$n_0$ 不能等于 $0$, $n$ 可以等于 $n_0$)。

此外，Big-Oh可以会被定义为：
$$\limsup_{n\to \infty} \frac{f(n)}{g(n)} < \infty $$

Big-Oh只规定了$f(n)$的增长率的上限(upper bound on the growth rate of the function)。

特点

• Big-Oh不关注算法或者是“算法最差的运行时间”，而是只关注于函数。也就是说它并不是对算法进行分类，而是对函数进行分类。
• 一般$f(n)$表示运行时间，$n$表示输入的个数，所以Big-Oh中描述的函数一般为 $f: \mathbb{N^+} \to \mathbb{R^+}$，$g(n)$也类似。
• Big-Oh只规定了$f(n)$的增长率的上限，也就是说，当$n$足够大时，$f(n)$的增长速率不大于$g(n)$。
• Big-Oh中$g(n)$的选择并不是一定要选择“最佳”或者“最有用的”函数。例如，对于$f(n) = 1$可以是$O(1)$，但也可以是$O(n)$。因此$g(n)$的增长率越小越能反应出$f(x)$的增长率。

性质

Big-Oh作为一个二元关系(binary relation)，拥有以下性质：

• Big-Oh具有自反性(Reflexive, e.g. $x R x$)，即 $f(n)$ 是 $O(f(n))$。
• Big-Oh不具有对称性(Symmetric, e.g. $x R y \iff y R x$)，例如 $f(n) = 1$ 是 $O(n)$，但是 $f(n) = n$ 不是 $O(1)$。
• Big-Oh具有传递性(Transitive, e.g. $x R y \land y R z \to xRz$)。即如果 $\forall n \geq n_1, f(n) \leq c_1g(n)$，且$\forall n \geq n_2, g(n) \leq c_2h(n)$，那么总有 $\forall n \geq n_3, f(n) \leq c_1c_2h(n), n_3=\max(n_1,n_2)$。

综上所述，Big-Oh具有自反性和传递性，因此Big-Oh更像是$\subset, \in, \leq$,而不是$=$，因此有一种表示方法是将Big-Oh视作集合，使用$n \in O(n)$。此时也有会 $O(lower\ order) \subset O(heigher\ order)$。

此外，也有一种说法是使用$f(n) = O(n)$，其中等于号是一种单向的等于。但是本笔记中更偏向于使用“是”或者“is”来表示。

推论 & 方法

• 推论1：存在三个函数$f(n)$, $g(n)$, $p(n)$和正数$k, b\in \mathbb{N^+}$，如果$f(n)$是$O(g(n))$，且$f(n)=k\ p(n) + b$，那么有$p(n)$是$O(g(n))$。

:::details 证明推论1

假设有$c_0 > 0, n_0 > 0$，对于$n_1 \geq n_0$，有：

$f(n_1) \leq c_0 \ g(n_1)$，那么有：

$k\ p(n_1) + b \leq c_0 \ g(n_1)$，整理得：

$p(n_1) \leq \frac{c_0}{k}g(n_1) - \frac{b}{k}$

当n足够大时候，假设此时$n_1 \geq n_2$，有 $cg(n_1) \geq 2b$

从而有 $p(n_1) \leq \frac{c_0}{2k}g(n_1)$

设 $c_1=\frac{c}{2k}>0$，我们得到：

$p(n_1) \leq c_1\ g(n_1)$，即

存在 $c_1$，$n_2$使得 $\forall n > n_2, p(n) \leq c_1\ g(n)$

因此$p(n)$是$O(g(n))$。

:::

• 推论2 （乘法）：如果$f_1(n)$ 是 $O(g_1(n))$, $f_2(n)$ 是 $O(g_2(n))$，那么 $f_1(n)f_2(n)$ 是 $O(g_1(n)g_2(n))$。

:::details 证明推论2

$∵ f_1(n)$ 是 $O(g_1(n))$

$∴ f_1(n) \leq c_1\ g_1(n)\ \text{ for all } \ n \geq n_1$

$∵ f_2(n)$ 是 $O(g_2(n))$

$∴ f_2(n) \leq c_2\ g_2(n)\ \text{ for all } \ n \geq n_2$

$∵ f_1(n), f_2(n), g_1(n), g_2(n) \geq 0$

那么有 $n_0 = \max(n_1, n_2)$
$f_1(n)f_2(n) \leq c_1c_2g_1(n)g_2(n) \ \text{ for all } \ n \geq n_0$

因此$f_1(n)f_2(n)$ 是 $O(g_1(n)g_2(n))$

:::

• 推论3 （加法）：如果 $f(n) = 1 + h(n)$，且当$n \to \infty$ 时 $h(n) \to 0$，那么 $f(n)$ 是 $O(1)$。

:::details 证明推论3

$∵$ 当$n \to \infty$ 时 $h(n) \to 0$
$∴$ $\exists n_0 > 0,\ \forall n \geq n_0, h(n) \leq 1$
$∴$ $\exists n_0 > 0,\ \forall n \geq n_0, f(n) \leq 2$
$∴$ $f(n)$ 是 $O(1)$ 取 $c = 2, n_0 = n_1$ 且 $h(n_1) <= 1$

:::

一些常用的 $h(n)$:

• $n^2/2^n$
• $n^{2000}/2^{\frac{n}{100}}$
• $(log(n))^{100} / n^{0.1}$

综合推论2和3，可知如果 $f(n) = g(n)(1 + h(n))$，且当$n \to \infty$ 时 $h(n) \to 0$，那么 $f(n)$ 是 $O(g(n))$。

因此我们总结了获取Big-Oh的通用方法 —— 删除规则(Drop Rules)：

• 删除低阶(lower-order)项 (根据推论2, 3)。阶排名可以看下面常用表示表。
• 删除常数(constant)项系数 (根据推论1,总能找到 $k$ 使得系数变成 $1$)。

例子

:::details 证明arrayMax(A, n)是 $O(n)$ 的例子 (定义)

由上述计算原始运算数的例子可知，arrayMax(A, n)的原始运算记数为 $f(n) = 8n - 4$

设$g(n) = n$，因此需要求证 $\exists c > 0, \exists n_0 > 0, \forall n \geq n_0, f(n) \leq c \ g(n)$，整理可得：

$$
\begin{cases}
n \leq \frac{4}{c - 8} & c > 8 \
n \geq \frac{4}{c - 8} & c < 8 \
-4 \leq 0 & c = 8
\end{cases}
$$

由于我们规定是 $\forall n \geq n_0$，因此我们只能取 $n \geq 8$。

当我们取 $n = 8$时，很明显任意$n_0 > 0$都可以证明成立。此时我们可以取 $n_0 = 1$。

当我们取 $n > 8$时，很明显任意$n_0 > \frac{4}{c - 8}$都可以证明成立。此时我们可以取 $n_0 = \frac{4}{c - 8}$。

实际上，上述情况只需要求出一组$(c,n_0)$即可，因此我们可以直接取$c = 8, n_0 = 1$。不过这里给出了一种选取$(c,n_0)$的具体方法。

因此arrayMax(A, n)的时间复杂度是 $O(n)$。

:::

:::details 对于分段函数Big-Oh的证明 (定义)

如何计算下面函数的Big-Oh:
$$
f(n) =
\begin{cases}
n & \text{if } n \text{ is even} \
1 & \text{if } n \text{ is odd}
\end{cases}
$$

因为Big-Oh是规定的函数增长率的上限，因此我们应该取增长率最大的函数，即$f(n) = n$，此时当$c = 1, n_0 = 1$可以证明出$f(n)$是$O(n)$，而无法证明出$f(n)$是$O(1)$。

:::

:::details 求 $f_(n) = n^2 + n$ 的Big-Oh (定理2, 3)

$f(n) = n^2 + n = n^2(1 + \frac{1}{n})$

因为自反性，$n^2$ 是 $O(n^2)$。

因为当$n \to \infty$ 时 $\frac{1}{n} \to 0$，根据推理3可知 $1 + \frac{1}{n}$ 是 $O(1)$。

因此根据推理2，$f(n)$ 是 $O(n^2 * 1) = O(n^2)$

:::

:::details 求 $f_(n) = 5n^4 + 3n^3$ 的Big-Oh (删除规则)

• 删除低阶$3^n$，因此$f(n)$ 是 $O(5n^4)$
• 删除常数$5$，因此$f(n)$ 是 $O(n^4)$

:::

Big-Oh公约

遵循这个公约可以更好地去分析算法以及给出最大的信息。

• 使用最小且正确的增长率函数表示Big-Oh。例如说 $2n$ 是 $O(n)$ 而不是 $O(n^2)$，尽管后者也是正确的。
• 使用最简的函数表示Big-Oh。例如说 $2n$ 是 $O(n)$ 而不是 $O(2n)$。

其他

对于 $n^{O(1)}$来说，相当于是 ${ n^f(n)\ |\ f(n) \text{ is } O(1)}$。
也就是说 ${n^1, n^2, n^3, …} \subset n^{O(1)}$，${n^\frac{1}{2}, n^\frac{1}{3}, n^\frac{1}{4}… } \subset n^{O(1)}$

$n^{O(1)}$ is any function that is no worse than (Big-Oh of) some power law.
$n^{O(1)}$表示任何不超过指数级的函数。

---

Big-Omega：Ω(n)

定义

假设有两个正函数$f(n)$和$g(n)$，如果我们称 $f(n) \ is \ \Omega (g(n))$ ，当且仅当
$$\exists c > 0, \exists n_0 > 0, \forall n \geq n_0 : f(n) \geq c \ g(n)$$

注意：

• 量词顺序是 $\exists \ \exists \ \forall$。
• 与Big-Oh不同，最后的符号是 $\geq$ 而不是 $\leq$。

此外，Big-Omega可以会被定义为：
$$\liminf_{n\to \infty} \frac{f(n)}{g(n)} > 0 $$

特点

• Big-Omega规定了$f(n)$的增长率的下限，也就是说，当$n$足够大时，$f(n)$的增长速率不小于$g(n)$。
• Big-Omega中$g(n)$的选择并不是一定要选择“最佳”或者“最有用的”函数。例如，对于$f(n) = n^3 - n$ 可以是 $\Omega(n^3)$，但也可以是 $\Omega(n^2)$。因此$g(n)$的增长率越大越能说明$f(n)$的增长率。
• 一般可以用来描述算法的最佳情况。

性质

类似于Big-Oh，Big-Omega作为一个二元关系拥有下面的性质：

• Big-Omega具有自反性(Reflexive, e.g. $x R x$)。
• Big-Omega不具有对称性(Symmetric, e.g. $x R y \iff y R x$)。
• Big-Omega具有传递性(Transitive, e.g. $x R y \land y R z \to xRz$)。

Big-Omega更像是 $\geq$。

推论 & 方法

• 推论1：$f(n) \text{ is } O(g(n))\iff g(n) \text{ is } \Omega(f(n))$
• 推论2 （乘法）：如果$f_1(n)$ 是 $\Omega(g_1(n))$, $f_2(n)$ 是 $\Omega(g_2(n))$，那么 $f_1(n)f_2(n)$ 是 $\Omega(g_1(n)g_2(n))$。

删除规则依然适用于Big-Omega，但是注意删除法则跟Big-Oh一样是删除低阶函数而不是删除高阶函数。

例如 $f(n) = n^3 - n$中，应该删除的是$n$。找到$n^3$后我们就可以找比$n^3$阶级低的函数来代替。

---

Big-Theta：θ(n)

定义

假设有两个正函数$f(n)$和$g(n)$，如果我们称 $f(n) \ is \ \Theta (g(n))$ ，当且仅当

$$\exists c’ > 0, \exists c’’>0, \exists n_0 > 0, \forall n \geq n_0 : c’\ g(n) \leq f(n) \leq c’’ \ g(n)$$

此外，Big-Theta可以被定义为：

$$f(n) \text{ is } \Theta(g(n)) \iff f(n) \text{ is } O(g(n)) \text{ and } f(n) \text{ is } \Omega(g(n))$$
$$f(n) \text{ is } \Theta(g(n)) \iff f(n) \text{ is } O(g(n)) \text{ and } g(n) \text{ is } O(f(n))$$

性质

Big-Theta作为一个二元关系拥有下面的性质：

• Big-Theta具有自反性(Reflexive, e.g. $x R x$)。
• Big-Theta具有对称性(Symmetric, e.g. $x R y \iff y R x$)：如果 $f(n)$ 是 $\Theta(g(n))$，那么 $g(n)$ 是 $\Theta(f(n))$。可以根据Big-Theta的第二定义和Big-Omega的推论1得出。
• Big-Theta具有传递性(Transitive, e.g. $x R y \land y R z \to xRz$)。

Big-Theta更像是 $\approx$。

---

little-oh：o(n)

定义

假设有两个正函数$f(n)$和$g(n)$，如果我们称 $f(n) \ is \ o(g(n))$ ，当且仅当
$$\forall c > 0, \exists n_0 > 0, \forall n \geq n_0 : |f(n)| < c \ g(n)$$

注意:

• 量词顺序是 $\forall \ \exists \ \forall$。
• 因为是对于全部的 $c$ 存在 $n_0$，因此 $n_0$ 的数值可以依赖于 $c$。
• 与Big-Oh不同，最后的符号是 $<$ 而不是 $\leq$。

little-oh也可以被定义为：
$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$

性质

little-oh作为一个二元关系(binary relation)，拥有以下性质：

• little-oh不具有自反性(Reflexive, e.g. $x R x$)。即$f(n) = n$ 不是 $o(n)$。
• little-oh不具有对称性(Symmetric, e.g. $x R y \iff y R x$)。
• little-oh具有传递性(Transitive, e.g. $x R y \land y R z \to xRz$)。

little-oh 更像是严格的 $<$。

特点

• 与Big-Oh类似，little-Oh定义是函数的严格无法到达的上限。
• little-oh的意思是，当$n$足够大时，$f(n)$的增长速率小于$g(n)$。
• little-oh中 $g(n)$ 阶级越小，越能说明 $f(n)$ 的增长率。

推论 & 方法

• 推论1：如果$f(n)$ 是 $o(g(n))$，那么 $f(n)$ 一定是 $O(g(n))$
  正如 $<\ \to\ \leq$ 一样，很明显 $O(g(n)) \subset o(g(n))$。
• 推论2 （乘法1）：如果$f_1(n)$ 是 $o(g_1(n))$, $f_2(n)$ 是 $o(g_2(n))$，那么 $f_1(n)f_2(n)$ 是 $o(g_1(n)g_2(n))$。
• 推论3 （乘法2）：如果$f_1(n)$ 是 $o(g_1(n))$, $f_2(n)$ 是 $O(g_2(n))$，那么 $f_1(n)f_2(n)$ 是 $o(g_1(n)g_2(n))$。

与Big-Oh类似，little-Oh也可以使用删除规则。与Big-Oh不同的是，little-Oh不能选择事实删除规则后的函数，而只能选择比该函数阶级更大的函数。

例子

:::details 证明 $f(n) = n ^ 2 + n$ 是 $o(n^3)$

要证明$f(n) = n ^ 2 + n$ 是 $O(n^3)$，则需要证明 $\forall c > 0, \exists n_0 > 0, \forall n \geq n_0 : f(n) < c \ g(n)$。

代入和整理可得 $\forall c > 0, \exists n_0 > 0, \forall n \geq n_0 : cn^2-n-1 > 0$。

由公式可得，若 $cn^2-n-1 = 0$，且$n_r > 0$，可解得 $n_r = \frac{1 + \sqrt{4c + 1}}{2c} > 0$。

且当 $n > n_r$ 时，$cn^2 - n - 1 > 0$ 恒成立，那么可以取 $n_0 = n_r + 1 = \frac{1 + \sqrt{4c + 1}}{2c} + 1$，使得 $\forall n \geq n_0 : f(n) < c \ g(n)$ 恒成立。

因此，$f(n) = n ^ 2 + n$ 是 $O(n^3)$，此时对于所有的 $c$ 取 $n_0 = \frac{1 + \sqrt{4c + 1}}{2c} + 1$。

:::

关于Big-Oh和little-oh的定义上的思考：

如果将Big-Oh的定义改为：$\exists c > 0, \exists n_0 > 0, \forall n \geq n_0 : |f(n)| < c \ g(n)$，称为 $O_<$，而原定义称为 $O_{\leq}$，
那么实际上，对于 $g(n) > 0$， $f(n)$ 是 $O_<(g(n)) \iff f(n)$ 是 $O_{\leq}(g(n))$。
唯一的区别是对于 $f(n) = 0, g(n) = 0$ 来说 $0$ 是 $O_{\leq}(0)$ 而不是 $O_<(0)$。
而我们想要定义Big-Oh的渐进符号为 $\leq$，就得要求 $0$ 是 $O(0)$，因此使用 $\leq$ 而不是 $<$。

同理，对于little-oh如果定义改为：$\forall c > 0, \exists n_0 > 0, \forall n \geq n_0 : |f(n)| \leq c \ g(n)$，称为 $o_{\leq}$，而原定义称为 $o_{<}$。
此时 $o_{<}$ 与 $o_{\leq}$ 定义的唯一区别也是当 $f(n) = 0, g(n) = 0$ 的时候，此时 $0$ 是 $o_{\leq}(0)$ 而不是 $o_{<}(0)$。
而我们想要定义little-oh的渐进符号是 $<$，就得要求 $0$ 不是 $o(0)$，那么使用的是 $<$ 而不是 $\leq$。

实际上，对于Big-Oh和little-oh最主要的区别是 $\exists c$ 和 $\forall c$。

---

常用表示表

根据阶级(order)从小到大排名。

表示	中文名	英文名	数量级
$O(n^c), c < 0$ $or$ $O(\frac{k}{n})$	负数幂级	negative power	$\infty$,不存在
$O(1)$	常数级	constant	$\infty$
$O(\log{\log{n}})$	双对数级	double logarithmic	$2^{2^{10^6}}$
$O(\log{n})$	对数级	logarithmic	$10^{301030}$
$O((\log{n})^c), c > 1$	多重对数级	polylogarithmic	$2^{10^{\frac{6}{c}}}$
$O(n^c), 0 < c < 1$ $or$ $O(\sqrt[c]{n})$	分数幂级	fractional power	$10^{6c}$
$O(n)$	线性级	linear	$10^6$
$O(n\log{n}) = O(\log{n!})$	对数线性/拟线性级	loglinear, n-log-n	$10^5$
$O(n^2)$	二次级	quadratic	$10^3$
$O(n^c), c > 1$	多项式/代数级	polynomial, algebraic	$\sqrt[c]{10^6}$
$O(c^n)$	指数级	exponential	$6\log_{c}{10}$
$O(n!)$	阶乘级	factorial	$9$

---

Big-Oh家族使用样例

• 用于表示一个范围：算法 X 最坏的情况时间复杂度是 $o(n^4)$ 和 $\Omega(n^3)$，但是实际表现并不确定。
• 用于确定一个增长率：算法 X 最佳的情况时间复杂度是 $\Theta(n^2)$。
• 用来表示一个平均值：算法 X 平均情况时间复杂度是 $O(n^3)$。

---

使用Big-Oh家族分析算法效率注意点

Big-Oh家族之所以实用是因为它隐藏了低阶项和常数。它们主要分析当 $n$ 足够大时渐进的范围,也可以说是 $n$ 的增长率。

但是在 $n$ 比较小时这些被隐藏掉的项可能会成为非常重要的参考指标。也就是说不能完全根据Big-Oh家族和阶级大小来完全判断一个算法的实际工作时的效率。

例如：

• $10000n$ 是 $O(n)$，同时 $2^n$ 是 $O(2^n)$，当时当 $n$ 比较小时，例如 $n = 6$ 时，前者需要进行的计算数是 $60000$，而后者是 $64$，此时前者的效率是不如后者的。
• $O(1.02^n)$ 尽管是指数级(exponential)，但是它的效率并不逊色。

但是Big-Oh家族在理论上对算法效率进行分析往往是有效的，并且在 $n$ 比小的时候程序所消耗的时间往往是会忽略不计的。

---

总结

• Big-Oh家族定义及其渐进表示法总结

表示法	名字	描述	渐进符号	形式定义
$o(g(n))$	little-Oh	函数渐进地由$g$支配	$<$	$\forall c > 0, \exists n_0 > 0, \forall n \geq n_0 : | f(n) | < c \ g(n)$
$O(g(n))$	Big-Oh	函数以$g$为渐进边界	$\leq$	$\exists c > 0, \exists n_0 > 0, \forall n \geq n_0 : |f(n)| \leq c\ g(n)$
$\Theta(g(n))$	Big-Theta	函数由$g$为渐进边界和下边界	$\approx$	$\exists c’>0,\exists c’’>0, \exists n_0 > 0, \forall n \geq n_0 : c’g(n) \leq f(n) \leq c’’g(n)$
$\Omega(g(n))$	Big-Omega	函数由$g$为渐进下边界	$\geq$	$\exists c>0,\exists n_0>0,\forall n \geq n_0: f(n) \geq c\ g(n)$
$\omega(g(n))$	little-omega	函数渐进支配$g$	$>$	$\exists c>0,\forall n_0 > 0, \exists n \geq n_0 : f(n) > c\ g(n)$

• 如何求解一个算法的时间复杂度Big-Oh：
  • 建立算法函数的伪代码。
  • 求出该算法函数的原始运算数(number of primitive operator)和输入大小n的函数关系。
  • 根据该函数求出Big-Oh表示。

---

三. Master定理

分而治之(Divide and Conquer)

分而治之是一个设计算法的思想，它通常能够高速地处理问题。

分而治之的组成成分如下：

• 分解 (Divide)：将输入分为两个或多个不相交的输入子集。
• 递归 (Recur)：使用递归解决这些子集的子问题。
• 组合 (Conquer)：将所有子集的解组合起来形成输入的解。

---

递归关系 Recurrence Relation

定义：

A recurrence relation is a recursively-defined function.
递归关系(Recurrence Relation)是使用递归定义的函数。

假设一个程序的运行时间是 $T(n)$，那么递归关系会在一系列小于n的值中来表达 $T(n)$。

:::details 例子：归并排序(merge-sort)的递归关系及其时间复杂度的证明

关于归并排序的具体算法请看下面 五. 算法 中 归并排序。

假设归并排序的运行时间为 $T(n)$，那么

$$
\begin{aligned}
T(n) & = 2\ T(\frac{n}{2}) + b + an \T(1) & = 1
\end{aligned}
$$

• $2\ T(\frac{n}{2})$ 表示数组分成了两个子数组，每个子数组的大小为 $\frac{n}{2}$。
• $b$ 是分裂的花费。
• $an$ 是 merge 的花费。

因此我们经过带入可以得到：

• $T(2) = 2\ T(1) + b + 2a = 2 + b + 2a$
• $T(4) = 2\ T(4) + b + 4a = 2 (2 + b + 2a) + b + 4a = 4 + 3b + 8a$
• $T(8) = 2\ T(4) + b + 8a = 2 (4 + 3b + 8a) + b + 8a = 8 + 7b + 24a$

由此我们猜测 $T(2^k) = 2^k + (2^k - 1)b + k\ 2^ka, k\in \mathbb{N}$
我们可以使用数学归纳法(induction)来验证：

Claim: $T(2^k) = 2^k + (2^k - 1)b + k\ 2^ka, k\in \mathbb{N}$.
Base case: $k = 0$，$T(1) = 1 + 0 * b + 0 * 1 * a = 1$ is meet the claim.
Step case: Assume that the claim is true at k, and we need to prove that $T(k + 1)$ is true.
$$
\begin{aligned}
T(2^{k+1}) & = 2\ T(2^k) + b + 2^{k+1}a \
& = 2 (2^k + (2^k - 1)b + k\ 2^ka) + b + 2^{k + 1}a \
& = 2^{k+1} + (2^{k+1} - 2)b + b + k\ 2^{k+1}a + 2^{k + 1}a \
& = 2^{k+1} + (2^{k+1} - 1)b + (k + 1)\ 2^{k+1}a
\end{aligned} $$
$Q.E.D.$

我们假设 $T’(n) = n + (n - 1)b + an\log(n), \text{for } n = 2^k, k\in \mathbb{N}$。
我们可以证明出 $T(n)$ 是 $\Theta(T’(n))$。
因此，$T(n)$ 是 $\Theta(n\log n)$。

:::

---

Master定理 (Master Theorem)

考虑存在下面的递归关系：
$$
\begin{aligned}
T(n) & = a\ T(\frac{n}{b}) + f(n) \
T(1) & = 1
\end{aligned}
$$
这是一个由分而治之设计的算法：分解成 $a$ 个子集，每个子集的大小是 $\frac{n}{b}$，此外每个递归/循环有一些额外的操作 $f(n)$。

Master定理(Master Theorem)是一个根据 $a, b$ 的数值以及对 $f(n)$ 进行放缩来快速求出$T(n)$的Big-Oh家族的方法。

下面就对 $f(n), a, b$ 不同情况进行讨论。

注意，本笔记中不形式证明Master定理，具体可以自行查阅。

> $f(n) = 0$ 时

此时 $T(n) = aT(\frac{n}{b})$，我们可以使用数学归纳法证明出 $T(b^k) = a^k$。

我们令$n = b^k$，根据数学公式我们可以推导出 $a^k = (b^k)^{\log_ba}$，因此我们可以得到
$$T(n) = n^{\log_ba}$$

因此我们可以知道 $T(n)$ 是 $\Theta(n^{\log_ba})$。

> $f(n) \neq 0$ 时

此时可以分为三种情况：

$f(n)$ 的形式	$c$ 与 $\log_ba$ 的关系	$T(n)$的Big-Theta	描述
$f(n)$ 是 $O(n^c)$	$c < \log_ba$	$\Theta(n^{\log_ba})$	$f(n)$ 的 增长率非常小，此时忽略 $f(n)$
$f(n)$ 是 $\Theta(n^c(\log n)^k), k \geq 0$	$c = \log_ba$	$\Theta(n^c(\log n)^{k+1})$	$f(n)$ 的 增长率适中，此时混合使用$a, b, f(n)$
$f(n)$ 是 $\Omega(n^c)$, 并满足正则条件	$c > log_ba$	$\Theta(f(n))$	$f(n)$ 的 增长率非常大，此时只考虑 $f(n)$

情况三中需要满足正则条件(Regularity Condition)：
$$\exists k < 1 : a f(\frac{n}{b}) \leq k f(n)$$

该条件保证了这个条件确保 $f(n)$ 不会增长过快导致 $T(n)$ 完全被非递归部分主导。

注意$f(n)$ 的形式以及$c$ 与 $\log_ba$ 的关系。

• 情况一中可知，$f(n)$的渐进上边界都不如 $n^{\log_ba}$，那么$f(n)$ 的增长率是可以被忽略的。
• 情况二中可知，$f(n)$的增长率是与 $n^{\log_ba}$ 持平的，因此应该要混合使用$a, b, f(n)$。
• 情况三中可知，$f(n)$的渐进下边界都超过了 $n^{\log_ba}$，因此只考虑 $f(n)$。

---

四. 数据结构

一些定义

• 遍历(Traversals)：指访问(visit)一个数据结构的所有元素。

  • 每一个元素只访问一次。
  • 访问的顺序是系统的、有序的、有意义的。

• 抽象数据类型(Abstract Data Types, ADTs)：是数据结构的抽象。

  • 组成成分：
    • 储存的数据类型。
    • 对数据的操作。
    • 与操作相关的错误条件。
  • 一般ADT的相关操作会使用Big-Oh来限制效率。

• 具体数据类型(Concrete Data Types, CDTs)：是数据结构的实际。

  • ADT的实现是通过选择不同的CDT。
  • CDT是数据隐藏的和封装的（面向对象）。
  • CDT的选择影响运行时间和空间使用。

• 面向对象编程(Object-oriented)的原因：

  • 区分规范(specification) 和 实施细节(implementation details)
  • 使用相同的ADT来探索不同的CDTs。
  • 无需更改ADT的代码来快速更改和提升CDTs。

---

单向链表(Singly Linked List) (CDT)

介绍

A singly linked list is a concrete data structure consisting of a sequence of nodes. Each node stores an element and a pointer/reference to the next node.

成员

• Node 节点
  • Element 元素
  • next 指向下一个节点的指针
• head : Node* 头节点指针
• tail : Node* 尾节点指针 (可选)

功能性函数

插入类函数：

• void insertHead(Object)：插入头结点
  • 时间复杂度：$O(1)$
• void insertTail(Object)：插入尾节点
  • 如果有记录尾节点，时间复杂度： $O(1)$
  • 如果没有记录尾节点，时间复杂度： $O(n)$

删除类函数：

• void removeHead()：删除头节点
  • 时间复杂度：$O(1)$
• void removeTail(Object)：删除尾节点
  • 无论有没有记录尾节点，时间复杂度：$O(n)$
    • 因为要让尾节点的前一个节点的next指针指向NULL

交换类函数：

• void swapElement(Node, Node)：交换元素而不交换节点的位置
  • 时间复杂度 $O(1)$
• void swapNode(Node, Node)：交换节点的位置（不常用）
  • 时间复杂度 $O(n)$
    • 因为要找到这两个Node的上一个Node来修改next。

---

双向链表(Doubly Linked List) (CDT)

介绍

A doubly linked list provides a natural extension of a singly linked list.Each node stores an element and a pointer/reference to the next node and a pointer/reference to the previous node.

成员

• Node 节点
  • element 元素
  • next 指向下一个节点的指针
  • pre 指向上一个节点的指针
• head : Node* | Node 头节点指针/节点
• tail : Node* | Node 尾节点指针/节点

功能性函数

插入类函数：

• void insertHead(Object)：插入头结点
  • 时间复杂度：$O(1)$
• void insertTail(Object)：插入尾节点
  • 如果有记录尾节点，时间复杂度： $O(1)$
  • 如果没有记录尾节点，时间复杂度： $O(n)$
• void insertAfter(Node, Object)：插入到Node节点后面
  • 时间复杂度：$O(1)$

删除类函数：

• void removeHead()：删除头节点
  • 时间复杂度：$O(1)$
• void removeTail(Object)：删除尾节点
  • 如果有记录尾节点，时间复杂度： $O(1)$
  • 如果没有记录尾节点，时间复杂度： $O(n)$

交换类函数：

• void swapElement(Node, Node)：交换元素而不交换节点的位置（不常用）
  • 时间复杂度 $O(1)$
• void swapNode(Node, Node)：交换节点的位置（建议）
  • 时间复杂度 $O(1)$

补充

• 有两种双向链表设计方式
  • 让head和tail指向实实在在的节点。如果链表为空，则head = NULL, tail = NULL。
  • 分配head和tail为新的节点，节点的元素为空。如果链表为空，则head.next == tail。

数据结构的思考

相比于数组 Array，链表数据结构具有较快的插入和删除能力。但是，链表具有较差的查询能力，其查询能力的时间复杂度是 $O(n)$。

一般具有较快的插入、删除和查询能力的数据结构都比较复杂，例如：

• 跳表 (Skip List)：其三个操作的时间复杂度都是 $O(\log n)$。
• 平衡树(Balanced Trees)：其三个操作的时间复杂度都是 $O(\log n)$。
  • 红黑树(Red-Black Tree)
  • AVL树(AVL Tree)
• 哈希表(Hash Table)：其三个操作的平均时间复杂度都是 $O(1)$，最差情况下时间复杂度是 $O(n)$。

---

向量(Vector) (ADT)

介绍

向量(Vector)是一种抽象数据类型(ADT)。向量的主要目的是创建一个比数组(Array)更泛用的模型。

其主要的特性是：

• 一个元素在向量中的索引(index)被认为是前面元素的个数(number of elements prceding it)。
  • 为了不完全依赖于数组，因此我们不使用“索引(index)”概念，而使用“前面元素的个数”概念。
  • 例如对于一个向量 $A$ 来说，$A[2]$ 表示有 $2$ 个元素在它的前面，分别是 $A[0], A[1]$。
  • 这个概念也可以被称为**排名(rank)**。
• 与数组固定大小不同，向量一个自动调节大小的数据结构。

向量ADT主要操作(operator)/方法

• Object elemAtRank(int r)：返回 rank 为 r 的元素。
• Object replaceAtRank(int r, Object o)：替换掉 rank 为 r 的元素为 o，并返回原来的元素。
• void insertAtRank(int r, Object o)：在 rank 为 r 的位置插入新的元素 o。
• Object removeAtRank(int r)：删除 rank 为 r 位置的元素。
• int size()：返回向量大小。
• boolean isEmpty()：返回向量是否为空。

使用向量作为栈(Stack)

栈(Stack)是一个先入后出(first in last out, FILO)的数据结构，其操作主要是：

• Object top()：返回栈顶。
  • 相当于 elemAtRank(size())。
• void push(Object o)：在最后的元素(栈顶)后面添加一个新的元素。
  • 相当于 insertAtRank(size(), Object o)。
• void pop()：删除最后的元素(栈顶)。
  • 相当于 removeAtRank(size())。

基于数组的向量(Array-based Vector) (CDT)

是使用一个大小为N的数组V作为向量的CDT，并使用整型变量n记录向量的大小。

>操作/方法时间复杂度分析

• elemAtRank(r)：可以直接返回V[r]，因此其时间复杂度是 $O(1)$。
• replaceAtRank(r, o)：时间复杂度是 $O(1)$。
• insertAtRank(r, o)：需要对原来的元素进行右平移，在最坏的情况下(即 $r = 0$ )时间复杂度是 $O(n)$。
• removeAtRank(r, o)：需要对原来的元素进行左平移，在最坏的情况下(即 $r = 0$ )时间复杂度是 $O(n)$。
• size()：直接返回变量 n，因此时间复杂度是 $O(1)$。
• isEmpty()：直接返回 n == 0，因此时间复杂度是 $O(1)$。
• push(o)：不需要进行平移。
  • 如果不需要扩大数组时间复杂度是 $O(1)$。
  • 扩大数组需要平摊时间(amortized time)获取时间复杂度。具体可以看下面扩大数组中不同策略。
• pop()：不需要进行平移，因此时间复杂度是 $O(1)$。

平摊时间(amortized time)是从一组操作中每个操作平摊下来的时间。与平均时间(average time)不同，后者主要是针对一次操作的平均时间。

>扩大数组(Resize Array)

在insertAtRank(r, o) 和 push(o) 操作中，如果数组已经满了，那么需要替换数组为更大的数组。

替换数组需要复制原来的数据到新的数据中。假设当前数组的大小为 $c$，每次替换所使用的时间为 $s_2$，那么这个过程需要的时间$T(c) = s_2c$，即这个过程的时间复杂度是 $O(c)$。

扩大数组的方法一共有两种：

• 增量策略(incremental strategy)：使用固定的常数 c 来进行扩大数组。

  • 假设执行push的次数为 $n$，那么替换数组的次数一共为 $k = floor(n / c)$ 次。
  • 假设$T(n)$是执行push $n$ 次所需要的运行时间，$s_1$是一次push所需要的时间，$s_2$是一次替换数组所需要的时间。
    • $s_1$ 和 $s_2$ 都是常数。
    • $T(n) = s_1n + s_2(c + 2c + … + kc) = s_1n + s_2c\frac{k(k+1)}{2}$，因此 $T(n)$ 是 $O(n^2)$。
  • 平摊下来每次 push 操作的时间复杂度是 $\frac{T(n)}{n}$ 是 $O(n)$。这个是要比一般 push 操作所需要的时间复杂度 $O(1)$ 是要差的。

• 双倍策略(doubling strategy)：双倍数组的大小。

  • 假设执行push的次数为 $n$，那么替换数组的次数一共为 $k = floor(\log n)$ 次。
  • 假设$T(n)$是执行push $n$ 次所需要的运行时间，$s_1$是一次push所需要的时间，$s_2$是一次替换数组所需要的时间。
    • $s_1$ 和 $s_2$ 都是常数。
    • $T(n) = s_1n + s_2(1 + 2 + 4 + … + 2^{k - 1}) = (s_1 + s_2)n - s_2$，因此 $T(n)$ 是 $O(n)$。
  • 平摊下来每次 push 操作的时间复杂度是 $\frac{T(n)}{n}$ 是 $O(1)$。

---

树(Tree) (ADT)

介绍

树是一种抽象数据结构(ADT)。

In computer science, a tree is an abstract model of a hierarchical structure. A tree consists of nodes with a parent-child relation.

成员

• Node 节点
  • element 元素
  • parent 父节点
  • children[] 子节点
• root : Node* 根节点：不具有父节点的节点。
• internal : Node 内节点：具有至少一个子节点的节点。
• leaf / external : Node 叶节点/外节点：不具有子节点的节点。
• ancestors : Node → Node[] 祖先节点：(递归定义) 一个节点其父节点和其父节点的祖先节点的数组/集合。
• descendant : Node → Node[] 祖孙节点：(递归定义) 一个节点其所有子节点和所有子节点的祖孙节点的数组/集合。
• depth : Node → Int 节点的深度：该节点的祖先节点的个数(不包括自己)。
  • 根节点的深度为0，根节点的子节点深度为1，以此类推。
• height : Tree → Int 树的高度：最大的叶节点深度。或者说从根节点到叶节点最长的路径(不包括根节点)。
  • 只有根节点的树的深度为0。

树ADT主要操作/方法：

> 基础方法 (Generic)：

• int size()：返回树的大小。
• bool isEmpty()：返回树是否为空。
• Iterator iterator()：返回树的遍历所有元素的迭代器。
• Iterator positions()：返回树的以一定顺序遍历位置的迭代器。

> 接入方法 (Accessor)：

• Node root()：返回树的根节点。
• Node parent(Node)：返回节点的父节点。
• Iterator children(Node)：返回节点的子节点迭代器。

> 查询方法 (Query)：

• bool isInternal(Node)：是否是内部节点。
• bool isExternal(Node)：是否是叶节点。
• bool isRoot(Node)：是否是根节点。

树的遍历 (Traversals)

> 前序遍历 Preorder Traversal

先遍历父节点，再从左到右遍历其子节点。

Algorithm preOrder(v)
  visit(v)
  for each child w of v
    preorder(w)

> 后序遍历 Postorder Traversal

先遍历子节点，再遍历父节点

Algorithm postOrde(v)
  for each child w of v
    postOrder(w)
  visit(v)

---

二叉树(Binary Tree) (ADT)

定义

二叉树是一种抽象数据结构(ADT)。

• 一般定义：

  a tree whose each internal node has at most two children, and the children of a node are an ordered pair, though one might be “missing”.

• 递归定义：

  A tree consisting of a single node, or a tree whose root has an ordered pair of “children”, each of which is missing (a null) or is the root of a binary tree

• 特点：

  • 每个节点最多有两个子节点
  • 节点之间是有序的，即左子节点和右子节点，尽管有一个是空节点。

性质

> 合适/完满二叉树 (proper/full binary tree)

A binary tree is said to be “proper” (a.k.a. “full”) if every internal node has exactly 2 children.
如果二叉树的所有内部节点都具有两个子节点，那么称这个二叉树是合适/完满二叉树。

> 完美二叉树 (perfect binary tree)

A binary tree is perfect if it is proper and all leaves are at the same depth.
如果一个满二叉树中所有的子节点都在同一个深度，那么称这个二叉树是完美二叉树。

• 在深度 $d$ 拥有的节点的个数为 $2^d$
• 在深度 $d$ 及其以下的深度总结点个数为 $2^{(d+1)}-1$
• 高度为 $h$ 的树总节点为 $n$，那么有 $h = \log_{2}(n+1) - 1$，$n = 2^{(h + 1)} - 1$

> 完全二叉树 (complete binary tree)

除了叶节点所处的深度以外，其他深度是一个完美二叉树，并且叶节点是靠右排序的二叉树是完全二叉树。

二叉树的遍历 (Traversals)

除了树通用的前序遍历和后序遍历以外，还有一个中序遍历(Inorder Traversal)：

先遍历左子节点，再遍历该节点，最后遍历子节点。

Algorithm inOrder(v)
  if hasLeft(v)
    inOrder(v.left)
  visit(v)
  if hasRight(v)
    inOrder(v.right)

二叉树的效率分析

• 求树的高度：如果树的大小为 $n$，那么：
  • 对于完美二叉树来说，时间复杂度是 $\Theta(\log(n))$。
  • 对于非完美二叉树来说，考虑到一条链，时间复杂度是 $\Omega(\log(n))$ 和 $O(n)$。

基于数组的二叉树 (Array-Based Representation of Binary Tree) (CDT)

它也可以被称为 **树形数组(tree-as-array)**。它是一种使用数组作为CDT实现二叉树ADT的方式。

一般使用 int rank(Node) 来表示节点的数组索引。注意，它返回的是整型。

• rank(root) = 1：根节点的索引是 $1$。
• rank(parent(node)) = rank(node) >> 1：每个节点的父节点是该节点的索引除以 $2$。
• rank(left_child(node)) = rank(node) << 1：每个节点的左节点是该节点的索引乘以 $2$。
• rank(right_child(node)) = rank(node) << 1 + 1：每个节点的右节点是该节点的索引乘以 $2$ 加 $1$。

树形数组的优点：

• 能够节省空间。因为不用储存相关的指针，而是使用计算代替。
• 储存能够更紧凑，具有更好的内存局部性”better memory locality”。
• 很好地解决缓存和内存层次结构的问题——当访问数组元素时，其他条目可以被拉入缓存，因此访问速度更快。

---

优先队列(Priority Queue) (ADT)

介绍

优先队列是一个抽象数据结构(ADT)。优先队列是储存一组具有 (key, value) 的数据结构，并能够有效地返回和操作其中具有最小/最大 key 的元素。

一般我们默认优先队列是**最小优先队列(Min-Priority Queue)**，也就是返回/操作拥有最小key的元素。

优先队列ADT主要操作/方法：

• void insert(k, v)：插入一组(k, v)的元素。
• Element removeMin()：删除并返回具有最小key的元素。
• Element min()：返回具有最小key的元素。
• int size()：返回元素个数。
• bool isEmpty()：优先队列返回是否为空。

基于二叉堆(Binary Heap)的优先队列 (CDT)

本笔记中默认的二叉堆是 小根堆。

A binary heap is a complete binary tree storing key-value pairs at its nodes.
二叉堆是将 (key, value) 对储存在节点的完全二叉树。

除了二叉堆以外，还有二项式堆(Binomial Heap)和斐波那契堆(Fibonacci Heap)。

二叉堆具有以下的性质：

• Heap-Order：对于每一个除了根以外的节点，都有 key(v) >= key(parent(v))。
  • 即子节点的值不会比父节点更小。
  • 那么堆顶，即二叉堆的根节点是所有节点中的最小值。
• Complete Binary Tree：是一个二叉树。因此如果一共有 $n$ 个节点，则树的高度为 $h = \log n$。

堆的插入(insert)

步骤如下：

1. 根据完全二叉树性质寻找插入点 $Z$ 作为叶节点。
2. 储存 $key$ 值给点 $Z$。
3. 恢复堆序属性(unheap操作)：将插入点 $Z$ 从下到上进行 冒泡，如果父节点的 key 值比 $Z$ 大，那么就交换两个节点的位置或元素，直到父节点的 key 值比 $Z$ 小或者已经到达根节点。

关于 $1$，如果使用结构体模拟树的结构，那么时间复杂度可能会达到 $O(n)$。但是如果使用数组作为CDT模拟二叉树(具体可看上方二叉树中基于数组的二叉树，树形数组)，那么只需要在数组的末尾插入新的节点即可，此时的时间复杂度是 $O(1)$。
关于 $3$，因为二叉树的高度是 $h = \log n$，因此 upheap 操作的时间复杂度是 $O(\log n)$。

堆的删除(remove / pop)

堆的删除指的是删除堆顶。步骤如下：

1. 使用最后一个节点 $w$ 代替根节点。
2. 删除 $w$ 原节点。
3. 恢复堆属性(Downheap操作)：选择两个子节点中最小的子节点，如果该子节点的key值比 $w$ 节点的小，那么就交换两个节点的位置或元素，直到所有子节点的 key 值比 $w$ 大或者已经达到叶节点。

---

映射(Maps) (ADT)

介绍

A map models a collection of (key, value) entries that is searchable by the key.

性质：

• 具有搜索、插入、删除元素的功能。
• 具有相同 key 值的元素是不被允许的。

映射ADT主要操作/方法：

• Value get(Key k)：如果存在key相应的元素，则通过 key 获取相应的 value，否则返回 NULL。
• Value put(Key k, Value v)：插入 (key, value) 对。如果已经存在 key 在映射里则返回 NULL，否则返回 value值。
• Value remove(Key k)：如果存在key相应的元素，则通过 key 来删除并返回该元素的 value，否则返回 NULL。
• int size()：返回元素个数。
• bool isEmpty()：返回是否为空。
• Iterator keys()：返回 key 的迭代器。
• Iterator values()：返回 value 的迭代器。
• Iteraotr entries()：返回 (key, value) 的迭代器。

基于简单链表的MAP (CDT)

• get(k)：遍历链表来寻找 key。时间复杂度是 $O(n)$。
• put(k, v)：遍历链表来寻找是否有重复的 key，如果没有则插入到链表中。时间复杂度是 $O(n)$。
• remove(k, v)：遍历链表来寻找 key。时间复杂度是 $O(n)$。

因为链表的特性（具有较差的访问能力），因此无论是排序的链表还是未排序的链表（链表无法使用二分查找法），时间复杂度操作都是 $O(n)$。

基于哈希表的MAP (CDT)

基本思想：将每个 key 转化成 index 放入一个较大的数组 Array 中。

哈希表的特性：

• 哈希值 (hash value)：由哈希函数得到的值被称为哈希值。
• 哈希码 $h_1$ (hash code)：是一个键值转一个整型的函数，即keys → integers。一些可能的方法：
  • 将 key 的内存地址作为哈希码。
  • 将 key 的 bit 值转化成整型作为哈希码。一般用于内存不大于整型的数据类型，例如byte, short, int, float。
  • 将 key 的 bit 值划分成相同长度的部分，对这些部分求和(忽略溢出)。适用于内存大于整型的数据类型，例如 double, long。
  • 多项式累积方法。
• 压缩函数 $h_2$ (Compression function)：是一个将整型压缩到一定范围的函数，即integers → [0, N-1]。一些可能的方法：
  • 除法(Division)：$h_2(x) = x \mod N$。
    • $N$ 通常是一个素数。
  • 乘加除法(Multiply, Add and Divide (MAD))：$h_2(x) = (ax + b) \mod N$。
    • $a, b$ 是非负整数。
    • $a \mod N \neq 0$，否则无论 $x$ 为多少总会映射到 $b$。
• 哈希函数 $h$ (hash function)：是一个将对象(Object)映射到一个固定的范围 $[0, N-1]$ 整型的函数。
  • 此时有 $h(x) = h_2(h_1(x))$。
  • 哈希函数的主要目的是使用明显随机的方式来将 keys 分散。
  • 分散的目的是为了减少冲突(Collision)。
  • 随机的目的是为了减少模式(Pattern)，从而减少冲突。
• 冲突 (Collision)：当不同的元素获取到相同的索引时，会发生冲突。一些可能的解决方法：
  • 分离链(Separate Chaining)：让相同 index 的元素以链表的形式连接起来。
  • 二叉搜索树(Binary Search Tree)。
  • 开放地址(Open addressing)：让冲突的新元素放入到下一个可用的数组中。一些可能的方法：
    • 线性探索(Linear probing)：使用一个常数 $c$ 来进行冲突元素的新元素寻址，即$h(k) + c$。
      • 一般使用循环数组作为哈希表。
      • 可能会导致未来新元素使用更长的时间来寻址。
      • 如果数组满了可能会导致死循环，因此要规定最多循环次数。
      • 如果中间有冲突的数组被删除，可能会导致后面冲突的数组查询失败。
        • 一个删除的解决方案是不断检测右边是否具有相同的哈希值，如果相同则将该数值重新插入。
        • Lazy deletion延迟删除：将被删除的数值标记为“删除”，只当用到它的时候再进行修复。当被查询到“删除”标记的点时直接跳过而不是停止。
    • 双哈希(Double Hashing)：使用一个额外的哈希函数 $d(k)$ 来辅助寻找新元素。
      • 新的哈希值为 $(h(k) + j\ d(k))\mod N, j\in[0, N-1]$，选择第一个空元素作为哈希值。一些可能的 $h(k)$：
        • $d(k) = q - (k \mod q)$，其中 $q < N$ 且 $q$ 是素数。
      • 对于线性探索来说，$d(k) = 1$。
      • $N$ 必须是素数，以探索所有的可能数组包。

那么使用哈希表来实现Map主要的思路是：

• 寻找哈希函数：将 $(k,v)$ 储存在 $i = h(k)$ 索引的数组中。
• 处理冲突。

基于分离链(Separate Chaining)处理冲突的方法

因为分离链定义让相同 index 的元素以链表的形式连接起来，其中链表中每个节点还有一个单独的 key 值用于寻找具体的元素。

那么链表的每个节点应该具有以下的操作，假设有 $m$ 个冲突的元素：

• Element get(k)：获取key = k的元素。其时间复杂度是 $O(m)$。
• Element put(k, v)：放入(k, v)对的元素，需要检测是否有相同 key 的元素，如果有则返回null。因此时间复杂度是 $O(m)$。
• Element remove(k)：删除key = k的元素。其时间复杂度是 $O(m)$。

那么使用基于分离链哈希表的map具体实现方式如下：

• get(k)：return A[h(k)].get(k)。
• put(k, v)：return A[h(k)].put(k)。注意要让 size++。
• remove(k): return A[h(k)].remove(k)。注意要让 size--。

对于每个操作，最佳访问时间是 $O(1)$，最差访问时间依然是 $O(n)$，即全部都有冲突。但是平均下来，其时间复杂度应该是 $O(n / N)$，其中 $N$ 是哈希表数组的容量。

哈希函数的性能分析

在最坏的情况下，搜索、插入和删除的时间复杂度都是 $O(n)$。

一般用负载因子(load factor) $\alpha = n / N$ 来表示哈希表的性能。

哈希表各个操作的期望值基本上都是 $O(1)$。具体证明可自行查阅。

---

二叉搜索树(Binary Search Tree) (ADT)

A binary search tree is a binary tree storing (key,value) entries at its internal nodes and satisfying the following “search tree” property.
二叉搜索树是一个储存(key,value)值到节点的二叉树，并满足下面的性质：

性质：

• 对于任意一个内部节点 $v$，拥有左子节点 $u$ 和 右子节点 $w$，满足 key(u) <= key(v) <= key(w)。
• 对于任意一个节点 $v$，其左边子辈的值都比 $v$ 小，右边子辈的值都比 $v$ 大。
• 换句话说，二叉搜索树的中序遍历(inorder traversal)返回的数组一定是根据key升序的。

二叉搜索树ADT主要操作/方法

• Node search(Key k)：返回key = k的节点，如果没有则返回null。
  • 实现：比较当前节点储存的key 与 k 相比较，如果等于则返回。如果k大则查找右节点，如果k小则查找左节点。如果不存在节点，则返回null。
  • 时间复杂度是 $O(h)$，其中 $h$ 是树的高度。
  • 如果是平衡二叉树，则时间复杂度是 $O(\log n)$。
• void insert(Key k, Value v)：插入 (k, v) 对。
  • 实现：使用二分法找到要插入的位置，将其插入进去。
  • 时间复杂度是 $O(h)$，其中 $h$ 是树的高度。
• Node remove(Key k)：删除 key = k 的节点。
  • 实现：使用二分查找找到要删除的节点删除，分为下面四个情况：
    • 没有找到该节点，此时返回 null。
    • 该节点是叶节点，此时删除该节点。
    • 节点具有一个子节点，将该子节点替换到原来的位置。
    • 节点具有两个子节点，此时根据树的中序遍历找到当前key的下一个key节点 $w$ ($w$ 称为该节点的中序后继)，并使用这个节点 $w$ 替代该节点，再尝试删除 $w$，直到不符合被删除的节点具有两个子节点为止。
  • 时间复杂度是 $O(h)$，其中 $h$ 是树的高度。

平衡二叉树(Balanced Trees)

平衡二叉搜索树的任何结点的左子树和右子树高度最多相差1。
平衡二叉树的高度 $h = \log n$。

一般使用旋转(notation)的方法来让二叉搜索树逐步变成平衡二叉树。

一次旋转 (Single Rotation)

一次旋转适合三个高度节点之间呈类似于 \ 和 / 的直线形。也就是中间高度的节点是中间值的情况。

过程如下：

• 选择一个节点 $P$。
• 选择该节点的一个子节点 $C$。
• 交换两个节点：
  • 选择 $C$ 中相反方向的子节点 $V$：如果 $C$ 是 $P$ 的左节点，那么就选择 $C$ 的右节点。否则选择左节点。
  • 处理 $P$ 的父节点：
    • 将 $P$ 的父节点相应方向的子节点修改为 $C$。
    • 将 $C$ 的父节点修改为 $P$ 的父节点。
    • 如果 $P$ 为根节点，那么修改根节点为 $C$。
  • 处理 $C$ 的子节点 $V$：
    • 将 $V$ 的父节点修改为 $P$。
    • 将 $P$ 原来方向上的子节点 $C$ 的位置修改为 $V$。
  • 处理 $C$ 和 $P$：
    • 将 $C$ 原来 $V$ 位置的子节点修改为 $P$。
    • 将 $P$ 的父节点修改为 $C$。

整个过程时间复杂度是 $O(1)$。

二次旋转 (Double Rotation)

诸如下图中的类似 >和< 形，是无法使用一次旋转的，如果只旋转a 和 c 将无法改变高度。

此时需要先将>或<形旋转成/或\形，再进行一次旋转。整个过程被称为二次旋转，如下图。

具体的其他二叉树方法将（例如AVL树、红黑树）不在本笔记中展示。可能会未来在其他笔记中展示。

---

五. 算法

算法的设计思路通常有这么几种：

• 暴力搜索(Brute Force)：生成所有潜在解决方案并测试哪些是实际解决方案。时间复杂通常非常高，是属于多项式级其以上的时间复杂度。
• 分而治之(Divide and Conquer)：递归地将问题分解成更小的部分并逐步解决它们，然后将它们重新组合在一起。是一种比较高效的设计思路。
• 启发式(Heuristics)：是一个使用经验法则(rule of thumb)设计的算法。启发式算法比简单的方法能够做出更好的决策，但仍然不一定是最佳的。
• 动态规划(DP)：DP是一种适用于最优解满足“分解性质”情况的通用方法。

---

排序算法(Sorting algorithms)

排序算法的性质：

• 排序稳定性(Stability)：如果两个元素键值相等，排序算法会保留这两个元素的相对位置。
• 排序自适应性(Adaptive)：如果数组已经接近已排序，那么算法的效率会提高。
• 排序接入模式(Access Patterns)
  • Sequential Access：数据的读取和写入是按照其在存储器中存放的顺序进行的。
  • Random Access：数据储存中能够在常数时间 $O(1)$ 内直接访问任意位置的数据。
• 是否需要额外空间。

如果没有特殊说明，以下算法都默认从小到大排序/升序、使用 数组(array) 作为数据结构。

基于比较的排序算法的一些思考

如果一个排序算法仅包含关于成对比较元素的信息，那么就称这个排序是基于比较的(comparison-based)。

并不是所有的排序算法都是基于比较的，例如桶排序(bucket sort)是使用实际的值来进行排序的，其时间复杂度是$O(n)$，但是其实现依赖于其值的范围。是一种使用空间换取时间的方法。

对于 $n$ 个数的数组来说，它一共拥有 $n!$ 种排序方法。我们使用基于比较的算法来对数组进行排序是通过两两比较来减半它排序方法的可能性。也就是说，基于比较的排序算法本质其实是逐步将 $n!$ 减半成 $1$。

这意味着我们需要去做 $\log_2(n!)$ 次比较。实际上 $O(\log(n!)) = O(n \log n)$。也就是说基于比较的算法不能比 $O(n \log n)$ 更优。

---

1. 冒泡排序(Bubble sort)

基本思想

让大的元素逐渐往后移动。

• 外部循环(Outer loop)：扫描整个数组。
• 内部循环(Inner loop)：对于数组每个元素与右边邻域对比，如果右边邻域更小则立即交换。

算法思考

因为算法中最大元素像水泡一样逐渐向上冒，因此被称为冒泡排序。

复杂性分析

考虑到最差的情况，也就是每次循环都会进行交换。外部循环次数为$(n - 1)$，假设当前外部循环$index = i$，那么内部循环次数为 $(n - i - 1)$，因此总循环次数为 $\frac{n(n - 1)}{2}$。

假设比较和交换原始操作数为 $t$ 为常数，循环以外的原始操作数为 $k$ 为常数，那么总原始操作数为 $\frac{n(n - 1)}{2} + t(n - 1) + k$。

根据删除规则，我们可以知道它的时间复杂度是 $O(n^2)$。

此外，也可以使用递归关系来证明冒泡排序的时间复杂度：

:::details 使用递归关系证明冒泡排序的时间复杂度

首先冒泡排序并不是天然递归的，而是一个双重循环。

但是我们能使用递归思想来将冒泡排序改成递归：如果要将长度为 $n$ 的数组进行排序，首先将这个数组中的最大数值通过冒泡操作交换到当前数组最右边的位置并固定，随后再将剩下 $n - 1$ 的数组进行排序(递归)。

这样就写出其运行时间的递推公式：
$$
\begin{aligned}
T(n) & = dn + T(n - 1) \
T(1) & = 1
\end{aligned}
$$

• $dn$ 表示通过冒泡操作交换所需要的时间。
• $T(n - 1)$ 表示剩余数组排序所需要的时间。

我们可以根据等差数列求出 $T(n)$ 的通项公式为：
$$T(n) = 1 + (\frac{n(n+1)}{2} - 1) d$$

那么很明显 $T(n)$ 是 $\Theta(n^2)$。

:::

算法的性质。

• 如果相同的元素不进行交换，那么该算法 具有 稳定性。
• 可以通过添加变量来让算法 具有 自适应性（内部循环没有进行任何交换）。
• 不需要额外的空间。
• 可适用于单向链表的swapElement(Node, Node)，时间复杂度不变。

---

2. 选择排序(Selection sort)

基本思想

保持数组后面的元素不变作为已排序的元素，前面的元素作为未排序的元素，选择未排序的元素组中最大的元素插入到已排序元素组的头部。

• 外部循环：扫描整个数组。
• 内部循环：扫描整个未排序部分的数组。并不会让最大的元素立即交换，而是记录住最大元素的位置。等内部循环扫描完，将被记录的元素：
  • 插入到已排序部分的数组的最左边。或者：
  • 与未排序部分的数组最右边的元素交换并将其加入到已排序部分数组。

算法思考

与冒泡排序不同，冒泡排序是比较当前元素和其邻域，而该排序是比较当前元素和被记录的元素。
为什么要延迟交换而不是立即交换：

• 如果交换操作可能会比较昂贵，并不像数组一样是$O(1)$，那么就需要尽可能减少交换次数。
• 如果数组非常大，那么需要尽可能地减少交换次数来提高效率。

复杂度分析

相比于冒泡排序，它们具有相同数量的迭代和比较，仅仅是有更少数量的交换。

因此它的时间复杂度也是$O(n^2)$。

算法的性质。

• 该算法 不具有 稳定性。
• 该算法 不具有 自适应性。
• 不需要额外的空间。
• 可适用于单向链表的swapElement(Node, Node)，时间复杂度不变。

---

3. 插入排序(Insertion sort)

保持数组前面元素的排序不变作为已经排序的元素，后面的元素作为未排序的元素。选择当前未排序元素不断交换左边比该元素大的元素，并将其加入到已经排序的元素。

• 外部循环：扫描整个数组。
• 内部循环：获取并记录当前未排序元素的最左边元素，从右到左扫描已经排序的元素，如果被扫描的元素比记录的元素大，那么就交换，直到被扫描的元素比记录的元素小。

复杂度分析

• 在最坏的情况下，它的外部原始操作数是 $O(n)$，内部原始操作数是 $O(n)$，因此它的总时间复杂度是$O(n * n) = O(n^2)$。
• 在最佳的情况下，它内部循环操作数是 $O(1)$，那么它的总时间复杂程度是 $O(n * 1) = O(n)$。

算法的性质

• 如果相同的元素不进行交换，那么该算法 具有 稳定性。
• 该算法 具有 自适应性。
• 不需要额外的空间。
• 不适用于单向链表。适用于双向链表。

---

4. 归并排序(Merge sort)

归并排序是一个基于分而治之(divide-and-conquer)的算法，它是先划分再排序。

• 分解 (Divide)：将待排序的数组 $S$ 分解为两个部分 $S_1$, $S_2$。
  • 分解直到只剩下单个元素或者空元素为止。因为单个元素的数组一定是已经排序好的数组。
  • 分解只是简单的数学运算，因此时间复杂度是 $O(1)$。
• 递归 (Recur)：递归地将 $S_1$ 和 $S_2$ 进行排序(带入到分而治之中)。
  • 递归分解，回归组合。
  • 递归全部子集的时间复杂度是 $O(\log(n))$。
• 组合 (Conquer)：将已排序的 $S_1$ 和 $S_2$ 合并(merge)。
  • merge是基于两个已经排序好的数组进行的：依次判断两个数组当前第一个数(最小的数)，选择最小的一个放入到新的数组后面，直到有一个数组为空后，将另一个数组剩余的元素依次放入到新的数组后面。
  • 假设放入的操作时间复杂度是$O(1)$，那么合并的时间复杂度是 $O(n)$。

归并排序递归调用的过程是一个二叉树结构。

复杂度分析

综上所述，归并排序的时间复杂度是 $O(n\log{n})$。
此外可以使用递归关系来证明归并排序的时间复杂度，详细请见 三.Master定理 中 递归关系 中的样例。
归并排序需要用到额外的空间，因此其空间复杂度是 $O(n)$。
也可以使得空间复杂度是 $O(1)$，但是过于混乱一般不作考虑。

算法的性质

• 在归并遇见相等数据时，如果优先选择左边数组那么该算法 具有 稳定性。
• 该算法 不具有 自适应性。
• 该算法 需要 额外的空间。
• 该算法对数据的访问是顺序的(sequential)，因此在硬盘中具有较好的排序效率。
• 因为依赖于快速对中间的数据进行访问，因此不太适合使用链表。

---

5. 快速排序(Quick Sort)

快排是一个基于分而治之的算法，它是先排序后划分。

• 分解 (Divide)：称之为partition操作。选择一个元素 $x$ 称之为枢(pivot)，并将数组 $S$ 分为：
  • $L$：元素小于 $x$ 的。
  • $GE$ 元素大于等于 $x$ 的。
  • pivot经常是使用随机选择。
  • 假设 交换 或者 删除再插入 的时间复杂度是$O(1)$，那么分解的时间复杂度是 $O(n)$。
• 递归 (Recur)：对 $L$ 和 $GE$ 使用进行递归排序，带入到分而治之中。
  • 最差的情况下，选择的枢总是最小/最大值，那么此时递归所有的子集时间复杂度是 $O(n)$。
  • 最佳的情况下，选择的枢总是中间值，那么此时递归所有的子集时间复杂度是 $O(\log n)$。
• 组合 (Conquer)：将 $L$ 和 $GE$ 左右连接起来。
  • 组合只是简单的连接，时间复杂度是 $O(1)$。

快速排序递归调用的过程是一个二叉树结构。

快速算法的分解(Divide)实现形式

该操作称为partition操作。

• 使用额外的空间进行分解，具体思想如下：

  1. 创建两个数组，分别表示 $L$ 和 $GE$。
  2. 选择一个枢(pivot)。
  3. 从左到右遍历数组，将小于枢的数加入到 $L$，将大于等于枢的数加入到 $GE$。

• 使用双指针的方法进行分解，这个方法是就地(in-place)，步骤如下：

  1. 选择一个枢(pivot)。
  2. 定义两个指针 $j$ 和 $k$，分别初始化指向数组的开头和结尾。
  3. 使用 $j$ 向右扫描，直到找到第一个 $\geq$ 枢的元素 或者 $j == k$ 停止。
  4. 使用 $k$ 向左扫描，直到找到第一个 $<$ 枢的元素 或者 $j == k$ 停止。
  5. 交换 $j, k$ 的元素。
  6. 如果 $j < k$，则返回 $3$。
  7. 此时 $j == k$，并且此时 $j, k$ 的位置元素等于枢，也是 $GE$ 位置的左边界线。

算法的思考

如果选择枢的方式是固定而不是随机的(例如总是选择第一个值作为枢)，并且出现了 $L$ 子集是空的情况(此时选择的枢是最小值)，那么此时会导致算法出现死循环。因为每次对 $GE$ 子集进行排序时，总是会选择最左边的值(也是最小值)作为枢，从而导致 $L$ 子集是空的情况。

快速排序要避免固定选择枢和出现一方子集是空集的情况，否则可能会导致死循环。

• 解决方法1：使用随机的方式选择枢。
• 解决方法2：将排序分为三个部分，分别是 $L$, ${pivot}$, $E+G$。
• 解决方法3：三点取值，选择最左边的数、中间的数和最右边的数中的中位数作为枢。

复杂度分析

• 最差的情况下，快速排序的时间复杂度是 $O(n^2)$。
• 最佳的情况下，快速排序的时间复杂度是 $O(n\log{n})$。
• 平均情况下，在一半的时间中快速排序选择的枢是中间值，那么时间复杂度是 $O(n\log{n})$。
  • 也可以认为平均情况下，选择的枢值总是让两个子集分解成 $\frac{1}{3}$ 和 $\frac{2}{3}$ 两个区域，也就是说递归二叉树的高度是 $\frac{3}{2}\log n$。
  • *具体证明可以自行查看维基百科*。

快速排序不需要用到额外的空间，因此其空间复杂度是 $O(1)$。

算法的性质

• 快速排序 不具有 稳定性。
• 该算法 不具有 自适应性。
• 该算法 不需要 额外的空间，是就地(in-place)的算法。
• 该算法对数据的访问是随机的(randomized)。
• 因为是使用 交换 或者 删除再插入 操作进行，因此可以使用双向链表。

---

启发式算法(Heuristics)

启发式算法是一个使用经验法则(rule of thumb)设计的算法。启发式算法比简单的方法能够做出更好的决策，但仍然不一定是最佳的。
通常有两种：

1. 程序中的决策可以给出准确/最佳的答案，但通常是为了加快程序运行速度。
   • 例如，A*搜索算法中使用可接受的启发式方法(Admissible heuristic)、在快速排序算法中使用随机选择的方式选择枢(pivot)。
2. 程序中的决策可能不会给出最佳答案，但旨在给出以其他方式无法获得的良好答案。
   • 一般用于解决一些NP-hard问题，例如 TSP问题、图染色问题等。
   • 例如 遗传算法、模拟退火。
   • 具体可以参考AIM-优化算法笔记。

贪心算法(Greedy)

贪心算法是一种常见的启发式算法。贪心算法是做出短期内看起来最好的决定，而不考虑未来的策略。

一些贪心算法可以得到最优解，例如最小生成树(Minimal Spanning Tree, MST)中Prim算法。

大部分贪心算法无法给出最优解，但是可以给出接近最优的解。

最小生成树问题(Minimal Spanning Tre, MST)

问题输入：联通的、有边权值的无向图(connected, undirected, weighted graph)。
问题输出：一棵树，仅使用图中存在的边连接图中所有顶点，并且边权重的和是最小的。

Prim算法

思路：

1. 选择任意顶点 $M$。
2. 选择对外可以连接到的所有的点中最小的那个边，并将边加入到 MST中，将点加入到内部的点中。
3. 是否全部连接，如果没有则返回 $2$。通过已连接的边个数判断，即 边的个数 $e = n - 1$。

算法实现：

• $1.$ 初始化数组 value[n] = inf，数组大小为点的个数，表示表示内部点对未连接的点边权的最小值；初始化连接边的个数m = 0。
• $2.$ 随机选择一个点 $M$。
• $3.$ 使value[M] = 0，并根据 $M$ 连接的所有边 $(M, V)$ 更新 edge 数组。即

  value[M] = 0              # 因为已经被连接，所以更新为0
  forall e in edge(M)
    v = e.v                 # 获取边连接的另一个点
    if(e.value < value[v])  # 根据边权值更新对外连接点的大小
      value[v] = e.value 

• $4.$ 找到 value[v] != 0 中最小的点 $V$，使 value[V] = 0，m++。
• $5.$ 跟 $3$ 一样根据 $V$ 连接的所有边 $(V, U)$ 更新 edge 数组。
• $6.$ 判断是否所有的点已经连通，即 (m - 1) == n，如果没有则返回 $4$。

---

动态规划(Dynamic Programming, DP)

DP is a general method that can be suitable when the optimal solutions satisfy a “decomposition property”.
DP 是一种适用于最优解满足“分解性质”情况的通用方法。

DP的步骤通常如下：

1. 将最优解分解为子解相当于将问题分解为子问题，并且子解对于子问题是最优的。
2. 因此，最优解可以通过更小的子问题的最优解来构建。

与分治法不同的是，DP中的子问题可以重叠，即不同的路径可能会遇见相同的子问题。

因此DP的思想通常是，对于某一个解 $S_n$，如果我想要得到这个解，我该直到哪些解才能得出这个解，并依次获取和尝试合并这些可能解的组合。又或者说，我现在已知某一个解，我是否可以让这个解和其他输入/解组合获取一个新的解。其中这个“得到”和“获取”的过程是一个状态转移的过程，这个过程是一个状态转移方程/贝尔曼方程(Bellman Equation)。

• 例如，假设有这样一个问题：给出一个整型集合 $S$，和一个目标值 $K$，我是否可以找出一个 $S_{sub}$ 的子集，其元素的和等于 $K$。
  • 假设我们输入 $S[i], 0 \leq i \leq (n-1)$ 是集合第 $i$ 个元素。
  • 我们使用 $dp[i][m] = true, 0 \leq m \leq K$ 来表示使用前 $i$ 个元素组成的子集中 $S_{sub}$ 元素和可以等于 $m$。
  • 如果我们知道 $dp[i - 1][m] = true$，那么可以根据它和当前元素 $S[i]$ 得出 $dp[i][m + S[i]] = true$。
  • 如何知道$dp[i - 1][m] = true$? 只需要对 $m$ 进行遍历 $(0 \leq m \leq K-S[i])$ 依次检查是否为true即可。
  • 由此我们就可以得到状态转移方程：$dp[i][m] = dp[i][m]\ \text{ | } \ dp[i - 1][m - S[i]]$。
  • 时间复杂度是 $O(kn)$。
  • 此外我们可以使用滚动数组将其变成一维dp，此时对容量 $m$ 的遍历是倒着的（如果正着就会导致元素 $i$ 被重复计算，此时属于完全背包问题）。

与暴力搜索，暴力搜索是将所有可能的答案依次列出来并测试，答案之间可能没有太大的关系。而动态规划是根据状态转移来尝试获取哪些解。

---

最短路算法(Shortest Path)

最短路算法分为单源最短路和多源最短路。
解决单源最短路的一种方法是 Dijkstra 算法，其时间复杂度是 $O(n\log n + m)$。如果将其应用在多源最短路的话，那么其时间复杂度是 $O(n(n\log n + m))$。

此外，有一个特定的算法用来解决多源最短路，就是Floyd-Warshall (FW)算法，该算法的时间复杂度是 $O(n^3)$。

Floyd-Warshall (FW)

FW算法是一个动态规划的算法，通过逐步加入点来构造子答案从而获取整体最优解的方法。
适用于负数边、有向边的情况。

• 定义：

  • 定义 $d(i,j,k)$：表示点在 $i,j$ 之间使用 ${1,…,k}$ 作为允许使用的潜在中间点的最短路。

    • 例如 $d(2,5,3)$：在仅使用 ${1,2,3}$ 其中的点作为中间点（这些点可以使用也可以不使用，但不能使用其他的点）时点 $2$ 到点 $5$ 的最短路。

  • 定义 $w(i, j)$：表示两个点之间的距离。

    • 如果不连通则等于 $\infty$，即 w(i, j) = inf。
    • 自边等于 $0$，即 w(i, i) = 0。

• 初始化：对于所有的两个点之间：$d(i, j, 0) = w(i, j)$。

• 状态转移方程：考虑当 k = k + 1时，即对于每两对点之间在前 k 个点已经加入好，那么有：
  $$d(i, j, k+1) = \min (d(i, j, k), d(i, k+1, k) + d(k+1, j, k))$$

---

Reference

1. “Big O Notation.” Wikipedia, The Free Encyclopedia, 10 May 2024, en.wikipedia.org/wiki/Big_O_notation. Accessed 19 May 2024.
2. “Recurrence Relation.” Wikipedia, The Free Encyclopedia, 8 April 2024, en.wikipedia.org/wiki/Recurrence_relation. Accessed 20 May 2024.
3. “Master Theorem (Analysis of Algorithms).” Wikipedia, The Free Encyclopedia, 10 May 2024, en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms). Accessed 22 May 2024.
4. “Quicksort.” Wikipedia, The Free Encyclopedia, 12 May 2024, en.wikipedia.org/wiki/Quicksort. Accessed 21 May 2024.