引言
本课程旨在围绕各类数据结构的设计与实现，揭示其中的规律原理与方法技巧；同时针对算法设计及其性能分析，使学生了解并掌握主要的套路与手段。本文将讲解数据结构入门的一些基本概念。
计算
计算是数据结构的直接研究对象和内容，同时也是最终的研究目的和目标。具体说来，我们需要研究计算过程中所蕴含的本质的内在规律，也需要总结和挖掘出其中一般性的方法以及典型的技巧。最终所有这些需要服务于我们的研究目标，也就是实现有效和高效的计算，同时也需要在资源的消耗方面做到足够的低廉。推而广之，计算也可以看作是整个计算机科学的研究对象内容和目的。
Computer science should be called computing science, for the same reason why surgery is not called knife science.
– E.Dijkstra
所谓的计算机科学，更准确的说应该称作计算科学。他在强调计算机只是一个工具和手段，而计算才是我们不应忘记的最终的研究目的和目标。
绳索计算机
输入：任给直线l及其上一点A
输出：经过A做l的一条垂线
- 算法（2000 B.C. 古埃及人）
取12段等长的绳索，首尾联接成环
从A点起，将4段绳索沿l伸直并固定于B
沿另一方向找到第3段绳索的终点C，移动点C，将剩余的3+5段绳索伸直
可以很容易的看出，12段绳索最终构成了一个勾三股四弦五的直角三角形，垂线也就显而易见了。而在这个过程中，12段绳索扮演的角色就是计算机。
尺规计算机及其算法
任给平面上线段AB（输入），将其三等分（输出）
- 算法：
从A发出一条与AB不重合的射线p
在p上取AC’ = C’D’ = D’B’
联接B’B
经D’做B’B的平行线，交AB于D
经C’做B’B的平行线，交AB于C
算法
计算 = 信息处理
借助某种工具，遵照一定规则，以明确而机械的形式进行
计算模型 = 计算机 = 信息处理工具
所谓算法，即特定计算模型下，旨在解决特定问题的指令序列
- 输入 待处理的信息（问题）
- 输出 经处理的信息（答案）
- 正确性 的确可以解决指定的问题
- 确定性 任一算法都可以描述为一个由基本操作组成的序列
- 可行性 每一基本操作都可实现，且在常数时间内完成
- 有穷性 对于任何输入，经过有穷次基本操作，都可以得到输出
对于可行性，宋丹丹和赵本山有一个很著名的小品《钟点工》，里面有一个脑筋急转弯是“如何把大象装到冰箱里去？”。最后她给出了三个步骤：
- 把冰箱门打开
- 把大象赶到冰箱里去
- 关上冰箱门
表面上看上面的过程已经构成了一个算法，因为它确实可以描述出来而且说的比较清楚。但是这里有一个致命的点，也就是这个小品的笑点所在，就是实际上它其中的动作有一条是不能兑现的：把大象赶到冰箱里去。所以这种算法是没有任何意义的，因为它是不可行的。
有穷性
举例：
$Hailstone(42)={42,21,64,32…，1}$
- 根据上面的表达式，我们可以写出如下的伪代码：
int hailstone(int n) |
再次举例：
$Hailstone(7)={7,22,11,34,17,52,26,13,40,20,10,5,16…，1}$
$Hailstone(27)={27,82,41,124,62,31,94,47,142,71,214,107…，1}$
观察比较这几个列举的序列可以发现，变化规律不明显，序列的长度和输入本身没有必然的关系，呈现出非常强的随机性。我们再次回到之前写的伪代码，重新思考一下，这个序列是否满足有穷性。这不取决于程序，而是取决于序列本身： $对于任意的n，总有|Hailstone|<\infty$
而遗憾的是，到目前为止这个问题还没有结论，也就是说我们既不能证明对于任何的n序列必然都是有穷的，也没有找到一个反例。回到伪代码，我们这个看似非常正确而又简洁的程序未必是一个算法，也就是说，程序不等于算法。回忆在刚开始学习程序语言的时候，我们会经常遇到死循环或者栈溢出的情况，机器会非法退出。而死循环关联着有穷性的概念，需要我们特别留意。
好算法
正确：符合语法，能够编译、链接
能够正确处理简单的、大规模的、一般性的、退化的、任意合法的输入
健壮：能辨别不合法的输入并做适当处理，而不致非正常退出
可读：结构化 + 准确命名 + 注释 + …
然而上面这些固然也重要，但还不是最最重要的：
- 效率：速度尽可能快；存储空间尽可能少
Algorithms + Data Structures = Programs
(Algorithms + Data Structures) x Efficiency = Computation
计算模型
之前的算法与数据结构也可以简写为DSA。显然，不同的DSA的性能有好坏优劣之分，这种好坏和优劣完全是从它的效率而言的。然而“好坏”、“优劣”也只是定性的判断，我们需要定量的度量来分析。
性能测度
To measure is to know.
If you can not measure it,
you can not improve it.
– Lord Kelvin
如果科学的使命是去了解这个世界，是去理解这个世界的规律，那么最终的形式往往是体现为对世界或是自然界的有效测量或者测度，算法也是一样。
- 引入理想、统一、分层次的尺度
- 运用该尺度，以测量DSA的性能
问题规模
- 正确性：算法功能与问题要求一致？数学证明？
- 成本：运行时间 + 所需存储空间 如何度量？如何比较？
首先要证明DSA是正确的，过程中许多工具和方法都不是那么一目了然。然而在实际开发中，我们更关注成本（时间成本+空间成本）。通常而言，我们忽略
考察：$T_A(P)=$ 算法A求解问题实例P的计算成本
意义不大，毕竟可能出现的问题实例太多
如何归纳概括？划分等价类
观察：问题实例的规模，往往是决定计算成本的主要因素
通常而言，规模接近，计算成本也接近；规模扩大，计算成本亦上升。
最坏情况
经过刚才等价类的划分，我们可以对定义进行改写：令$T_A(n)=$ 用算法A求解某一问题规模为n的实例，所需的计算成本。讨论特定算法A（及其对应的问题）时，简记为$T(n)$
- 观察：同一问题等规模的不同实例，计算成本不尽相同，甚至有实质差别
例如：
在平面上的n个点中，找到所成三角形面积最小的三个点
以蛮力算法为例，最坏情况下需列举所有$C_n^3$种组合
但如果运气比较好，三点共线的情况可以直接结束，面积为0
同样的例子还有Hailstone。显然我们不能寄托于最好的情况下，而是应该更多的关注一个算法的最坏情况。稳妥起见，取$T(n)=max{T(P)||P| = n}$
在规模同为n的所有实例中，只关注最坏（成本最高）者：在所有规模为n的问题实例中，将它们的计算成本进行总体的比较，并取出其中的最大值。
理想模型
当同一个问题拥有多个算法的时候，如何评价其优劣？
实验统计
最直接的方法，但足以准确反映算法的真正效率？是骡子是马拉出来溜溜，谁用的时间越短、谁用的资源越少，谁就越优。
这种想当然的想法不足够，因为测试总是不充分的。不同的算法可能更适应于不同规模/类型的输入；同一算法，可能由不同程序员、用不同程序语言、经不同编译器实现、运行于不同的体系结构、操作系统……如果测试在问题实例的规模以及类型等等方面覆盖的不够全面、不具有充分的代表性的话，那么这种测试本身就是带有偏见的，它的结论也就难以让人信服。
为了给出客观的评价，需要抽象出一个理想的平台或模型，不再依赖于上述种种具体的因素，从而直接而准确地描述、测量并评价算法。
图灵机
Tape依次均匀地划分为单元格，各注有某一字符，默认为’#’Alphabet字符的种类有限Head总是对准某一单元格，并可读取和改写其中的字符。每经过一个节拍，可转向左侧或右侧的邻格StateTM（Turing Machine）总是处于有限种状态中的某一种。每经过一个节拍，可（按照规则）转向另一种状态Transition Function：（q，c；d，L/R，p）若当前状态为
q且当前字符为c，则将当前字符改写为d；转向左侧/右侧的邻格；转入p状态；一旦转入特定的状态h，则停机
图灵机实例
功能：将二进制非负整数加一
算法：全’1’的后缀反转为全’0’，原最低位的’0’或’#’翻转为’1’
根据前面的分析，不难写出相应的指令：
(<, 1, 0, L, <) //左行 1->0 |
RAM模型
在可计算的意义上讲，RAM（Random Access Machine）和图灵机是完全对等的。
寄存器顺序编号，总数没有限制
R[0]，R[1]，R[2]，R[3]，...
每一基本操作仅需常数时间
R[i] <- c //常数赋值语句
R[i] <- R[j] //数值复制
R[i] <- R[R[j]] //间接取址
R[i] <- R[j] + R[k] //基本运算
IF R[i] > 0 GOTO 1 //条件判断跳转终止
与TM模型一样，RAM模型也是一般计算工具的简化与抽象，使我们可以独立于具体的平台，对算法的效率做出可信的比较与评判。
在这些模型中，算法的运行时间关联于算法需要执行的基本操作次数，$T(n)$ = 算法为求解规模为n的问题，所需执行的基本操作次数。
RAM实例
功能：向下取整的算法
$\lfloor x \rfloor = max{x|dx <= c}=max{x|dx < 1 + c}$ $(0 <= c，0 < d)$
算法：反复地从 $R[0] = 1 + c$ 中减去 $R[1]=d$ 统计在下溢之前，所做减法的次数x
R[3] <- 1 //increment |
按照算法我们最终可以得到下表：
执行过程可以记录为一张表，表的行数即是所执行基本指令的总条数，能够客观度量算法的执行时间。
图灵机、RAM等模型为度量算法性能提供了准确的尺度。
大O记号
如果前面的计算模型是一把公正的直尺，那么大O记号就是直尺上的刻度。我们不需要刻意强调刻度的精细程度，只需要在定性和定量之间达到一个适度的折中，使得我们可以用更短的时间更迅速地抓住DSA性能的要害和主要方面。
Mathematics is more in need
of good notation than
of new theorems.
– Alan Turing
记号的作用很类似于陶渊明的诗：
好读书不求甚解
每有会意，便欣然忘食
– 陶渊明
主流长远
这里的不求甚解并不是说不去求解，而是说不要过多的拘泥于问题的细节和一些琐碎的部分。回到原先的问题：随着问题规模的增长，计算成本如何增长？注意这里关心足够大的问题，注重考查成本的增长趋势。
渐进分析（Asymptotic analysis）：
在问题问题规模足够大后，计算成本如何增长？当问题规模足够大之后，对于规模为n输入，算法：
- 需执行的基本操作次数：$T(n)=?$
- 需占用的存储单元数：$S(n)=?$
如果用一张图来表示，也就是用横轴表示问题的规模、纵轴表示相应的计算成本，那么数据结构和算法具体的任何一个组合，都可以得到这样一条曲线：
我们关心的并不是这条曲线局部的、细微的、包括暂时的一些趋势，而是看它主要的、长远的变化趋势。
大O记号
大O记号（big-O notation）
$T(n)=O(f(n))$ 充要条件是 ${\exists}c > 0$，当$n>>2$后，有$T(n)<cf(n)$
$\sqrt{5n \cdot [3n \cdot (n + 2) + 4] + 6} < \sqrt{5n \cdot [6n^2 + 4] + 6}<\sqrt{35n^2 + 6}<6 \cdot n^1.5 = o(n^1.5)$
与$T(n)$相比，$f(n)$更为简洁，但依然反映出前者的增长趋势。
- 常系数可忽略：$O(f(n))=O(cf(n))$
- 低次项可忽略：$O(n^a+n^b)=O(n^a)，a>b>0$
可以认为大O记号是对计算成本的悲观估计。
渐进分析：其他记号
$T(n)=\Omega(f(n)):\exists c > 0$，当$n >> 2$ 后，有$T(n)>cf(n)$
$T(n)=\theta(f(n)):\exists c_1 > c_2 > 0$，当 $n >> 2$ 后，有 $c_1 \cdot f(n)>T(n)>c_2 \cdot f(n)$
高效解
在大O记号的直尺上，有许多相应的刻度:
- 常数（constant function）
包括常数、较大的常数以及按照通常的四则混合运算经过运算以后得到的常数。
$2 = 2013 = 2013 \times 2013 = 2013^{2013} =O(1)$。
这类算法的效率最高。
如果一段代码不含转向（循环、调用、递归等），必顺序执行，即是$O(1)$。当然包含循环、分支转向、递归调用的代码段仍然可能是$O(1)$，具体情况应具体分析。
- 对数 $O(\log^cn)$
$\ln n$ | $\lg n$ | $ \log_{100}n$ | $ \log_{2013}n$
常底数无所谓
在这里我们往往不再标明具体的底数，因为在底数为常数的情况下，具体是多少是无所谓的。
$\forall a，b > 0，\log_an =log_ab \cdot \log_bn = \theta(log_bn)$
常数次幂无所谓
$\forall c >0，\log n^c = c \cdot logn = \theta(logn)$
多项式形式（ploy-log function）
参照大O处理方法，把低次项和常系数的项都忽略掉从而得到一个简明的多项形式。
$123*\log^{321}n + log^{105}(n^2-n+1)=\theta(log^{321}n)$
这类算法非常有效，复杂度无线接近于常数。$\forall c > 0,logn=O(n^c)$
有效解
多项式（polynomial function）复杂度
$100n + 200 = O(n)$
$(100n - 500)(20n^2 -300n +2013) = O(n \times n^2)$$(2013n^2 - 20)/(1990n - 1)=O(n^2/n)=O(n)$
一般的：$a_kn^k + a_{k-1}n^{k-1} + … + a_1n + a_0 = O(n^k)，a_k >0$
线性（linear function）：所有$O（n）$类函数
幂：$[(n^2013-24n^2009)^{1/3}+512n^567-1978n^123]^{1/11}=O(n^{61})$
这类算法的效率通常认为已可令人满意，凡多项式复杂度，均视为可解问题。
难解
- 指数（exponential function）复杂度：$T(n) = a^n$
$\forall c > 1，n^c=O(2^n)$
$n^{100} = O(1.0000001^n) = O(2^n)$
$1.0000001^n = \Omega(n^{1000})$
这类算法的计算成本增长极快，通常被认为不可接受。从$O(n^c)$到$O(2^n)$，是从有效算法到无效算法的分水岭。
很多问题的$O(2^n)$算法往往显而易见，然而设计出$O(n^c)$算法却极其不易，伸直有时注定只能是徒劳无功。
2-Subset
问题描述
S包含n个正整数，$\Sigma S = 2m$，S是否有子集T，满足$\Sigma T = m$
选举人制
各州议会选出的选举人团投票，而不是由选民直接投票。
50个州加1个特区，共538票。获得270张选举人票，即可当选。
若共有两位候选人，是否可能恰好各得269票？也就是说是否有一个办法能把所有的州按照选举人分成两部分，使得它们各自所积累起来的选举人票恰好是各自一半？
直觉算法：逐一枚举S的每一子集，并统计其中元素的总和
$|2^s|=2^{|s|}=2^n$，代表直觉算法需要迭代$2^n$轮，并（在最坏情况下）至少需要花费这么多的时间–不甚理想。
定理：2-Subset is NP-complete
就目前的计算模型而言，不存在可在多项式时间内回答此问题的算法 – 就此意义而言，上述的直觉算法已属最优。
算法分析
He calculated just as men breathe,
as eagles sustain themselves in the air.
– Francois Arago
算法分析的主要任务包括两个方面的内容：正确性（不变性 x 单调性）+ 复杂度
C++等高级语言的基本指令，均等效于常数条RAM的基本指令；在渐进的意义上，二者大体相当：
- 分支转向：
goto算法的灵魂；出于结构化考虑被隐藏 - 迭代循环：
for()、while()、… 本质都是if+goto - 调用 + 递归（自我调用）：本质上也是
goto
复杂度分析的主要方法：
- 迭代：级数求和
- 递归：递归跟踪 + 递推方程
- 推测 + 验证
级数
算术级数：与末项平方同阶
$T(n)=1+2+…+n=n(n+1)/2=O(n^2)$
幂方级数：比幂次高出一阶：$\Sigma^n_{k=0} \approx \int^n_0x^{d+1}dx=\frac {1}{d+1}x^{d+1}|^n_0=O(n^{d+1})$
$T_2(n) = 1^2 + 2^2 + 3^2 + … + n^2 = n(n + 1)(2n + 1)/6=O(n^3)$
$T_3(n)=1^3 + 2^3 +3^3 + … + n^3 = n^2(n + 1)^2/4 = O(n^4)$
$T_4(n)=1^4 + 2^4 + 3^4 + … + n^4 = n(n+1)(2n+1)(3n^2+3n-1)/30=O(n^5)$
…
几何级数（$a>1$）：与末项同阶
$T_a(n)=a^0+a^1+…+a^n=(a^{n+1}-1)/(a-1)=O(a^n)$
$1+2+4+…+2^n=a^{n+1}-1=O(2^n+1)=O(2^n)$
收敛级数
$1/1/2 + 1/2/3 + 1/3/4 + … +1/(n-1)/n=1-1/n=O(1)$
$1 + 1/2^2 + … + 1/n^2 < 1 + 1/2^2 + … = \pi^2/6 = O(1)$
$1/3 + 1/7 +1/8 +1/15 + 1/24 + 1/26 + 1/31 + 1/35 + … = 1 = O(1)$
循环
for(int i = 0;i < n;i++) |
算术级数：$\Sigma^{n-1}_{i=0}n=n+n+…+n=n*n=O(n^2)$
我们可以用一个二维矩形来表示。i外循环的控制变量，j内循环的控制变量构成对应的两个维度。矩形中的每一个点都对应于内部这个$O(1)$的操作的一次执行，而整个二重循环其实就等效于这个矩形被填充的过程。因此我们可以建立联系，这段代码的时间复杂度就等于矩形的面积。
for(int i = 0;i < n;i++) |
算术级数：$\Sigma^{n-1}_{i=0}i=0+1+…+(n-1)=\frac{n(n-1)}{2}=O(n^2)$
该过程依然可以表述为一个二维图形。外循环控制变量i依然是从0一直变化到n，而内循环的控制变量j则呈一个算术级数，不断线性递增的规律。这段代码的执行时间应该等于这个被填充的三角形总体的面积。
for(int i = 0;i < n;i++) |
for(int i = 0;i < n;i <<= 1) |
几何级数：
$1 + 2 + 4 + … + 2 ^ {\lfloor{log_2(n-1)}\rfloor}=\Sigma^{\lfloor{log_2(n-1)}\rfloor}_{k=0}2^k (k = log_2n) = 2^{\lceil log_2n \rceil}-1=O(n)$
实例：非极端元素+起泡排序
非极端元素
问题：给定整数子集S，$|S|=n\geq3$ 找出元素$a\in S，a \neq max(S)$且$a \neq min(S)$
算法：
- 从S中任取三个元素${x,y,z}$
- 确定并排除其中的最小、最大者（不妨设$x = max{x,y,z},y=min{x,y,z}$）
- 输出剩下的元素$z$
无论输入规模n多大，上述算法需要的执行时间都不变 $T(n)=O(1)=\Omega(1)=\Theta(1)$
起泡排序
问题：给定n个整数，将它们按（非降）序排序
观察：有序/无序序列中，任意/总有一对相邻元素顺序/逆序
扫描交换：依次比较每一对相邻元素，如有必要，交换之。若整趟扫描都没有进行交换，则排序完成；否则再做一趟交换。
void bubblesort(int A[],int n) |
正确性的方法
该算法必然会结束？至多需要迭代多少趟？
- 不变性：经过k轮扫描交换后，最大的k个元素必然就位
- 单调性：经过k轮扫描交换后，问题规模缩减至n-k
- 正确性：经过至多n趟扫描后，算法必然终止，且能给出正确解答
封底估算
考察对全国人口普查数据的排序 $n=10^9….$
| 硬件/算法 | 普通PC | 天河1A |
|---|---|---|
| Bubblesort | 30 yr | 20 min |
| Mergesort | 30 sec | 0.03s |
通过硬件的改进，我们可以从30年改进为20分钟；而算法上的改进我们可以从30年改进为30秒，效率上是巨大的提升。
迭代与递归
在已经能够逐步了解和评判数据结构和算法的性能优劣之后，我们要慢慢学会如何设计一个高效的DSA。
The control of a large force is
the same principle as
the control of a few men:
it is merely a question of
dividing up their numbers.
- 问题：计算任意n个整数之和
- 实现：逐一取出每个元素，累加之
int SumI(int A[],int n) |
无论A[ ]内容如何，都有：
$T(n)=1+n*1+1=n+2=O(n)=\Omega(n)=\Theta(n)$
减而治之
【Decrease-and-conquer】：为求解一个大规模问题，可以将其划分为两个子问题：其一平凡，另一规模缩减，分别求解子问题，由子问题的解，得到愿问题的解。
递归跟踪
对于n个数求解这样一个问题，我们将它分解为一个规模缩小了一个单元的问题，另外剩下的一个问题本身是一个平凡的问题，可以直接求解得到。
sum(int A[],int n) |
递归跟踪（recursion trace）分析
检查每个递归实例
累积所需时间（调用语句本身，计入对应的子实例）
main() --> sum(A,n) --> sum(A,n-1) --> sum(A,n-2) --recursive calls--> sum(A,2) --> sum(A,1) --> sum(A,0) |
本例中，单个递归实例自身只需$O(1)$时间，$T(n)=O(1)*(n+1)=O(n)$
- 递归跟踪：直观形象，仅适用于简明的递归模式
- 递推方程：间接抽象，更适用于复杂的递归模式
递推方程
从递推的角度看，为求解sum（A，n），需：
递归求解规模为n-1的问题sum(A,n-1) //T(n-1) |
递推方程：
T(n) = T(n-1)+O(1) //recurrence
T(0) = O(1) //base求解：
T(n) - n = T(n-1) - (n-1) = ...
= T(2) - 2
= T(1) - 1
= T(0)
T(n) = O(1) + n = O(n)
数组倒置
任给数组A，将其前后颠倒
统一接口
void reverse(int* A,int lo,int hi);
递归版
if(lo < hi) //问题规模的奇偶性不变，需要两个递归基
{ swap(A[lo],A[hi]); reverse(A,lo + 1,hi - 1); }
else return; //base case通过代码可以知道第一次递归的问题规模由
n变为了n-2与lo、hi，之后的递归以此类推。迭代原始版
if(lo < hi)
{ swap(A[lo],A[hi]); lo++; hi--; goto next; }迭代精简版
while(lo < hi) swap(A[lo++],A[hi--]);
分而治之
【Divide-and-conquer】：为求解一个大规模的问题，可以将其划分为若干（通常是两个）子问题，规模大体相当；分别求解子问题；由子问题的解，得到愿问题的解。
二分递归：数组求和
sum(int A[],int lo,int hi) //入口形式为sum(A,0,n-1) |
递归跟踪
以某个具体数值（0～7）为例，画出递归实例彼此调用的关系图：
可以发现，0到7的求和问题被化简为0到3的求和问题以及4到7的求和问题；后者又进而被划分为4到5以及6到7之间的求和问题……直到最后变成递归基的形式，也就是说lo分别等于hi。
统计所有递归实例所需要的时间总和：如果把递归调用本身的语句去掉，里面并不包括任何形式的隐式的或者是显式的迭代。换而言之，每一个递归实例无论有效区间的长短，都是只需$O(1)$时间：
$\begin{equation}\begin{split}
T(n)= O(1) \cdot(2^0 + 2^1 + 2^2 + … + 2^{logn})=O(1) \cdot (2^{logn+1} - 1)=O(n)
\end{split}\end{equation}$
从递推的角度看，为求解sum（A，lo，hi），需：
递归求解sum(A,lo,mi)和sum(A,mi + 1,hi) //2*T(n/2) |
递推关系
$T(n)=2*T(n/2)+O(1)$
$T(1)=O(1)$
二分递归：Max2
从数组区间$A[lo,hi)$中找出最大的两个整数$A[x1]$和$A[x2]$
Konstantinos Pappas