时间：20200806

署名：我的偶像是木子

引用：《数据结构》邓俊辉 · 编著

版本：version 0.2

简介：个人学习笔记，infoQ不好排版，后续考虑发word版本吧，希望对想系统学习数据结构和算法的人能有一定的帮助，文中有些数据公式和符号省略掉了（不知道怎么插入），如需阅读，建议从头到尾，嗯就说这么多把，尽量日更（不现实）



第一篇：从计算模型到渐进分析法



计算机是人类从事计算的工具，是抽象计算模型的具体物化，现代计算机就是基于图灵模型



计算机科学的核心在于研究计算方法与计算过程的规律，而不仅仅是作为计算工具，计算才是目的和目标，

因此计算机科学又是计算科学

• 计算作为对象（计算方法）：需了解内在规律，一般性方法，典型的技巧

• 计算作为目标（计算过程）：需有效且高效，且资源消耗低廉



如果把计算的过程抽象为一个信息处理的过程，那么首先需要借助某种工具，并遵照一定规则，最后必须能够以明确而机械的一系列简单基本的操作形式而构成一个序列或者说是过程



作为一个计算过程，也可以称为算法，所谓算法可以看作是指基于特定的计算模型下，解决某一信息处理问题而设计的一个指令序列



一个算法应该具备以下要素：

• 输入与输出：求解问题的描述，以及经计算和处理之后得到的问题答案

• 确定性与可行性：算法可以描述为由若干条语义明确的基本操作组成的序列，且每一个基本操作在对应的计算模型中均可兑现

• 有穷性：任何算法都应在执行有限次基本操作后终止并给出输出

• 正确性：算法不仅应该会终止，而且所给的输出还应该能够符合问题本身在事先确定的条件

针对有穷性和正确性这两条性质并不好证明，证明算法的有穷性和正确性的一个重要技巧，就是从适当的角度审视整个计算过程，并找出其所具有的某种单调性和不变性



单调性通常指问题的有效规模会随着算法的推进不断递减，而不变性则不仅应在算法初始状态下自然满足，而且应与最终的正确性相呼应，当问题的有效规模缩减到0时，不变性应随机等价于正确性



具体可以参考冒泡算法，看看单调性和不变性应该如何定义和体现？

冒泡排序算法的不变性和单调性可分别概况为：经过k趟扫描交换之后，最大的前k个元素必然就位；经过k趟扫描交换之后，待求解问题的有效性规模将缩减至n-k

由单调性可知，无论如何，至多经过n-1趟扫描交换后，问题的有效规模必将缩减1，而算法的不变性在于，其余n-1个元素在此前n-1步迭代中也已相继就位，因此算法不仅必然停止，而且输出序列必然是整体有序的，其有穷性与正确性由此可证



那什么是好的算法？

• 正确：符合语法，能够编译

• 能够正确处理简单的输入

• 能够正确处理大规模的输入

• 能够正确处理一般性的输入

• 能够正确处理退化的输入

• 能够正确处理任意合法的输入

• 健壮：能辨别不合法的输入并作适当处理，而不会导致非正常退出

• 可读：结构化 + 准确命名 + 注释

• 效率：速度尽可能快，存储空间尽可能少

• 

如果说：算法 + 数据结构 = 程序，但程序未必能有效的进行计算，所以在这个公式的基础上稍加修改：（算法 + 数据结构） * 效率 = 计算



无论是算法的初始输入、中间结果还是最终输出，在计算机都可以以数据的形式表示，对于数据的存储、组织、转移及变换的操作，不同计算模型和平台环境所支持的具体形式各不相同，其执行效率直接影响和决定算法的整体效率



数据结构正是以数据这一信息的表现形式为研究对象，旨在建立支持高效算法的数据信息处理策略、技巧与方法，要做到根据实际应用灵活的设计、实现和选用适当的数据结构，必须首先对算法设计的技巧及相应的数据结构的特性了然于心，因此，有效且高效的计算的前提是算法和数据结构能有机结合，故简称它们为DSA（Data Structure + Algorithm）



不同DSA的性能有好坏优劣之别，这种好坏和优劣完全是从它的效率而言的，在实际中，必须学会定量的来做度量

这里的测度，实际上是算法分析的范畴，所谓的算法分析，主要有两个方面：

• 正确性： 算法功能与问题是否一致？怎么用属性工具进行证明？

• 成本： 运行时间 + 所需存储时间，空间成本可以暂时忽略不计



在算法分析中，最重要的是关注时间成本，那么如果关注一个DSA的时间成本，那么该如何度量？如果度量又涉及到多个DSA，那么又该如何比较？



解决这些问题的思路先从建模开始，首先定义一个数学上的描述：一个名字为A的算法，求解某一个问题的实例P，那么它所需要的计算时间成本就会被记为：TA（P）



如果能够真正获得这样一个度量值，就可以对算法进行比较，但遗憾，纯粹从数学上所做的这样一个定义，其实意义不大，因为同样一个问题可能出现的实例非常多，接近无穷，所以不能把目光注意到这些实例上去，任何一个具体的实例都存在以偏概全的问题，它不可能使我们获得对这个问题所对应的算法有一个总体的认识



如何对这些实例归纳概括？数学上提供了一个常用且非常有效的方法：划分等价类 ，一般来说，需要对任何一个问题的无数实例进行一定的粗略分类，并且就某一类谈它的计算成本



那么怎么分类呢？任何一个问题的计算成本，实际上往往是和问题实例的规模相关联，一般来说还是正相关的，大多数时候这个结论是成立的，并不是说所有的时候都是这样，所以通常来说：

• 规模接近，计算成本也接近

• 规模扩大，计算成本亦上升



经过这样一个等价类划分之后，接下来可以对之前那个数学描述的度量形式进行改写，把原来每一个具体实例的P，变成了笼统而言的一个规模的度量值n，也就是说，可以把某一个算法，在求解规模为n的一大类实例的过程中，它们各自所需要的时间成本为：TA（n），如果暂时把算法固定的话。那么也可以把这个A忽略掉，简记作T（n）



但依然遗憾，这样一个定义还是不能满足实际的需求，不足以支撑分析的需要，为什么？

对于同一问题，即便是规模接近甚至相等的输入实例，计算成本虽然大体是差不多的，但毕竟还是有差异的，甚至会有实质性的差异，比如求解一组数中最小值（n>=0），最好情况可能在第一个数就找到了答案，反之最坏情况可能会在最后一个数才确定



既然如此，又该如何定义T（n）？显然，我们不能把命运寄托在最好的情况下，而应该更多的关注一个算法的最坏情况



如果只关心其中最坏的情况，也就是成本最高的情况，那么T（n）的取值应该是在所有规模为n的问题实例中，将它们的计算成本进行总体的比较，并取出其中最大值，即只关注计算成本最高（最坏）的那一个，这也就是之前所说的最坏情况分析原则且必须要关注的，当然还会关注一些其他的性能，如平均性能、分摊性能等等，但首当其冲的，却是最坏的情况



解决了算法的评价问题之后，接下来需要进一步回答另一个问题：同一问题通常有多种算法，那么如何评判其好坏或是说优劣呢？



一种直观的方法是，通过实验统计，一个个比较，谁所用的时间最短，谁用的资源最小，那么谁就是最优

这种想当然的方法，在实际应用中是不够用的，因为它并不能准确的反应一个算法真正的即全面的效率，这个原因就在于实验统计总是不充分的



不同的算法，各有所长，各有所短，所以如果实验在问题实例的规模以及类型等方面覆盖的不够全面，不具有充用的代表性的话，那么这种测试，本身就是带有偏见的，它的结论也就难以让人信服



再退一步，即使是同一种算法，也可能是由不同的程序员用不同的编程语言，经不同的编译器实现，即便上述因素都是一致的，在不同的体系结构下，不同的操作系统，它所体现出来的性能也可能是有很大的区别，比如硬件的CPU速度，内存和磁盘的速度和容量，以及它们之间的带宽等，还有包括操作系统在不同的时刻，对不同的计算资源分配的当时状态不同等等，这些因素都不可能通过少数次、有限次的实验统计就足以覆盖



综合起来，能够可行的方法只有一条，为了给出客观的评判，需要抽象出一种理想的计算平台或者说是模型，只有这样才能抛开上述种种具体，其实是次要的因素，从而能够更加直接和准确地进行评价和测量算法，最后得出一个客观的结论（开篇对算法的定义：所谓算法可以看作是指基于特定的计算模型下，解决某一信息处理问题而设计的一个指令序列）



图灵机模型就是这种理想的计算模型或者说是平台，图灵机模型具有以下要件：

• 首先是Tape也就是纸带，这个纸带被均匀划分为一个一个的小个子，称作Cell，每个小格子上面都标注有某个字符，默认的初始情况下，所有的格子中都标有一个特定的符号，而每个格子标记的符号，都是来自于一个字符表

• Alphabet这个字母表的长度是有限的，即字符的种类有限

• 还有一个Head，一般称它为读写头，在任何时刻，都是对准了Taple上的某一个Cell，而整个图灵机，是按照一个节拍的节奏来运转的，每经过一个节拍，Head或是向左或是向右移动一格单元，而在对准一个单元格的时候，它都可以读取出这个单元格中所标记的那个字符，也可以修改单元格中的字符

• 整个图灵机，也就是这个读写头，在任何时候都会处于某一种状态State，当然这些状态本身只有有限种可能，图灵机在读写头每经过一个节拍移动一次以后，它都有可能从一个状态转入另一个状态，当然这个过程中需要遵照事先约定好的某一套规则

• 那么这套规则是什么样？它是一种以Transition Function的形式来标识的：（q, c; d, L/R, p）,每一个这样的转换或者传递函数都是由5个元素组成的



第一个元素q代表图灵机或者读写头当前所处的状态，第二个元素c代表的是当前读写头所正对的单元格里所存的字符，前两项可以理解为是当前的状态，后面三项描述的是图灵机紧接着动作，也就是我们说的转换



第三个元素d代表的是在当前单元格里填入的，或者是说修改成的一个新字符，在修改完毕后，读写头自己可以向左或是向右移动一个单元格，即第四个元素L/R，同时将自己的状态由刚才的q，转换为现在的p，即第五元素



在所有的状态中，有一个特定的状态是约定好的，通常用h标记，表示停机，一旦图灵机进入h状态，就会立即停止，此时它所对应的计算任务也就完成了



再来看RAM模型（Random Access Machine），在可计算的意义上将，它和图灵机是完全相等的，尽管两者之间还是有重要的区别

首先一个共同之处就是，它们都拥有无限的空间，它以一组顺序编号的寄存器形式给出来，每一个寄存器都是由一个自然数唯一的标识：R[0],R[1],R[2]

与图灵机的转化函数相对应的，提供了大概由10种格式的可行语句，每种语句的基本操作仅需常数时间：

1.     R[i]  <-  c,        // 将一个常数赋值给编号为i的寄存器

2.     R[i]  <-  R[j],  //也可以在寄存器与寄存器之间完成数值的复制，把编号为j的寄存器中的数值赋值给编号为i的寄存器

3.    R[i]  <-  R[R[j]],  //间接取址，首先去除编号j的寄存器中的整数数值，并将这个整数作为编号，再取出对应编号的寄存器中的数值，最终将取出来的数值赋值给编号i的寄存器中

4.     R[i]  <-  R[j]  +  R[k],  //寄存器与寄存器之间的数值加减两种基本的算数运算，并将能够将结果转入到第三个寄存器中

5.     R[i] <-  R[j]  –  R[k],

6.     R[i]  <-  R[j],  //也可以在寄存器与寄存器之间完成数值的复制，把编号为j的寄存器中的数值赋值给编号为i的寄存器

7.     R[R[i]]  <-  R[j],

8.     IF  R[i]  =  0  GOTO  L,  //为了构成算法，这里也不可或缺的需要有条件判断语句和转向语句，所谓条件判定语句，也就是判断一个寄存器中的数值是不是0，只要条件满足，就会相应的转到对应的语句，这个L是顺序语句的编号

9.     IF  R[i]  >  0  GOTO  L,  //判断数值是不是正数

10.  GOTO  1     STOP  //绝对转向，还有一个特别的STOP语句，也就是终止语句，和图灵机中的那个停机状态h是完全对等的，每当执行到STOp，对应的程序都会停止下来

与图灵机模型一样，两者其实都是对一般的计算工具进行抽象以后的简化，这样一个简化之后，不仅可以用这种基本的简单的操作来描述算法，最重要的是，可以因此独立于具体的环境和平台，对具体算法的总体效率做出比较和评判，这种比较和评判，相对于之前那种实验统计的方法更具有可信度

为什么会这样？这里关键是做了一个转换，也就是将算法的有效时间转换成了，在上述这些计算模型上执行算法的过程中所需执行基本操作的次数（时间 -> 次数） ，这样就将时间的统计问题，转换为了次数的整体求和和估算问题

因此，之前定义的那个T（n），也就是在求解规模为n的问题时所需要的时间成本，在这里可以转换为，所需要执行的基本操作的次数

这样的好处有很多，其中一点是至少现在不用考虑硬件环境了，评价一个算法好不好，并不取决于运行的时候所依赖的那个CPU主频的快慢，而取决于它本身需要执行多少次CPU的计算

通过图灵机模型和RAM模型，给出了一个清晰准确的尺度，这个尺度可以用来对算法进行度量，也因此可以判断，哪个算法的性能更好

如果说把计算模型比作一杆直尺，那么大O记号就是尺子上的刻度，开心的是，并不需要强调这种刻度的精细程序，而是在定性和定量之间达到一个适度的折中，使得可以用更短的时间更迅速地抓住DSA性能方面的要害和主要的方面

大O记号作为一种强大的工具，对于复杂度分析而言，是非常至关重要

大O记号可以使着不拘泥于问题的细节和一些琐碎的部分，比如考察一个DSA的时候，应该更多的看重它的长远，也就说，要看DSA的潜力如何，比如在处理更大规模问题的时候，它应该是如何的，第二不要过多纠结于它的细微不足，而应该更多的看到它主要的方面，也就是主流

回到之前说的问题，随着问题规模的增长，计算成本如何增长？这里更关心的是足够大规模的问题，而且考察的是计算成本的总体增长趋势

因此，应该更倾向于Asymptotic analysis,也就是渐近分析方法，具体来说就是考察，当问题的规模足够大时，相应的规模为n的时候，需要多少计算的时间，之前说过，计算时间可以转化为需要执行的操作次数，以及存储单元相应需要的规模（空间成本通常可不考虑）





横轴表示问题的规模n，纵轴表示相应的计算成本F（n），那么数据结构和算法的任何一个具体组合都可以得到这样一条曲线T（n），我们所关心的并不是这条曲线上局部的、细微的包含暂时的一些趋势，而是看它主要的、长远的变化的趋势

为此可以采用大O记号的表示方式，从形式上简化度量时间的T（n）的表示，具体来说，在满足一些条件之后，可以在big-O的意义下，将大写的T（n）转换为某一个F（n）的函数

什么条件呢？这个条件就是需要存在一个预先确定的一个常数c，当n足够大后，就会发现T（n）绝不会超过F（n）的常数倍：T（n）< F(n) * c，这样的话就有可能可以更为简便地界定一个算法的复杂度

看一个例子，假设已经得到这样一个T（n）表达式，那么可以看到这个表达式闲着略微复杂，不容易抓住其中主要的脉络，为此可以采用之前说的办法，不断简化，注意T（n）< F(n) * c 用的是小于号，所以我们可以不断地对函数T（n）进行放大

• 先把 中的2替换为n，之前说了，当n足够大后，是会远远大于2的，所以不妨替换它，现在这个地方就是： $2n\to (n+n)$

这也是为什么经过一次放大后，转化为：  $6n^2\to [3n\cdot (2n)+4]<[6n^2+4]$



• 接下来，对4做一个放大，同样的把它放大成：  $n^2\to [6n^2+4]，$

这也是，为什么会有一个常系数35的 $n^3\to 5n\cdot [6n^2+n^2]<35n^3$

• 接下来，再对6做一次放大，放大成：$n^3\to 35n^3+6，$

这样就可以得到 ，大概是等于：$6\cdot n^1.5$

因为这里还有一个常数 $c\to c\cdot f(n)$

而通过T（n）< F(n) * c可以看出，常系数6其实可有可无，所以可以把这个6进一步的抹去，最后通过在外面再加一个big-O记号，来完成这样一个估计   $\to O(n^1.5)$

刚才那个例子告诉了我们，经过这样的一次变换之后，big-O内用来近似的那个函数F（n），将会更加的简洁，同时它依然能够准确地反映前者的增长趋势

根据这样的一个定义以及充要条件，可以得出关于大O记号的两个重要处理手法：

第一个，任何这种函数的常数项系数是可以忽略掉的： $O(f(n))=O(c\cdot f(n))$ ，c可以等于1

第二个，低次项也是可以忽略掉，如果一个表达式可以表示或者是至少展开成这样一个多项式的形式： $O(n^a+n^b)=O(n^a)，a>b>0$ 那么低次项$n^b$ 是可以忽略不计

从这里可以看出，之前说的长远是体现在n足够大，而所谓的主流就体现在所有这些常系数和低次项等这些非主流的旁支末节的因素都是可以忽略的，使得主流的信息能够突出出来





这个图在之前的途中，增加了一个big-O的这样一条虚线，可以从这个图很好地看出来big-O所设计和定义的用意

可以理解为在时间复杂度的上方给出了T（n），也就是这个时间复杂度的上界upper bound，所以可以认为big-O是对T（n）的一个悲观估计

在当n规模比较小的区域内，T（n）未必在big-O这条曲线的下方，实际上big-O这个upper bound这条线，完全是可以在常系数的下面，它在准确的数值上，未必是低于T（n），只要预先约定好一个常数项系数c，经过放大能够完成上界这样的功能就可以了

还有另一些记号可以帮助考量数据结构与算法的效率，比如说， big- $\Omega$记号（T（n） = （F（n））），这个记号从定义上讲，它的充要条件依然是需要一个常数c，当n足够大后，T（n）> F（n）* c，从定义上将，big- $\Omega$是定义原来复杂度T（n）的一个 下界，这种情况往往属于算法最好的情况，

还有一种记号，big-$\theta$ 记号，可以认为是big-O和

big-Ω的组合，它要求同时存在两个常数c1和c2，且c1 > c2 > 0，规模n足够大时，

c1 * F(n) > T(n) > c2 * F(n)，在经过c1和c2的放大后，T（n）可以被同一个函数F（n）从上下两方界定，所以可以认为θ构成了一个准确的确界





在大O记号定义的这杆直尺上，到底有哪些刻度？首先看第一个刻度，即常数复杂度，把它记作O（1）

哪些是常数复杂度呢？这里的常数，包括较大的常数，以及常数按照经过四则混合运算之后得到的常数，甚至常数的更高阶次的一些运算结果，从理论上将，依然认为是常数

如果有算法能够达到这样的复杂度，那真是再好不过，什么都不用做就能得到结果，那是不可能的

从代码段的形式上来看，如果一段代码中不含显示的或者隐式的循环，具体来讲就是由分支判断构成的代码体，那么它必然是顺序执行的，总体而言，它必然是O（1）的复杂度

接下来说的是对数复杂度O（logn），也就是问题规模n的对数，往往不需要标明底数，因为在底数为常数的情况下，其实具体是多少，在这里都是无所谓的，在big-O中，常系数是也可以忽略的，所以说具体是a还是b都是无所谓的，只要是常数，就可以忽略），常数次幂也如此：c > 0，$log{n}^c=c\ast logn=O(logn)$（高阶项可以等价换算到log的前边，变成一个常系数），对数本身也可以呈现多项式的形式，但依然可以简化，得到一个简明的log多项式形式

对数复杂度这类算法依然十分高效，因为从渐近地意义上讲，可以证明对于任何一个多项式，哪怕次数很低，只要它是一个正数次数的c，logn都是可以在大O记号的意义下，被n的c次方所掩盖，所以它应该是低于任何多项式的一个复杂度，从这个意义上讲，它本身应该是无限接近于O（1）的：c > 0 ,  $logn=O（n^c）$

接下来的一个刻度是一个大家族，统称为多项式复杂度，从一般意义上讲复杂度呈现出多项式的一个形式， 之前说过多项式的低次项是可以忽略不计的，即便是最高次项，它的常系数依然可以忽略，所以这个多项式可以很简明的界定，其中最高次此也就是这个多项式本身的次数$O（n^k）$

线性复杂度属于多项式复杂度的特例，n的阶次为1：$n^1$，所谓的线性复杂度指的是一个规模为n的问题，它所需要的时间成本恰好就是由n一阶来度量的：O（n），

更高的多项式复杂度会使着问题的难度一下增加，计算时间也会提高，在算法复杂度理论中，多项式时间复杂度被视为一个具有特殊意义的复杂度级别，多项式级的运行时间成本，在实际应用中被认为是可以接受或者说可以忍受的，若一个问题存在一个复杂度在此范围以内的算法，则该算法是可有效秋活的或易解的

多项式的次数为一个正的常数，而未对其最大取值范围设置具体上线，所以实际上复杂度界别涵盖了很大的一类算法，如n的平方和n的2012次方，尽管两者的计算效率有天壤之别，但依然属于同类算法，因为从理论上来说，不得不把它归类为稍微容易求解的问题，因为相对于后面难解的问题，需要下一个刻度即指数级复杂度来划分

指数复杂度具体来说，计算成本T（n），可以表示为一个常数a的n次方形式：T（n）= $a^n$ （前者n为问题规模，后者n为a的阶次），这个和刚才的多项式是有天壤之别的，当c > 1，对与任何固定的n的c次方这样的多项式而言，它都可以在大O记号的意义下，被2的n次方这样的一个指数形式所覆盖：$n^c=O（2^n）$，这类算法的计算成本增长极快，通常被认为不可接受

从$O（n^c）$到$O（2^n）$，是有效算法到无效算法的分水岭，很多问题他的指数形式的算法都很容易看出并且实现，但试图去改进成一个多项式算法却极其不容易，甚至很多情况，注定只能是徒劳无功的

考察这样一个问题，如果给定了n个正整数，它们的总和恰好是两倍的m，那么是否存在一个其中的子集T，使得T中的元素总和是整体综合的一半？

∑S = 2m，∑T = m？

直觉算法：逐一枚举S的每一个子集，并统计其中元素的总和

注意到，所枚举的子集相对于原来的集合来说，就是所谓的幂集，而幂集的规模就是原来集合的规模，以2为底的指数：$2^s=2^n$，所以这些要枚举的实例总数其实就是一个指数规模

那么有没有更好的算法优化它，可惜是没有的，这类问题是一个典型的NPC问题，就目前所采用的计算模型而言，不存在可在多项式时间内回答此问题的算法，所以就此意义而言，上述的直觉算法以属最优（笑哭）

把所有的刻度汇总在一起，让对这把直尺以及上面的刻度有一个总体的感觉和认识，这里要记住，需要放眼长远，如果只是在一个相对较小的尺度（规模），只观察局部的话，有可能会得出错误的结论





针对算法复杂度的界定，都是相对于问题的输入规模而言的，不同的人在不同场合下关于输入规模的理解、定义和度量可能各不相同，因此就可能导致复杂度分析的结论有所差异，严格地说，所谓待计算问题的输入规模，应严格定义为：用以描述输入所需的空间规模，即输入参数m的二进制展开宽度作为输入规模更为合理，对应地，以输入参数n本身的数值作为基准而得出的O（logn）和O（n），则应该称作伪对数和伪线性复杂度