MIT 6006 Lecture 3——插入排序，归并排序

我们依赖秩序，而反感混乱

为什么要排序

有许多直接的应用需要我们进行排序，例如按照人名首字母的顺序对班上的人进行排序；字典的索引需要排序等。此外许多问题通过排序可以得到化简，例如寻找中位数的问题、文件压缩以及视频渲染等。

插入排序

原理及算法

插入排序的算法如下：

For i = 1,2,3,...,n
    insert A[i] into sorted array A[0:i-1] by pair swaps down to the correct position

算法的可视化过程如下所示：

复杂度分析

时间复杂度

这个算法可以分为：

• 移动key：一共移动了$n$步，复杂度为$\Theta(n)$
• 交换相邻元素：每一步最大可能比较并交换$n$次，复杂度为$\Theta(n)$

由于底层操作的缘由，比较操作相对于交换来说，更加耗时，所以一个改进就是降低比较的次数，我们可以对已经比较好的部分$A[0:i-1]$进行二分查找，从而将比较操作的时间复杂度降低为$\Theta(\log i)$，不过由于需要整体移动，所以总时间复杂度还是没有变化，只是比较次数变少了。改进后的时间复杂度为：

• $\Theta(n\log n)$次比较
• $\Theta(n^2)$次交换

空间复杂度

插入排序的空间复杂度为$\Theta(1)$，不需要额外的空间

归并排序

基本原理

归并排序的思想是先将长度为$n$的大数组$A$转换为长度为$n/2$的小数组$L$和$R$，然后分别对其进行排序，之后再将数组进行合并，最后得到排序后的数组$A’$

所谓归并，就是将两个排序好的数组作为输入。下面结合具体例子对归并过程进行讲解

给定两个已经排序的数组l'和R’，两个指针分别指向L'和R'的最小元素位置，每次选择两个数组中最小的数，然后移动指针
L'      R'          L'       R'
----------          -----------
20      12   --->   20       12
13      11          13       11
 7       9           7        9<-p2
 2<-p1   1<-p2       2<-p1    1

最后合并的结果为：1 2 7 9 11 12 13 20

归并的复杂度为$\Theta(n)$。

复杂度分析

时间复杂度

根据归并排序的原理，我们可以写出归并排序的时间复杂度为：

$$T(n) = C_1+2T(n/2)+C\cdot n$$

其中$C_1$为分割数组的时间复杂度，$C\cdot n$为归并数组的复杂度，$C$和$C_1$是一个常数，$T(n/2)$为递归过程时间复杂度。下面我们构造一个二叉树对这个过程进行分析：

这个递归树有$n$个树叶，每一层和都为$C\cdot n$，叶子节点值都为$C$，这个满二叉树层数为$1+\log n$，故

$$T(n) = (1+\log n)\times C\cdot n=\Theta(n\lg n)$$

空间复杂度

空间复杂度为$\Theta(n)$，因为需要有拆分数组的过程，为了改进这个算法，人们提出了原地归并排序算法

两种排序方法的比较

归并排序相对于插入排序更快，但是需要额外的空间以及拷贝动作。在python中，归并排序时间为$(2.2n\lg n)\mu s$，而插入排序时间为$0.2n^2$

复杂度计算

本节一个重要的点就是复杂度的计算，仿照归并排序的复杂度分析过程，我们这里给出一道例题：

求$T(n)=2T(n/2)+C\cdot n$的时间复杂度

构造二叉树如下：

树深度为$\lg n+1$，最后一层叶子节点数为$n$，值为$C$，故总时间复杂度为：

$$T(n)=Cn^2+Cn^2/2+Cn^2/4+\cdots+Cn\le2Cn^2$$

作业

分形渲染

题目

我们首先来直观了解一下分形问题：

上面这个分型就是经典的$Koch$雪花，一开始有一个初始三角形，然后三角形的边上会长出新的三角形，由于CPU和GPU精度限制，分形的过程是有限的，令$n$为分形的深度（或者细节，Level of detail, LoD），我们规定：当$n=0$时，为初始三角形。分形的算法可以由如下伪代码表示：

${\rm S{\small NOW}{\small FLAKE}}(n)$

​ $e_1,e_2,e_3=\textrm{edges of an equilateral triangle with side length 1}$

​ ${\rm S{\small NOW}{\small FLAKE}}-{\rm E{\small DGE}}(e_1,n)$

​ ${\rm S{\small NOW}{\small FLAKE}}-{\rm E{\small DGE}}(e_2,n)$

​ ${\rm S{\small NOW}{\small FLAKE}}-{\rm E{\small DGE}}(e_3,n)$

${\rm S{\small NOW}{\small FLAKE}}-{\rm E{\small DGE}}(e,n)$

​ $\mathbf{if}\ n==0$

​ $e\ \textrm{is an edge on the snowflake}$

​ $\mathbf{else}$

​ $e_1,e_2,e_3=\textrm{split edge in 3 equal parts}$

​ ${\rm S{\small NOW}{\small FLAKE}}-{\rm E{\small DGE}}(e_1,n-1)$

​ $f_2,g_2=\textrm{edges of an equilateral triangle whose 3rd edge is }e_2$

​ $\textrm{pointing outside the snowflake }\Delta(f_2,g_2,e_2)\textrm{ is a triangle on the snowflake’s surface}$

​ ${\rm S{\small NOW}{\small FLAKE}}-{\rm E{\small DGE}}(f_2,n-1)$

​ ${\rm S{\small NOW}{\small FLAKE}}-{\rm E{\small DGE}}(g_2,n-1)$

​ ${\rm S{\small NOW}{\small FLAKE}}-{\rm E{\small DGE}}(e_3,n-1)$

这里我们提供了四种方法实现SnowflakeEdge，我们需要判定这些方法的时间复杂度。在${\rm S{\small NOW}{\small FLAKE}}(n)$函数中，我们实际上是构建了三棵树，构成了一个森林，但我们出于统一的考虑，将这个森林视作一个树。

第一组

1) 根据上面的SnowflakeEdge算法，渲染一个深度为$n$的雪花，其迭代树深度为多少？

上面的算法时间复杂度可以写为：

$$\begin{equation} \begin{aligned} T(n)&=4T(n-1)+\Theta(1)\\ T(0)&=\Theta(1) \end{aligned} \end{equation}$$

绘制其递归树，得到一个深度为$n$的四叉树，层数为$n+1$。

2) 求第$i$层（$0\le i\le n$）节点数$f(i)$

我们先考虑一棵树，再推广到整个森林：第$i$层有$4^i$个节点，我们采用数学归纳法进行证明：当$i=0$时，有一个节点，显然成立；假设算法在第$j$层（$0\le j< i$）均成立，那么第$j$层有$4^j$个节点，当$j=i-1$时，该层有$4^{i-1}$个节点，现证明当$j=i$时算法依然成立，根据递归过程可知，该递归树每个节点度为4，那么下一层节点数为当前层的4倍，则第$i$层节点数$f(i)=4f(i-1)=4\times 4^{i-1}=4^{i}$。

由于森林中有三棵相同的树，所以最终第$i$层节点数为$3\cdot4^i$。

3) 在递归树的第$i$层，渲染一个节点的时间复杂度是多少？其中$0\le i<n$。

根据算法的时间复杂度：

$$\begin{equation} \begin{aligned} T(n)&=4T(n-1)+\Theta(1)\\ &=4(4T(n-2)+\Theta(1))+\Theta(1)\\ &=\cdots\\ &=4^{i+1}T(n-i-1)+4^{i}\Theta(1) \end{aligned} \end{equation}$$

对于一颗递归树，渲染第$i$层的时间复杂度为$\Theta(4^{i})$。而第$i$层节点数为$4^i$，故渲染第$i$层一个节点的时间复杂度为$\Theta(1)$。

4) 求第$i$层的时间复杂度

根据2)和3)可知时间复杂度为$\Theta(4^i)$。

5) 求总时间复杂度

因为递归树第$i$层时间复杂度为$\Theta(4^i)$，故总时间复杂度$T(n)=\Theta(4^0)+\Theta(4^1)+\cdots+\Theta(4^n)$，根据极限定理可知，总时间复杂度$T(n)$满足$\Theta(4^n)\le T(n)\le \Theta(4^{n+1})$。所以时间复杂度为$T(n)=\Theta(4^n)$。

第二组

为了提高分形效率，我们采用GPU对程序进行加速，将雪花图案视为一个闭合的直线路径，通过CPU计算路径的端点，最后将深度为$n$的路径点交给GPU进行渲染。当$n=0$时，需要绘制三条边，当LoD增加后，每增加一层，那么原先的每一条边会被更新为4条边。请回答如下问题：

1) 根据硬件加速的SnowflakeEdge算法，渲染一个深度为$n$的雪花，其迭代树深度为多少？

硬件加速的时间复杂度为：

$$\begin{equation}\begin{aligned}T(n)&=4T(n-1)+\Theta(1)\\T(0)&=\Theta(1)\end{aligned}\end{equation}$$

同样也是一个四叉树，深度为$n$。第$i$层节点数为$3\cdot4^i$，这里一个节点代表构造一条边，

2) 渲染第$i$层一个节点的时间复杂度为？

当$0\le i<n$时，只构造边但是不渲染，故时间复杂度为0，而当$i=n$时，进行一次渲染，渲染一条边的时间复杂度为$\Theta(1)$.

3) 渲染第$i$层的所有节点时间复杂度为？

由于中间层不进行渲染，因此时间复杂度为0，最后一层渲染时时间复杂度为$\Theta(4^n)$，总的时间复杂度为$\Theta(4^n)$。

所以硬件加速省略了中间的渲染过程，最后待分形图案的点完成后，统一进行渲染，节约了渲染时间，但是构造分形的复杂度没有降低。

第三组

继续改进算法，我们依旧将雪花图案保存为闭合直线路径，但是我们不使用硬件加速，而是根据起点和端点，对线条进行绘制，绘制时间是线性的，即如果线长为1，那么绘制时间为1，如果线长为$1/3$，相应地绘制时间也会变为原来的三分之一。渲染依旧是在最后一步进行，回答下面的问题：

1) 求Lod为$n$时树的深度以及第$i$层的节点数

这个树是一个四叉树，高度为$n$，第$i$层节点数为$3\times4^i$。

2) 渲染第$i$层的一个节点时间为？

第$i$层不渲染，所以时间为0

3) 渲染第$n$层的一个节点和所有节点时间为？

第$n$层节点数为$3\times4^n$，而渲染一个节点（即一条边）的过程和边长有关，第$n$层边长为$(1/3)^n$，所以渲染一个节点的时间为$(1/3)^n$，那么总的时间复杂度为$(\frac{4}{3})^n$。

4) 总渲染时间为？

虽然每一层不用渲染了，但是依然需要做保存端点的操作，因此每一层每个节点时间复杂度为$\Theta(1)$，最后一层渲染的总时间复杂度为$(\frac{4}{3})^n$。所以总时间为：

$$T(n)=\sum_{i=0}^{n-1}4^i+(\frac{4}{3})^n$$

占主要部分的是前半部分，所以时间复杂度为$\Theta(4^n)$，不过如果只看渲染时间，那么就是$(\frac{4}{3})^n$。

第四组

不使用硬件加速渲染3d的雪花图，CPU保存一系列的三角形，渲染时间和三角形面积成正比。如果边长为1，那么面积为$\sqrt{3}/4$；如果边长为1/2，那么面积为$\sqrt{3}/16$。是指数关系。首先，不变的是树的高度和每层节点数，由于最后渲染，所以第$i$层（$0\le i<n$）的渲染时间为0，最后一层节点数为$3\times 4^n$，第$n$层边长为$(1/3)^n$，出于简单考虑，令面积为$(1/3)^{2n}$，所以总时间为$(\frac{4}{9})^n$，即$\Theta(1)$。

更正

这里有一个理解错误，渲染形状和渲染线段是不一样的，渲染形状不能只看最后一层的顶点和线段，要将每一层三角形的形状都考虑进来，因此每一层都要考虑，第$i$层边长为$(1/3)^{i+1}$，面积为$(1/9)^{i+1}$，所以每一层的渲染时间为$3\times 4^i\times (1/9)^{i+1}$，总时间为：

$$T(n)=\sum_{i=0}^{n}3\cdot\frac{1}{9}\cdot (\frac{4}{9})^i=\Theta(1)$$

参考文献

---

1. 第三课视频 ↩
2. 第三课作业 ↩