听邓公课，反思之余的随记。

主要脉络

五个问题，环环相扣。

什么是计算？

计算是数据结构主要的研究对象和内容，甚至可以说是终极目标。
评价DSA优劣的参照？

在回答完什么是计算这个问题后，那下一个问题就是怎样才能够构成一个优秀的计算。好的计算取决于所使用的数据结构和算法的性能，这里存在一个好坏的问题。归纳而言，就是如何来给出一个参照，使得我们可以来谈论和比较这个数据结构和算法的优或者劣。所以形象的说就是给你一把度量的尺子，即给出标准的计算模型。
度量DSA性能的尺度？

有了标准计算模型后，难道我们需要去精细的测量一个数据结构和算法的复杂度嘛？其实不必。我们在一定的精细度情况下来做这种测度就足够了，所以引入所谓的渐进复杂度的概念。在这个概念的指导下，可以将所有的数据结构和算法分出一些渐进的层次，在这种层次上做出相应的界定，就相当于我们在这把度量的直尺上加上足够精细又刚刚够用的刻度。
DSA性能度量的方法？

有了这种刻度以后该如何去具体的度量一个给定的数据结构和算法的性能呢？
DSA的设计及其优化？

这个问题要更复杂一些，我们在知道数据结构和算法的优劣后，如何来设计并且对它进行优化？

还有两个相关的拓展问题。

理论模型与实际性能的差异？

上述给出的那把带着刻度的直尺，和实际有没有区别？有多大的区别？那我们的答案是存在区别，细微但同时也确实是很本质的区别。
DSA优化的极限(下界)？

当我们知道算法和数据结构可以不断优化的时候，能不能一直优化下去？任何一种优化都应该是有尽头的。从复杂度的概念来讲，它总有一个极限的最低的复杂度，即复杂度的下界。

a) 计算

计算是数据结构的直接研究对象和内容，以及最终的研究目的。我们需要在计算的过程中研究其所蕴含的本质规律，也需要总结和挖掘出其中一般性的方法及典型的技巧。最终的研究目标可谓是实现有效、高效的计算的同时，在资源的消耗方面也做到足够的低廉。

实际上，推而广之，计算也可以看作是整个计算机科学的研究对象，内容和目的。

Computer science should be called computing science, for the same reason why surgery is not called knife science. - E. Dijkstra

计算机科学的本质是研究计算过程中的规律和方法，而计算机自身无非是我们的一种工具和手段，计算才是我们最终的研究目的和目标。这是在计算机科学的角度进行的主次之分。

在给出计算的明确概念之前，不妨通过几个实例来看所谓的计算具有哪些特点和共性。

当我们给定一条直线L，之后我们在上面确定一个点A。如何经过这个点做这条线的一条垂直线？在4000多年前，古埃及人使用12段长度均等的绳索首尾连接而成的一个环状的工具解决了这个问题。利用这种工具，重复的，机械的完成了全过程，这其实就是一种计算。

另一个例子是中学的平面几何。

任意给定的端点A和B确定的一条线段，如何在这条线段上找出恰当的两个切分点，使得这两个切分点能够将这条线段均匀的切分为三段。解决方式就是中学的尺规作图。

这个例子背后的原理就略过，我们需要从计算的角度反思一下这个过程。

首先计算的过程需要工具，这里我们的计算工具就是欧式作图所需的直尺和圆规。另外，这一整个计算过程也是会被分解为若干步骤，并且每一步骤都可以明确的描述出来，然后机械的执行。这与刚才的绳索计算是类似的。这几个过程实际上都隐含了一种子程序的概念，也就是说一个算法里可能同时会包含解决另一个相对来说较小问题的算法，比如一些通用的作图步骤。这样我们也能总结出算法与算法之间可以互相套用的特点。

此外还有一些问题，比如说这种计算能解决什么，它的能力范围在哪，以及它不能解决什么。这里就不多讨论了。计算本质的特点其实通过这两个例子已经能够清晰的体现。

回到原来的话题，什么叫一个计算的过程呢？

如果抽象的认为计算是一个信息处理的过程的话，那么首先它必须借助某种工具，比如刚才的绳索计算机或者是尺规计算机。然后还需要遵照一定的规则，比如说刚才提到的绳索的使用方法以及尺规的使用方法。而且必须能够以明确的，很机械的方式形成一系列由基本操作所构成的序列。概括就是：借助某种工具，遵照一定规则，以明确而机械的形式进行的过程。

我们常说的计算机实际上也是某种计算模型，可以认为是信息处理工具。

所谓算法，就是在特定计算模型下，旨在解决特定问题的指令序列。算法具有如下特征与描述。

输入：待处理的信息/问题。
输出：经处理的信息/结果。
正确性：经处理，可以解决指定的问题。

我们给出的计算过程应该能达到我们的要求。虽然在实际中这一点并不是那么容易，但是至少我们可以假定这个是满足的。
确定性：任一算法都可以描述为一个由基本操作组成的序列。

所有的操作都应该是确定的，都可以描述为一个或者若干个基本的步骤。这些操作都是语义明确的。
可行性：每个基本操作都可以实现，且在常数时间内完成。

所有的操作都必须在计算的条件下能兑现。像“如何把大象装在冰箱里”这种，其中把大象赶进冰箱里是不可能兑现的。这样的算法毫无意义。
有穷性：对于任何输出，经有穷次基本操作，都可以得到输出。

有穷性很关键，有如下的例子。
\[Hailstone(n)= \begin{cases} \{1\}, &n\le 1\\ \{n\}\bigcup Hailstone\{\frac n2\}, &if\ n\ is\ even\\ \{n\}\bigcup Hailstone\{3n+1\}, &if\ n\ is\ odd \end{cases}\]
考察如上的Hailstone secquence，任取一个自然数n，以递归的形式来定义这样一组序列。对于n不超过1的罕见状况，就直接将其定义为由单个元素构成的序列。如果n大于1，那么就分奇数和偶数两种情况处理。
\[Hailstone(42)=\{42,21,64,32,...,1\}\]
64是特殊的数字，可以不断的折半。但序列的整体体现出一种飘忽不定的状态。虽然它有可能会持续的下降，但绝对不会持续的上升，原因在于每当任何一个奇数乘3加1后就必然会回到偶数的状态，然后继续折半。整个过程和冰雹很相似，有时候会偶尔上升，但紧接着总体会下降，偶尔又会上升，然后接下来又会不断的下降。

我们可以编写程序计算这个序列，或者说计算这个序列的长度。计算长度已经足够说明问题，无需将过程复杂化。
```
  int hailstone(int n) {  //计算序列的长度
  	int length = 1;  //从1开始，按定义逐步递推，并计数
  	while (1 < n) { (n % 2) ? n = 3 * n + 1 : n /= 2; length++;}	 
  	return length;  //返回｜Hailstone(n)｜
  }
```
上面这个程序的正确性似乎是不言而喻的，但其实并没有这么简单。值得注意的是，序列的长度与输入的n未必是成正比的。比如我们取7，就会发现序列的长度会远远的超过取42时的序列，甚至可能出现无穷的情况。如果称上面的程序是一个算法的话，它就应该满足有穷性。也就是说，它对任何的输入都应该在有限的步骤后退出返回，那么上面的循环能够做到这一点吗？

能不能做到不取决于这个程序，而是取决于这个序列自身的定义。任取一个n，它对应的序列长度是否都会是一个有限的长度呢？如果是，那算法的有穷性自然就满足；如果不是，这个程序就不见得能称作是一个算法。

但这个问题还没有结论。也就是说，我们既不能证明对于任何的n，这个序列都必然是有穷的，反过来也没有找到反例。所以从这个意义上讲，这段貌似非常简单，正确性都是一目了然的程序，它未必是算法。

程序未必是算法。

但我们都会时不时写出死循环的程序。所以，说算法的有穷性时，即使是作为算法的一个侧面要求，也不是那么简单就能够确定的。但再深究就不是数据结构的范畴了。

那什么是数据结构研究的问题呢？

在正确性，确定性，可行性，包括有穷性都基本确定了之后，我们如何能够设计并且优化出更好的一个计算过程，一个对应的数据结构和对应的算法。这就是研究的关键。

那什么是一个好算法？什么是好的计算过程？这可能是一个比较难回答的问题，不过我们或许能从不同的侧面听到过不同的回答。

正确：符合语法，能够编译、链接。

算法应该能正确处理简单的、大规模的、一般性的、退化的以及任意合法的输入。这确实是好算法的一方面，但这并不是最值得在意的。
健壮：能辨别不合法的输入并做适当处理，而不致非正常退出。

这也不是最值得在意的。
可读：结构化+准确命名+注释…

这点是非常值得强调的，程序除了是人与计算机交流的渠道外，还是人与人交流的一种方式，就像自然语言。也就是说，你设计出来的算法，在形式上必须是结构清晰的，所有的变量和有语义的对象的命名都应该是准确的。同时还应该准备足够多的注释和文档等等。但这依然不是最重要的。

那最重要的到底是什么呢？其实就是这样两个字：效率。

也就是说我们不仅需要指挥计算机来进行计算，同时希望它计算的速度要尽可能的快，消耗的资源要尽可能的少。如果以前有一句话叫做“既要马儿跑，又要马儿不吃草”，那我们在这里努力的方向，简要的说就是“既要马儿快快跑，又要马儿吃的少”。

在此前曾经有一个很著名的一个公式，算法和数据结构的结合就可以得到解决问题的程序。

Algorithms + Data Structures = Programs

那正如刚才所说的，程序未必能够进行有效的计算。所以邓公(heihei)对这个公式略做一点修改。在算法和数据结构这两个因素都兼具后，还需要具有效率。

(Algorithms + Data Structures) · Efficiency = Computation

这个等式的前提是这些因素不是简单的堆砌，而是能够有机的融合和结合。只有在这样的情况下，才能够写出高效的程序和算法，从而高效率的完成计算过程。

b) 计算模型

之前的内容概括来说，核心就是计算。计算实际上是来自于实际应用中(现实)的需求，为此我们必须保证计算能够高效的同时，能够低耗的进行。相应的我们需要在数据结构以及算法两个方面下功夫。一个好的数据结构做支撑的同时也需要有一个好的算法，这二者有机的结合才能够实现高效率的计算，进而完成相应的服务与应用。

所以高效的计算必然对应着好的数据结构和算法。反之亦然。那么计算的好与坏我们可以用高效和低耗来度量，那么算法和数据结构的好与坏又该如何度量呢？

To measure is to know. If you can not measure it, you can not improve it. - Lord Kelvin

在测度这个问题上，我们有两步要走。第一步是去认识一把抽象的，理想的并标有精密刻度的尺子；第二步才是如何去真正的运用这把尺子去度量DSA。

这里所谓的测量，实际上是算法分析的范畴。算法分析大致有两个方面。

证明DSA正确。

这不简单，不过不是数据结构最主要的方面。有系统的算法分析理论。
DSA成本：运行时间 + 所需存储时间。

把性能倒过来看，就是成本。这里分为时间成本和空间成本。

我们暂时把空间成本拖略掉，将注意力更多的集中在时间成本上。

那么目前的问题就是，如何来度量时间成本？如果这种度量涉及到两个或者多个DSA，那么它们之间又该如何进行比较？

思路首先是从建模开始。不妨在数学上定义一个表述。

\[考察：T_A(P) = 算法A求解问题实例P的计算成本\]

如果我们采用A算法来求解某一个问题的具体的一个实例P，那么它所需要的计算就是如上的时间成本。如果能够真正的获得这样一个度量值的话，我们当然可以拿来对算法进行比较。不过遗憾的是，这样的定义意义不大。因为一个问题所能够出现的实例是非常多的，我们不可能把目光聚集在这么多具体的实例上。而且任何一个实例都存在以偏概全的问题，它不可能使我们获得对这个问题对应的算法的一个总体的、全面的认识。所以必须进行归纳和概括。

那么如何进行归纳概括呢？数学中也给此类的问题提供了有效的模板。其中一种常用的有效方法就是划分等价类。对无数的实例进行一定的出粗分类，然后就某一类再来谈它的计算成本。

怎么分类呢？一般在这里会观察到一个普遍的结论，它在大多数的时候总是成立：任何一个问题，它的计算成本实际上是和对应的实例规模是相关的。一般还是正相关。当然这存在反例，不过并不影响我们的判断。大体上确实是如此。

例如，前面三等分线段的问题，如果我们把分成多少段的段数作为问题的输入规模的话，那么随着段数越多，这个问题的计算成本和代价也会相应的更高。所以概括而言，规模越接近，它们所对应的计算成本也会彼此接近，而随着规模的增加，计算成本通常也会呈现上升的趋势。

经过了这样一个等价类的划分后，我们就可以改写刚才的数学的度量形式。

\[考察：T_A(n) = 用算法A求解某一问题规模为n的实例所需的计算成本 \\ 在讨论特定算法A(及其对应的问题)时简写为T(n)\]

把原来具体的问题实例换成了一个笼统的规模度量值n。不过这样的定义也不足以支撑我们的需要。因为即便是同一个问题，它不同规模的实例的计算成本可能会有实质性的差异。例如，假设在平面上的n个点中，找到构成三角形面积最小的三个点。我们可以采取所谓的蛮力算法，也就是逐一枚举所有C(n,3)组合，正确性当然是不言而喻的。但是最好的情况或者最坏的情况所需要的成本是天差地别的。可能你把所有的组合都尝试遍了，在最后才会找到面积最小的三个点。而我们也可能一开始就找到三个共线的点。所以同样规模为n的那些实例中，它们所需要的计算成本是有天壤之别的。显然我们不能把命运都寄托在最好的情况，而应该更多的关注最坏的情况。

\[T(n)=max\{ \ \ T(P)\ \ | \ \ |P|=n\ \}\]

如上式，在所有规模为n的问题实例中将它们的计算成本进行总体的比较，确定其中的最大值。当然我们也会关注其他的性能，比如平均性能，分摊性能等等，不过首当其冲的还是最坏的情况。因为最坏的情况是必须要避免的。

在解决了特定算法的评价问题之后，就需要进一步回答另一个问题：同一个问题拥有多个算法的时候，我们如何来评价它们之间的好坏呢？一种直观的方法是实验统计方法，谁用的时间越短，资源越少，那么谁就越优秀。但是这种最直接的方法在实际应用中是不够用的，因为它并不能准确的反映一个算法真正的效率。我们做的实验测试总是不充分的。不同算法各有所长，如果测试时考虑的不够全面，那么这种测试本身就是带有偏见的，结论也就难以让人信服。即使是同一种算法也可能是由不同的程序员完成，他们会去选择不同的编程语言，进一步的可能会选择不同的编译器。甚至设置不同的编译优化选项等等。再进一步，即便上述因素能做到一致，那编译出来的执行代码在不同的硬件体系结构上，在不同的软件的操作系统上，它体现出来的性能在此时和彼时也可能有很大的区别。有限次实验统计不足以完全覆盖这些因素。

综合而言，为给出客观的评判，我们需要抽象出一种理想的计算平台或模型。这样才能更加直接和准确的测量算法，最后得出一个客观的结论。不是真正的去做一个现实中的实验，而是在头脑中去做一个虚拟的，理想的，但是又能够反映事物本质的实验。

目前人们已经构造出了很多种这样的理想平台，如图灵机模型和RAM模型。在可计算的意义上讲都是等价的。它们的一个共同之处是都拥有无限的空间，这点在现实中还无法做到。在这些计算模型的执行过程中可知算法会对它所处的整体状态有严格的规范要求，这种规范更多的是以接口的形式给出的。其他内容就不再赘述。不过，为什么算法在经过这些模型简化后就可以独立于具体的环境和平台对算法的整体效率作出比较和评判，还具备可信度呢？

这些模型关键都是做了转换，将算法运行的时间转化为在上述这些基本平台上所执行算法的过程中，需要执行的基本操作的次数。概括说就是时间到次数的转换。将时间的统计问题转化为执行次数的整体求和和估算问题。这样转换的好处很多，比如一个算法好坏并不取决于运行时CPU的快慢，更客观的是取决于它本身需要执行多少次CPU的计算。从这种角度出发会更加客观。

\[T(n)=算法为求解规模为n的问题，所需执行的基本操作次数\]

概括而言，图灵机模型和RAM模型给我们提供了清晰的尺度，这个尺度确实可以对算法进行度量。

c) 大O记号

如果将上一节介绍的计算模型比作一杆公正的直尺，那么大O记号就相当于是这杆直尺上的刻度。前面也提到，我们不需要一味的追求刻度的精细程度，而是在定性和定量之间达到一个适度的折中。这使得我们可以用更短的时间来迅速的抓住DSA性能方面的要害。

Mathematics is more in need of good notations than of new theorems. - Alan Turing

对于数学而言，最急需的是优秀的记号。

好读书不求甚解，每有会意，便欣然忘食 - 陶渊明

这里的不求胜解不是不去求解，而是说我们不要过多拘泥于问题的细节。换而言之，我们在考察DSA时，应该像考察一个人一样，更多的应该去看中它的长远，而不去纠结于细微的不足。比如说它在处理更大的问题规模时候，会有怎样的表现。这就是大O记号的思想所在。

回到最初的问题。随着计算问题规模的不断增长，相应的计算成本会如何增长呢？我们更关心大规模的问题，而且考察的是计算成本的总体增长趋势。因此我们更倾向于采用渐进分析的方法，如下式。

\[当n\ge2时，对于规模为n的输入，算法 \\需执行的基本操作次数：T(n)=? \\ 需占用的存储单元数：S(n)=?\]

计算模型可以将算法转化为平台上基本操作的次数以及存储单元需要的存储规模(后者目前不考虑)。如果用横轴表示问题的规模，用纵轴表示相应的计算成本，那么任何一个数据结构和算法的组合都可以得到一条曲线。

那么我们关心的并不是这条曲线局部的一些趋势，而是看它长远的变化趋势。为此我们可以采用大O记号表示度量的时间成本。充要条件是存在一个预先确定的常数c，当n足够大时T(n)绝对不会超过f(n)。

\[T(n)=\Omicron(f(n)) \ \ iff \ \ \exists c \gt0,当 n \gt\gt2后，有T(n) \lt c\cdot f(n)\]

可以看一个例子。

\[\sqrt {5n \cdot [3n \cdot (n+2)+4]+6} \lt \sqrt{5n \cdot [6n^2+4]+6} \lt \sqrt{35n^3+6} \lt 6 \cdot n^{1.5} = \Omicron (n^{1.5})\]

左边的表达式显得复杂，不容易抓住其中主要的脉络。为此，我们可以采用放缩的技巧完成这样的一步估计。与T(n)相比，f(n)更加简洁，但依然反映前者但增长趋势。关于大O记号有两个重要的处理手法：1)常系数可忽略；2)低次项也可以忽略。旁枝末节都可忽略，突出主流。

\[\Omicron(f(n))=\Omicron(c *f(n)) \\ \Omicron(n^a +n^b) = \Omicron(n^a), \ \ a \gt b \gt 0\]

在大O记号的处理下，我们可以发现这是对T(n)的一个悲观估计，是复杂度的上界。不过在上图中，在输入规模较小时，曲线未必在大O曲线的下面。不过大O曲线的函数值可以经过任意一个确定的常数进行放大，直到能达到上界的程度。这点在图中无法体现。

还有另一些记号可以帮助我们从其他的侧面来考量数据结构和算法的效率。如上图的另外两条曲线所对应的符号。

\[T(n)=\Omega(f(n)): \\ \exists c \gt 0,当n \gt \gt 2后，有T(n) \gt c \cdot f(n) \\ T(n)=\Theta(f(n)) :\\ \exists c_1 \gt c_2 \gt 0,当n \gt \gt 2后，有c_1 \cdot f(n) \gt T(n) \gt c_2 \cdot f(n)\]

前者构成了复杂度函数的下界，象征着算法最好的情况；后者相当于是一个准确的解。不过用的最多的还是大O，只有在一些特定的环境下，我们才会去讨论Big Omega和Big Theta。

在大O记号这杆直尺上有哪些刻度呢？

常数复杂度O(1)

2 = 2013 = 2013 * 2013 = O(1)，甚至是2013的平方。从理论上讲，更高阶的依然算是常数，这类算法效率最高。

哪些算法从代码段的形式上看是符合这种复杂度的呢？如果一段代码不含一些显式或隐式的循环，那么它必然是顺序执行的。不过有很多时候，代码包含循环，但未必会造成更大但复杂度；有时可能既有条件又有转向，但在语义上存在某种限制使得转向但目标不可能达到；还有一些隐式的递归等等。
```
  // 循环
  for (i = 0; i < n; i+= n/2013 + 1);
  for (i = 1; i < n; i= 1 << i);
  // 分支转向
  if ((n + m) * (n + m) < 4 * n * m) goto Unreachable;
  // 递归
  if (2 == (n * n) % 5) 01(n);
```
对数复杂度O(logn)

在这种刻度下，往往不需要标明底数。在底数是常数的场合，底数数值多少是无所谓的。经过换底变换后，多出一个常系数忽略后，完全没任何影响。
\[\forall a,b \gt 0, log_an = log_ab \cdot log_bn = \Theta(log_bn)\]
常数次幂也是无所谓的。
\[\forall c \gt 0, logn^c = c \cdot logn = \Theta(logn)\]
对数也有多项式的形式，可以参照上两个处理方式，低次项，常系数和常指数都可以忽略。对数复杂度的算法也非常高效，复杂度无限接近于常数。
\[\forall c > 0,logn = \Omicron(n^c)\]
多项式复杂度

同上，常系数和低次项可以忽略。可以很简明的按照多项式的最高次来定。
线性复杂度：所有O(n)类函数。一个规模为O(n)的问题，它所需要的时间成本恰好就是由n的一阶来度量的。编程问题主要涵盖的范围是n到n的平方的复杂度。更高的复杂度会使得问题的难度增加，计算时间提高。

通常算法是多项式复杂度，我们就可以认为是令人满意的了，当然你可能会觉得这样的标准是不是太低了，因为多项式的阶次c并没有做更多的限定，那么它可能是1，2，也可能是20甚至是200乃至更高。难道这样就可以了吗？

我们说确实是如此，因为在理论上讲，我们不得不把它归类为稍微容易求解的问题，而再往下，下一个刻度就要被归结为所谓的难解问题，即指数复杂度。

指数复杂度
\[T(n)=a^n \ \ \{ \Omicron(2^n)\}\]
显而易见，和多项式复杂度是天壤之别。
\[\forall c > 1, n^c = \Omicron(2^n) \\ n^{1000} = \Omicron(1.0000001^n) = \Omicron(2^n) \\ 1.0000001^n = \Omega(n^{1000})\]
对于任意次数的多项式来说，它都可以在大O记号意义下被2的n次方完全覆盖。即便n的次数是1000，但另一边，只要底数稍微大于1，即便尽可能的小，它的增长速度也是非常非常快的，远超多项式。多项式在某种意义上也构成了指数复杂度的下界。

指数复杂度的算法计算成本增长极快，是无法忍受的，属于难解问题。这中间的分水岭就是多项式复杂度和指数复杂度之间的界限。但往往很多问题的指数复杂度算法很显而易见，而设计出多项式复杂度算法却极其不易，甚至是徒劳无功的。

Subset is NP-complete

就目前的计算模型而言，不存在能在多项式时间内回答等分集合的算法。目前而言，指数复杂度的直觉算法已经最优。这种类似的问题也是很多的。不过不是这个学科讨论的重点。

在把所有的刻度汇总到一起后，我们可以对这把直尺有一个总体的感觉。当然同样需要放眼长远，如果我们只观察局部的话，很可能会得出一个错误的结论。

d) 算法分析

通过以基本的计算模型作为参照，并且以记号的形式在上面加入适当的刻度。实际上这里已经建立了一套对DSA进行分析的完整的工具和体系。接下来重点就是如何运用这种工具对DSA进行性能的分析。我们在具体运用这套体系的时候，依然要坚持去粗存精。

He calculated just as men breathe, as eagles sustain themselves in the air. - Francois Arago

算法分析的任务主要包括两个方面的内容

算法自身的正确性证明

通过挖掘算法所具有的不变性和单调性来共同证明。
复杂度的分析和界定

得益于前面引入的渐进复杂度的概念，我们在实际的估算过程中，无需统计基本指令的执行次数。在渐进的意义下，C++和其他高级语言所提供和支持的基本指令其实和RAM或图灵机模型所给出的基本操作是等效的。这种等效是在常数意义下的，就渐进复杂度而言，我们往往在不引起歧义的前提下，会偷换或者是借用二者的基本操作或基本指令。当然，我们这里考察的重点依然不是平铺直蓄式的代码段，而是如下几个形式。
```
  分支转向：goto //算法的灵魂，出于结构化的考虑被隐藏
  迭代循环：for(),while()... //本质上就是“if + goto” 
  调用 + 递归(自我调用)  //本质上也是goto
```

我们采用的分析方法大概可以分为这么几类。

迭代式算法：级数求和
递归式算法：递归跟踪(直观) + 递推方程(抽象) + 猜测验证

以上就是算法分析的利器。

最基本的极数是算数级数，从某一个数开始以固定的间隔为单位不断的线性递增的总和。在阶次上与末项的平方同阶。

\[T(n)=1+2+...+n= \frac {n(n+1)} 2 = \Omicron(n^2)\]

再来考察在幂指上对算数级数的推广，可以将这些等式的主要脉络归纳出来，结论是幂方级数的总和是比级数的末项高出一阶。具体求解不再赘述。

\[T_2(n)=1^2+2^2+3^2+...+n^2=\frac{n(n+1)(2n+1)} 6=\Omicron(n^3)\] \[T_3(n)=1^3+2^3+3^3+...+n^3=\frac{n^2(n+1)^2} 4=\Omicron(n^4)\] \[T_4(n)=1^4+2^4+...+n^4=\frac{n(n+1)(2n+1)(3n^2+3n-1)} {30}=\Omicron(n^5)\] \[...\]

几何级数也是算法复杂度的一种重要形式，也就是从某一常数开始，不断的以固定的倍数呈现几何式的增长。同样可以用大O记号将总和从数量级上转化为a的n次。

\[T_a(n)=a^0+a^1+...+a^n= \frac {a^{n+1}-1} {a-1}=\Omicron(a^n)\]

同时也有最常用的一种特例，结论也是类似，几何级数在大O记号的意义下，与级数的末项同阶。

\[1+2+4+...+2^n=2^{n+1}-1=\Omicron(2^n+1)=\Omicron(2^n)\]

收敛级数的各项会逐次递减，而且递减的速度足够快以至于尽管每一项都是正数，但是它们的总和不会超过某一上界。上界的数值虽然不同，但是从渐进的意义上讲都可视作常数。因此从大O记号的角度看，它们都可以记做是O(1)。

\[\frac 1 {\frac 1 2} +\frac 1 {\frac 2 3}+\frac 1 {\frac 3 4}+...+\frac 1 {\frac {n-1} n}=1-\frac 1 n = \Omicron(1)\]

不过这样一类每一项都可能是分数的级数有必要讨论和应用吗？基本操作的次数以及存储单元的数目怎么可能是分数或者小数呢？很有意思的是，在某种意义上讲的确如此。以投硬币为例，假设某段代码的迭代循环可以等效的描述为硬币的投掷过程，这是一个典型的几何分布。最后的解也可以近似为常数。

\[(1-\lambda)\cdot[1+2\lambda+3\lambda^2+4\lambda^3+...] = \frac 1 {1-\lambda} = \Omicron(1), \ \ 0<\lambda<1\]

当然还有另一类级数，它虽然未必是收敛的，但它的长度是有限的。以至于我们能经常用到的。

\[h(n)=1+\frac 1 2 + \frac 1 3 +...+\frac 1 n = \Theta(logn)\]

调和级数的界，可以估计为确界。这是个确解，另外一个就是对数级数。

\[log1+log2+log3+..+logn=log(n!)=\Theta(nlogn)\]

n的阶乘取对数，从渐进的意义上讲是和nlogn等阶的。这两个级数都是我们在后面会经常用到。其余的可参考具体数学(Concrete Mathematic，Goldbach Theorem)。

借助上述结论，如何分析代码段中涉及的循环操作的复杂度呢？

for (int i = 0; i < n; i++)
	for(int j = 0; j < n; j++)
		exe(i,j)

这是一个典型的二层循环，控制变量间没有耦合。内循环每一次执行的都是长度为n的循环，而外循环要求内循环也要反复的迭代n次。从数值上看，是常数的数列，和就是n的平方。稍微变化一下，就有如下这段代码。

for (int i = 0; i < n; i++)
	for(int j = 0; j < i; j++)
		exe(i,j)

\[\sum_{i=0}^{n-1}i=0+1+...+(n-1)=\frac {n(n-1)} 2 = \Omicron(n^2)\]

这段循环对应一个算数级数。作为算数级数，总和的阶次取决于末项的平方。就复杂度而言，这两段循环在渐进的意义上讲是完全相同的。整个过程有两个变量，就可以用一个二维图形表示，它的面积就等效于执行的时间和复杂度的大小。前者是正方形，后者是三角形，从图形上可以清楚的看出，后者面积虽然只有前者一半，但是从渐进的阶次而言，二者是完全相等的，都是平方的量级。

下一段实例又做了一些变化，内部的循环变量每次增长2013。

for (int i = 0; i < n; i++)
	for(int j = 0; j < i; j += 2013)
		exe(i,j)

不难理解，整个过程依然会构成一个算数级数。我们固然可以沿用刚才的算数方法，但是现在也许不必再这样做了。因为我们可以在头脑里参照画图的方式画出同样的一个二维图形，这次内循环的步长更大。最后得到的面积确实可以用来度量，尽管面积貌似缩小了，但这只是一个常系数下的缩小，并不足以影响整个代码的渐进时间复杂度，依然是n的平方。

进一步再来看这样一个例子。外循环的控制变量不再是线性的增长，而是每次都做了一个左移一位的操作，等效于乘2。

for (int i = 0; i < n; i <<= 1)
	for(int j = 0; j < i; j++)
		exe(i,j)

\[1+2+4+...+2^{[log_2(n+1)]}=\sum_{k=0}^{log_2(n-1)}2^k \ \ \ \ \ \ \ \ (let\ \ k=log_2i) \\ =2^{[log_2n]}-1=\Omicron(n)\]

上面这段等效于一个几何级数的形式，它的最大值是由n决定的。我们可以用代数的形式估算，也更推荐用直观的几何方式把复杂度绘制出来。这些方法都可以推广至一般性的办法。来看下面的问题，找出非极端元素。

\[给定整数子集S，|S|=n \ge3 \\ 找出元素a\in S，a \ne max(S)且a \ne min(S)\]

因为集合具有互异性，所以任取三个元素肯定也是互异的。剩下的两步就是排除掉最小和最大，剩下的肯定是非极端元素，同时也是源子集的非极端元素。不过，这个算法无论输入规模多大，所需要的执行时间都是不变的常数。

再看一个更一般的例子：起泡排序。任务是给定n个整数，将它们按(非降)序排列。我们能观察到的现象是有序/无序的序列中，任意/总有一对相邻元素顺序/逆序。所以算法的思路就是逐步消除这种相互紧邻的逆序元素。方法之一就是通过所谓的扫描交换，反复的去扫描这个序列，每扫描一趟，发现了逆序的紧邻元素就将二者位置交换，直到某趟没有发现类似的逆序对，就可以终止。否则将会一直持续下去。

整个起泡排序的计算过程可以精确的描述为这样一段代码，是典型的二层循环模式，外循环对应的就是一趟一趟的扫描交换，而内循环执行扫描交换。在每次内循环中，代码会逐一检查每一对相邻的元素。如果它们是逆续的，就会令二者交换位置。

void bubblesort(int A[], int n) {
	for (bool sorted = false; sorted = !sorted; n--)  //逐趟扫描，直到完全有序
		for (int i = 1; i < n; i++)    //自左向右，逐对检查A[0,n)内各相邻元素
			if (A[i-1] > A[i]) {   //若逆序，则
				swap(A[i-1], A[i]);  //令其交换，同时
				sorted = false;      //清除全局逆序标志
			}
}

接下来还是存在一个问题，就是如何证明上面这个算法必然会结束？它至多需迭代多少遍？换言之就是算法正确性的证明。首先基于算法的不变性，经k轮的扫描交换之后，最大的k个元素必然会就位，很明显这是正确的。这个过程中也蕴含了单调性。经k轮的扫描交换之后，问题规模缩减至n-k。所以由这两条，我们就可以得出结论。这个算法必然会正确的结束。考察它终止的边界情况，当k等于n时，不变性就可以翻译为经过了n轮扫描交换之后，最大的n个元素，也就是所有元素必然会就位。

通过挖掘并综合算法所具有的不变性和单调性，进而证明正确性的方法，是算法分析中的一个基本且重要的技巧。

除了大O记号这种定性的定界方法，我们在很多时候也需要进行准确定量的估算。而这种估算的重要方法之一就是Back-Of-The-Envelop-Calculation，即封底分析。这种估算几乎不需要笔纸等工具，而是在头脑中抓住问题的主要方面，就可以很快得出足够近似的估计。费米，古希腊的阿拉托斯顿尼都是这方面的大师。无论是物理学还是几何学，之所以能成功应用这种方法，关键都在于他们善于抓住问题的主要方面，从而简洁的得出这个问题的总体规律，我们也可以很自然的运用到复杂度的分析过程中。

由于对象变成了时间，因此我们对很多时间量都要建立起直接的概念。

1天 = 24hr * 60min * 60sec = 25 * 4000 = 10^5sec

最基本的计算单位是秒，CPU一秒钟大概是10^9次运算，而1天，将24估为25，最后是10^5秒。
1生 = 1世纪 = 100yr * 365 = 3 * 10^4 day = 3 * 10^9 sec
“三生三世” = 300yr = 10^10 = (1 googel)^(1/10) sec

…

而硬件和算法，我们在改进硬件和改进算法之后，哪个威力更强也是显而易见的。

e) 迭代与递归

前面已经围绕迭代进行了程序的复杂度分析，并介绍了一般性的方法和技巧，概括而言就是级数求和。这次我们将注意力转向递归程序。

To iterate is human, to recurse, divine. 迭代乃人工，递归方神通

递归更加高明，可以让我们更敏锐的抓住问题的要害，从形式上有更简便的解决办法。虽然从效率上讲，递归的形式并不是一个最佳的方案，而貌似复杂甚至有点笨拙的迭代式算法往往在实际的运行效率上体现出更强的优势。因此如果说此前你追求的境界是从简单的迭代慢慢的学会利用递归，那么现在我们又开始一个螺旋式的上升过程，要慢慢的从递归的程序转向为一种更加高效迭代。

从这里开始，我们要慢慢的转向另一个话题，也就是在能够逐步了解和评判数据结构和算法的性能优劣之后，我们要学会如何设计一个高效的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) {
	int sum = 0; //O(1)
	for (int i = 0; i < n; i++) //O(n)
		sum += A[i]; //O(1)
	return sum;  //O(1)
}

我们可以设置一个累加器，初始化后开始循环。每一次循环都会将相应的元素累加其中，最后将这个累加器返回。

\[T(n)=1+n*1+1=n+2=\Omicron(n)=\Omega(n)=\Theta(n)\]

它的复杂度很容易看出来，从渐进的意义上讲，几个初始化的部分，没有循环的语句都可以忽略掉，而实质部分都是来自于中间的循环，每一步的时间都是常数。所以最终是O(n)。这里所需要的空间是多少呢？凡是谈论到空间复杂度，我们都是在考量除了输入本身所占的空间外，额外用于计算所需的空间总量。这里就是累加器和内部循环的控制变量所需的空间，一共是O(2)，常数。

这段代码本身平淡无奇，但它的价值在于其背后蕴含着某种典型的规律。如果把输入参数中的n看作是这个问题的规模，那么我们会发现，每经过一次迭代，剩余的有效问题规模就会相应的递减。这种通过逐步蚕食不断削减问题有效规模的策略。就是减而治之。

为求解一个大规模的问题，可以将其划分为两个子问题：其一平凡，是退化后的常见问题，另一规模缩减。分别求解子问题，由子问题的解得到原问题的解。其中关键就是规模缩减后的子问题的形式与原问题依然保持一致。这时我们就可以递归求解，然后将解合并，从而得到最初原始问题的解。这样的策略就是减而治之。

sum(int A[], int n) {
	return
		(n < 1) ?
			0 : sum(A, n-1) + A[n-1];
}

如上是一种可能的实现方法，采用的是递归的形式，套用减而治之的策略。首先在空间上将规模缩小了一个单元，然后递归前者，后者本身是一个平凡问题，可以直接得到。最后将二者的解合并，当问题规模缩小到足够小后，它自身也成为了平凡问题。这个算法的正确性也毋庸置疑。那它的复杂度是多少呢？

我们来介绍递归算法分析的第一种主要技巧，也就是递归跟踪分析。具体来说忽略一些调用语句，检查每个递归实例。既然是减而治之，为了求解规模为n的问题，算法会生成一个规模为n-1的问题，进而不断降解直到规模退化到0。我们将这些实例连接成一个队列，累计所需时间(调用语句本身，计入对应的子实例)，其总和即算法执行时间。如此统计后，作为一个严格线性的过程，总体是显然渐进的，有线性个。

\[T(n)=\Omicron(1) * (n+1) =\Omicron(n)\]

上面的这种递归是最简单的形式。因为一个递归实例本身只会生成一个实例，所有这些实例都可以排成线性的次序。即线性递归。我们可以发现递归跟踪的应用范围非常有限，它的概括能力还不够强。为了更好的分析一些一般性的，复杂的递归函数复杂度，我们就必须使用更加强有力的方法。

如果递归跟踪是几何方法，那么递推方程就是纯粹的代数方法了。我们从递推的角度看整个算法的过程，即：

递归求解规模为n-1的问题sum(A, n-1) → T(n-1)
累加上A[n-1] → O(1)
还有递归基：sum(A, 0) → O(1)

整理成递推方程的形式，即：

\[\begin{cases} T(n)=T(n-1)+\Omicron(1)\\ T(0) = \Omicron(1) \end{cases}\]

第一个式子可以理解为是首先花了T(n-1)的时间去求解了一个规模为n-1的问题，然后再花上O(1)的时间将n-1规模问题的解和平凡问题的解合并，从而得到原问题的解。这就是递推方程，也可以很形象的比喻是解微分方程，我们需要去求解一个方程的显式形式，但目前我们知道的只是它以微分形式给出的隐式表达，所以不妨把这个隐式的表达作为方程列出来，再加上边界条件，通常情况下就应该能够得到唯一解。

就这个问题而言，我们可以来求解一下，非常容易。

\[T(n)- n=T(n-1)-n+1=T(n-1)-(n-1) \\ =T(2)-2=T(1)-1=T(0)\] \[故T(n) = \Omicron(1)+n=\Omicron(n)\]

我们再来看减而治之策略的另一个典型的应用。

例如，任给数组A[0, n)，将其前后颠倒。(或者更一般的，子区间在[lo, hi])

这里给出统一的接口：void reverse(int* A, int lo, int hi);

下面是递归版。

if (lo < hi)    //问题规模的奇偶性不变，需要两个递归基
	{ swap(A[lo], A[hi]); reverse(A, lo + 1, hi - 1);}

如果low和high之间还有足够多的元素，没有到退化的情况，我们就将当前的low和high彼此互换。接下来递归的去求解一个规模更小的问题，这个问题从数组的范围来说就是从low+1项到high-1项。为什么这是减而治之呢？因为可以认为通过这样一次O(1)时间的操作能将问题的规模在原来的基础上减少两个元素。当然这里隐含一个相当于return的else，这部分就是隐含的递归基。那就这个问题而言，递归基能否应付所有的情况？

实际上这里有两种情况要解决，关键就在于区间的宽度。经过减而治之后，虽然区间宽度有所减少，但每次减少的都是两个单位，所以它的奇偶性是不变的，在最终的情况，会有最小的奇数单个元素以及最小的偶数，也就是零个元素，这两种情况。所以那个不可见的else就是发挥这种作用的，这里不再赘述。

这个算法的正确性也可以用递归跟踪分析。当然这个问题还有别的版本，比如迭代版，甚至还有更精简的迭代版。

//迭代原始版
next:
	if (lo < hi)    
		{ swap(A[lo], A[hi]); lo++; hi--; goto next;}
//迭代精简版
while (lo < hi) swap(A[lo++], A[hi--]);

不过我们还是把注意力放在递归算法这里，这样一个正确的算法，不妨来重新应用刚才的方法来分析时间复杂度，并相互佐证。

另一种更加强烈的算法策略是分而治之。这个策略和刚才的减而治之颇为类似，但有本质的不同。分而治之策略在求解一个规模较大的原始问题时，可以将它分解为多个(通常是两个)子问题，规模大体相当。并同样沿用递归的策略求解这些子问题。一旦子问题们的解得到了，再通过合适的办法归并，从而得到原始问题的解。

还是回到刚才所讨论过的数组元素求和的问题，并做一下推广。对于任何给定的数组A，求和的范围是从low到high。

sum( int A[], int lo, int hi) { //区间范围是lo到hi
	if (lo == hi ) return A[lo];
	int mi = (lo + hi) >> 1;
	return sum( A, lo, mi ) + sum( A, mi + 1, hi );
} //入口形式为sum( A, 0, n-1 )

首先处理递归基，即判断low和high是否已经足够接近。如果足够接近，那么问题的有效范围就只有一个单元，这样就直接把这个元素返回就可以了。否则，我们会通过一次右移操作在low和high之间取它的中点middle，进而将原来的问题分解为两个形式完全一致的子问题。这两个子问题的区间范围分别是low到middle，以及middle+1到high。对这两个子问题递归的求解后，通过加法合并，得到最初问题的解。这就是分而治之的策略，正确性是毋庸置疑的。

那么这个算法的复杂度是多少呢？继续沿用之前的两个方法。

首先是递归跟踪。为此我们需要画出所有的递归实例彼此调用的关系图。

0到7的求和问题被化简为0到3的求和问题以及4到7的求和问题，之后继续进行划分直到最后变成递归基的形式。我们接下来需要统计所有递归实例所需的时间总和，如果把递归调用语句本身忽略的话，程序不包括任何形式的的迭代。每一个递归实例，无论它所对应的有效区间是长还是短，都只需O(1)时间。所以只需将所有递归实例的总数统计出来就够了。可以经过代数的推导得出结果：

\[T(n)=\Omicron(1) * (2^0+2^1+2^2+...+2^{logn})=\Omicron(1)*(2^{1+logn}-1)= \Omicron(n)\]

实际上无需计算就可以得到同样一个结论。按照分层的关系而言，所有递归实例在每一层的总数是构成一个以2为倍数的几何级数，几何级数的总和与它的末项同阶。所以底层递归实例的总数就能代表整体的总数了。对于原始区间中的任意元素有且仅有一个对应的实例，所以原来区间有多宽，在底层上就会有多少个递归实例。即n个，O(n)。

采用递推方程的方法对算法进行分析。从递推的角度，求解规模从low到high的问题，实际上是将它分而治之化简为两个问题，一个是从low到middle，另一个是middle到high。若这两个问题的解通过递归获得了，只需对这两个解花O(1)时间进行累加即可得到原问题的解。此外还有对递归基的处理，当low等于high时，需O(1)时间将元素返回即可。

递归求解sum(A, lo, mi)和sum(A, mi + 1, hi) → 2 * T(n/2)
子问题的解累加 → O(1)
递归基：sum(A, lo, lo) → O(1)

\[\begin{cases} T(n)=2*T(\frac n 2)+\Omicron(1)\\ T(1) = \Omicron(1) \end{cases}\] \[T(n)=2*T(\frac n 2)+c_1 \\ T(n)+c_1=2*(T(\frac n 2)+c_1)=2^2*(T(\frac n 4)+c_1) \\ =2^{logn}(T(1)+c_1)=n*(c_2+c_1)\] \[故T(n) = (c_1+c_2)n-c_1=\Omicron(n)\]

减而治之和分而治之都是算法设计中的强力武器，至少在算法复杂度为常系数的方面，在采用分而治之的策略后能有所改进。

来看这样一个问题：能否在一个给定的数组区间A[lo, hi)中找出最大的两个元素？我们考量的标准是整个过程中进行元素的比较操作的次数尽可能的少。

//找出最大的两个整数A[x1]和A[x2]，要求元素比较的次数尽可能的少  A[x1] >= A[x2]
void max2(int A[], int lo, int hi, int & x1, int & x2) {  //1 < n = hi - lo  
	for ( x1 = lo, int i = lo + 1; i < hi; i++ )     //扫描A[lo, hi)，找出A[x1]
		if ( A[x1] < A[i] ) x1 = i;                //hi - lo - 1 = n - 1
	for ( x2 = lo, int i = lo + 1; i < x1; i++ )   //扫描A[lo, x1)
		if ( A[x2] < A[i] ) x2 = i;              //x1 - lo - 1
	for ( int i = x1 + 1, i < hi + 1; i++ )      //再扫描A(x1, h1)，找出A[x2]
		if ( A[x2] < A[i] ) x2 = i;           //hi - x1 - 1
}

上面这段程序是由三趟循环构成。第一轮循环找出最大的元素A[x1]，后两轮循环就是在A[x1]的前驱和后继中扫描，并找出A[x2]。如果low和high是非退化情况，那么第一轮循环总共是n-1次，后面两轮的总数很好判断。最后的比较次数是2n-3。

\[T(n)=\Theta(2n-3)\]

无论输入是多少，这个算法都需要做固定次数的循环。确切的说，比较总数是固定的。所以不存在最好和最坏的情况，而是只存在一种情况，即2n-3。

我们可以试图从另一个方面进行改进。思路是维护x1和x2这两个指针，让其分别指向当前最大和次大的元素。

//找出最大的两个整数A[x1]和A[x2]，要求元素比较的次数尽可能的少  A[x1] >= A[x2]
void max2(int A[], int lo, int hi, int & x1, int & x2) {  //1 < n = hi - lo  
	if ( A[x1 = lo] < A[x2 = lo + 1] ) swap(x1, x2);
	for ( int i = lo + 2; i < hi; i++ )
		if ( A[x2] < A[i] )
			if( A[x1] < A[x2 = i] )
				swap(x1, x2)
}

这次整个算法过程仅有一趟扫描。经过了初始化(将x1指向low，将x2指向low+1，即最开始的前两个元素，然后按照A[x1] >= A[x2]的约定进行一次比较判断)后，从第三个元素开始扫描。每到下一个元素时，都会先将它和A[x2]进行比较。如果比A[x2]要大，那么进而和A[x1]做比较，这样我们就会更新A[x2]乃至更新A[x1]，反之就保持不变。这样可以适当的减少比较次数。这段程序同样隐藏了else语句，就不再展开了。算法的正确性也是显然的，那么复杂度是否有所改进？我们着重关注循环中的比较次数，这时循环的长度是n-2，但内部执行的计算次数是不确定的。那么这里就存在好和坏两种情况。在最好的情况下，除了最初的初始化需要一次比较外，剩下的n-2循环每次都只需一次比较，结果就是n-1，相对于之前的2n-3貌似有很大的改进。而最坏的情况则每次循环内部都会触发两次比较，合计后依然是2n-3。换而言之，就最坏的情况而言。这样的一个结果表示算法并没有实质性的改进。

那么更高级的改进方案就是分而治之了，就算最坏的情况也严格小于2n-3。思路就是我们把整个序列划分为两部分，接下来递归的求解两个子问题，分别求出左侧的最大元素和次大元素以及右侧的最大元素和次大元素。接下来全局的最大元素必然来自于左侧的最大元素和右侧的最大元素之间的更大者。为此我们会花费一次比较，那么当然有两种情况，可能是左侧的胜出，也可能是右侧的胜出。由于两边是完全对称的情况，所以我们只需考虑一侧。如果左侧胜出，那么进而可以得出结论：全局次大的元素必然是来自于左侧的次大元素和右侧的最大元素。同样我们再经过一次比较就可以确认他们中间的胜者。

void max2(int A[], int lo, int hi, int & x1, int & x2) { 
	if ( hi <= lo + 3 ) { trivial( A, lo, hi, x1, x2 ); return; } //T(3) <= 3 
	int mi = (lo + hi)/2;   //divide
	int x1L, x2L; max2( A, lo, mi, x1L, x2L );
	int x1R, x2R; max2( A, mi, hi, x1R, x2R );
	if ( A[x1L] > A[x1R] ) {
		x1 = x1L; x2 = A[x2L] > A[x1R] ? x2L : x1R;
	} else {
		x1 = x1R; x2 = A[x1L] > A[x2R] ? x1L : x2R;
	}  //1 + 1 = 2
} //T(n) = 2 * T(n/2) + 2 <= 5n/3 -2
//可以继续借助数据结构来进一步的优化

算法当然存在退化的情况，这里是省略了。在经过等分之后取中点，并且递归的求解出刚才所说的A[x1L]，A[x2L]，A[x1R]以及A[x2R]。接下来就是比较了。可以写出递推式：

\[T(n)=2*T(\frac n 2)+2 \le \frac {5n} 3 -2\]

就n的常系数而言，如果是二的话，现在这里降为了5/3。这种下降即便在最坏情况下也能够保证。

f) 动态规划

DSA的设计与优化是一个复杂而艰辛的过程，同时也不乏规律可循。

Make it work, make it right, make it fast. - Kent Beck

整个过程也许应该分为三步。首先是让DSA能够运转起来，比如说对小型的问题至少能够工作。其次是要使得它的正确性得到保证。这两步可以通过递归算法的形式很好的解决。不过递归从效率上讲并不能总是令我们满意。所以最后，若是要讲究算法的效率，就应该用到迭代。

所谓的动态规划，其实可以理解为是通过递归找出了算法的本质，并且能给出一个初步的解，之后再将其等效的转化为迭代的形式。

第一个例子就是大家都非常熟悉的斐波那契数。

\[fib(n)=fib(n-1)+fib(n-2):\{0, 1, 1, 2, 3, 5, 8, ...\}\]

这本身就是一个递归的形式，因此我们很自然的将它转化为这样一个算法来计算斐波那契数的第n项。

int fib(n) { return (2 > n) ? n : fib(n - 1) + fib(n - 2); }

这段程序运行会非常慢。该如何解释这种现象？

首先采用递推分析的方法。

\[\begin{cases} T(n)=T(n-1)+T(n-2)+1 &n>1\\ T(0)=T(1) = 1 \end{cases}\]

算法相当于首先花T(n-1)的时间算出第n-1项，再花T(n-2)的时间算出第n-2项，后面那个1对应加法，将结果合并。边界条件就是对于第0项和第1项用O(1)的时间直接返回。求解步骤如下：

\[令S(n)=\frac {[T(n)+1]} 2 \\ 则S(0)=1=fib(1),S(1)=1=fib(2)\\故S(n)=S(n-1)+S(n-2)=fib(n+1)\\T(n)=2*S(n)-1=2*fib(n+1)-1=\Omicron(fib(n+1))\\ =\Omicron(\Phi^n)=\Omicron((\frac {1+\sqrt5} 2)^n)=\Omicron(2^n)\]

从渐进复杂度的意义讲，算法的时间成本呈现出一个指数增长。没错，又是指数。不同的是这次要对指数进行一个准确的估计，封底估算。黄金分割数有两个近似式：

\[\Phi^{36}=2^{25}\] \[\Phi^{5}=10\]

基于这样的大致估计，我们就可以来估计一下斐波那契数的第43项。就有下式。

\[\Phi^{43}=2^{30}=10^9 flo=1sec\]

也就是说，计算的工作量大概可以用10^9条基本操作指令来度量。而10^9条基本操作指令大约就是现在主流的计算机，主频CPU在一秒钟之内大致能够吞吐的计算量。所以到这步会有明显的延迟。这也就是为什么当我们的计算大致接近43甚至更大的时候，我们会明显的感觉到。延迟。同理，67项相当于1天，92项相当于三生三世。所以利用这个算法，即便是算不超过100项的数，我们就需要一生都难以承受之久的等待。这说明算法从严格的意义上讲，它甚至不是一个算法。

我们也可以采用第二种手段，也就是递归跟踪来分析。列出比如计算第5项所需的递归实例。可以发现，递归版fib()低效的根源在于各递归实例均被大量重复的调用。其实概括而言，每个递归实例只需要计算一次，只需一个就足够了。所以，在对递归实例去重后，总共剩下的不过是O(n)种，指数到线性的变化。

第一种改进方法是直接了当的，思路是在每次试图去生成一个新的递归实例时都会去检查一下是否已经被计算得出过相应的结果。如果是，那么就不必再重新唤醒，直接把原先的结果取出就可以了。这是最好的方法之一，我们称作记忆法。即将已计算过实例的结果制表备查，一旦需要去再次唤醒实例时，都会先去查表。从而在O(1)的时间内返回所需要的结果。这种方法非常好，不过对原来的程序的改进不是很大。

第二种方法更加通用自然。就这个例子而言，如果说此前递归的计算方向是从大到小，自顶而下的话，不妨倒过来改为自底而上。由原来的递归改进为迭代的算法。这就是动态规划：颠倒计算方向。代码很简明。

f = 0; g = 1;  //fib(0), fib(1)
while (0 < n--) {
	g = g + f;
	f = g - f;
}
return g;

每一次迭代都通过两句赋值语句更新变量f和g，使得它始终指向斐波那契数列中相邻的两项，以一种交替滚动的方式不断推进，直到得到最终的解。除了由n控制的循环外，没有其余能引起复杂度的部分。所以就是O(n)的时间。而且在这里只需要f和g两个存储单元，只需要常数的空间，即O(1)。刚才递归版程序空间的浪费也是相当惊人的。

再来看动态规划策略的另一个实例，即找出最长公共子序列。所谓的序列是由若干个字符构成。子序列是在一个序列中随意挑选出若干字符，并按照它们原来的相对次序重新拼成一个序列。公共子序列中包括最长公共子序列，需要注意的是有可能同时有多个最长的公共子序列，还可能出现歧义。例如，其中某字符在某原始序列中可能有两个字符都对最长子序列构成了贡献等等。这里我们只关注简单问题，即计算出任意给定两个序列的最长公共子序列的长度。

参考之前的工作流程，暂时把计算效率放在一边，先考虑得到一个可行的、正确的算法。为此，我们需要拿起递归这个强有力的武器。将问题形式化描述为：对于长度为n+1的序列A[0, n]和长度为m+1的序列B[0, m]，它们的最长公共子序列LCS(A, B)无非是三种情况：

递归基：n或者m为-1的情况，子序列为空序列。空序列的子序列只可能是空序列，所以作为公共子序列也必然是空序列。
若A[n] = ‘X’ = B[m]，则取作：LCS( A[0, n), B[0,m) ) + ‘X’。即减而治之策略。我们去比较A序列和B序列的末字符，如果末字符相等，即变成平凡问题，那么我们可以把两个序列的最后一项去掉，然后求剩余减少一个单元长度的两个序列的最长公共子序列，即规模小一点但形式完全相同的问题。这一对前缀如果能够递归的求解的话，那么在并上最末尾的公共的字符。这样就必然构成了原问题的解。
A[n] ≠ B[m]，则分而治之。在LCS( A[0, n, B[0,m) )与LCS( A[0, n), B[0,m] )中取更长者。假如A的末字符是x，B的末字符是y，这肯定是不匹配的。那么原问题的解只有两种可能，一种是y字符对整个公共子序列没有贡献，这样我们不妨把y切除掉。然后剩下的前缀和另一个序列构成一个子任务，继续递归求解，另外也需要对称的考虑另一种情况。当x对整个公共子序列的匹配没有贡献时，将x去除，前缀和另外一组序列构成一个新的子任务递归求解。这种情况下整个问题的解无非是两种情况。我们最终只需要在它们中取一个最长的解即可。

归纳这三种情况，实际上我们已经得到了一个完整的递归算法，而且所有的递归操作都是封闭的。具体实现暂时忽略，现在需要分析的是这个算法的正确性以及效率。我们会发现效率并不是很好。

这部分的解释暂时省略吧…莫得精力了… LCS 理解.mp4

未完待续。