算法设计怎么做，分析步骤要求详解？

算法分析与设计基础

第一章， 绪论：

1、 一个人只有把知识教给别人，才能真正掌握知识。将知识表示成为一种算法，知识是一种高度浓缩的信息，算法的本质是应用知识解决问题的过程；输入是信息，

2、 算法的定义：一系列解决问题的明确指令，符合一定规范的输入能够在有限时间内获得要求的输出；性质：没有歧义、输入符合要求、有限时间、期望输出；算法描述形式多样、算法和问题之间是多对一的关系；

3、 算法求解的基础：理解问题、了解设备的性能、在算法之间做出选择、算法设计技术、确定数据结构、描述算法、算法正确性证明、算法效率的分析、编写实现的代码；

4、 算法解决的重要的问题类型：

a) 查找

b) 排序

c) 字符串处理

d) 图问题：商旅问题（求最优路径）、图填色问题；

e) 组合问题（计算领域最难的问题，随着问题规模增加，组合对象数量级增加，目前还没有一种已知算法可以在可接受时间，精确的解决相关的问题；

f) 几何问题：最近对问题、凸包问题（求一个能把给定集合所有点都包括在内的凸多边形）

g) 数值问题：求解方程和方程组，计算定积分、函数求值，最大的困难在于计算机无法精确表示实数，误差累计无法避免的叠加。

5、 基本数据结构

a) 线性结构：数组、链表（单链表、双链表）、栈（LIFO）、队列（FIFO）、优先队列（从动态改变的候选集合中选择一个优先级高的元素，堆是其中一个很好的实现方式）

b) 图，包括两个集合，顶点集合、边集合：顶点、边、无向图、有向图、完全图、稠密图、稀疏图；图的表示法：邻接矩阵、邻接链表；加权图，权重矩阵；路径和环：连通性、无环性、简单路径（路径中的顶点不重复）、路径长度（边的数量）、有向路径、连通图（每一对顶点都有一条路径相连）、回路、无环图

c) 树：有根树、根、自由树（连通无回路图）、森林（无回路但不一定连通）、祖先、真祖先、父母、子女、兄弟、真子孙、节点深度、树高度、有序树、二叉树、二叉查找树、多路排序树、先子女后兄弟表示法；

d) 集合与字典：抽象数据类型（表示数据项的抽象数据对象集合和一系列对这些对象做的操作构成）ADT；

第二章， 算法效率分析基础

1、 分析框架：时间效率、空间效率；主要分析的是算法的时间、空间效率；

a) 输入规模：

b) 运行时间的度量：基础运算的次数来度量；

c) 增长的次数：算法的运行效率log<n<nlogn<n2<n3<2n<n!(一个需要指数级操作次数的算法只能解决小规模的问题，logn级的算法可以应付所有大规模的问题)

d) 算法效率：最优、最差、平均效率

2、 渐进符号和基本效率类型

a) 渐进效率就是算法的上届，能够接近的规模，基本的量级：常数、对数、线性、线性对数、平方、立方、指数、对数。从效率来讲又快到慢，指数级的算法最慢；

3、 非递归算法的数学分析

a) 非递归算法的数学分析是有意义的，因为递归算法是其同类型小规模问题的迭代；非递归算法的数学分析针对不同类型的问题有不同的效率评价；

b) 非递归算法数学分析的一般步骤：

i. 决定用哪些参数表示输入规模（N的表达，数量？集合？还是对象）

ii. 找出算法的最基本步骤，即算法中频率最高的执行语句（至少执行一次）；

iii. 检查基本操作的执行次数是否只依赖于输入规模；是否可以用n的函数来表达算法执行的效率；

iv. 建立一个算法基本操作执行次数的求和表达式；

v. 利用求和运算的标准公式和法则来建立里一个操作次数的闭合公式，或者至少确定它的增长次数；

4、 递归算法的数学分析

a) 分析递归算法的时间效率的通用方案：

i. 决定用哪些参数表示输入规模（N的表达，数量？集合？还是对象）

ii. 找出算法的最基本步骤，即算法中频率最高的执行语句（至少执行一次）；

iii. 检查一下，对于相同规模的不同输入，基本操作的执行次数是否可能不同，如果有这种可能则必须对最差效率、平均效率和最优效率做单独研究；

iv. 对算法基本操作的执行次数，建立一个递推关系以及相应的初始条件；

v. 解递推式，或者至少确定它解的增长次数；

vi. 汉诺塔问题的递推公式：M（n）=2M(N-1)+1=2N-1;从汉诺塔问题的解法看出来，它是将输入规模为n的问题变成了一个输入规模为2N的问题，从道理上看，它是将原来输入规模扩大了，而不是减少了，所以问题的解题时间为2n，是不是可以有这样一个推论？任何扩大输入规模的算法都不是最优的。

vii. 斐波那契数列：f(n)=f(n-1)+f(n-2)=(an-a-n)，也是一个指数级的算法啊a=1.618；输入n=2n-3; n>3的时候，2n-3>n；

5、 算法的经验分析

a) 通常可以用经验的方法对算法的效率进行分析，建立操作图-输入规模的函数关系，可以大致评估算法的渐进效率，属于那种类型。线性？指数？平方？等等；

6、 算法可视化技术

a) 通过将算法的过程已动画的方式呈现出来，发现算法计算的规律，达到优化算法的目标；（用于教学等方面）

第三章， 蛮力法

算法的三个要素：模型、策略、计算方法。对问题建立数学模型，针对模型的特点选择解决方案的策略，最后根据策略实现算法的性能。对于相同的模型（问题），往往有多种策略可以选择，从多种可能的策略中选择最优的策略后，选定和优化实现的算法，正是算法设计的最核心的问题。任何可以用输入-处理-输出建模的事物，都可以视为算法设计的过程，所以算法是最贴近道的东西，足够抽象。输入是1，处理是2，输出是3。道家中说的道生一、一生二、二生三、三生万物；也可以理解为，这个世界每天都会从无生出很多问题来，这些问题的处理策略就是二，策略的具体落地（算法）就是三，由算法产生了无穷无尽的多样性。

把事情做好往往是浪费时间。

蛮力法：是一种简单直接的解决问题的方法，常常直接基于问题的描述和所设计的概念定义。蛮力策略也常常是最容易应用的方法；这里的力既指计算机的计算力、也可以指广义的能力（动物、植物、人类）等等，人类对信息处理有着多样化的策略，所以导致了人类处理信息的效率更高；看到了别人看不到的东西，这个才是你的竞争优势，下棋一样，你总是比对手能多看2步，别人是无法战胜你的。

有时在没有其他方法的时候，蛮力法总是一种可行解。也是一种重要的问题解决方法。它可能是唯一一种几乎什么问题都能解决的一般性方法。面对N中选择的时候最简单的方法就是一个个去试；蛮力法应是你工具箱中保留的重要工具（1、几乎能解决所有问题；2、对一些重要的问题如排序、查找、矩阵乘法和字符串匹配，它可以产生合理的算法，而且不必限制算法的输入规模；3、如果要解决的问题实例不多，输入的规模有限，它可以在能接受的速度范围内对实例求解；4、即使效率很低，仍然可以用蛮力法解决一些小规模的问题；5、蛮力法可以用于教学）

看一个人处理问题的方式就知道他处于算法的那个等级，蛮力的人算法的效率很低，往往用穷举的方式来试错；就想我们解决层流不稳定的问题，一项一项的试，对简单问题通常有效，但是对复杂因素构成的复杂问题来讲，往往是徒劳的，会导致筋疲力尽。对问题的认识，决定了处理的手段。

an=a*a*a*a….，需要时间为n次

1、 蛮力法适用的范围：

a) 问题的输入规模小；

b) 问题的实例规模有限，处理问题的时间可以接受；

c) 某些特殊问题的解法，排序、查找、矩阵乘法、字符串匹配；

d) 无计可施的情况下使用；

e) 教学和研究目的；

2、 选择排序和冒泡排序

a) 选择排序：扫描整个输入空间，找到最小元素进行排序；算法复杂度n+n-1+n-2=n(n-1)/2，n2规模的；

b) 冒泡排序：比较相邻元素，逆序的话就交换位置；算法也是n2难度的；

通常：蛮力法的第一个应用可以得到一个算法，此算法可以通过适度的努力来提升的的性能；进行一些算法上的优化，有可能会有效率上的提升；

3、 循序查找和蛮力字符串匹配

a) 顺序查找：简单的将给定列表中的连续元素和给定的查找键进行比较，直到找到对象；（算法是线性的，n）；

b) 蛮力字符匹配：从左到右，扫描整个文本，找到对应的值；（算法是n*m）

4、 最近对和凸包问题的蛮力算法

a) 最近对问题：要求在一个包含N个点的集合中，找出距离最近的两个点；扫描所有的点对，找出最小的值（n2查找+n次比较，综合n2）

b) 凸包问题；在平面或者高维空间的一个给定点集合中寻找凸包（最小凸多边形，n头熟睡的老虎围起来，胶合板上钉子用皮筋全部围起来）；用定义来求，当且仅当该集合中的其他点都位于这两点的直线的同一边是，他们的连线是凸包边界的一部分—遍历集合所有的点对，求（n2输入规模，对每一个输入都要做n次距离计算，算法效率应该是n3）ax+by=c，时间内能够实现的。

5、 穷举查找

a) 组合问题：要求在一个复杂度随着实例规模指数增长的域中，查找一个具有特定属性的元素。Y=2n。比如旅行商的最优路径的问题，从一个点出发到若干个城市，求最优路径。当城市的节点增加时，增加的路径是组合数增长的.

b) 组合问题的蛮力法：穷举查找，指生成所有实例的解，从中优选，但生成实例是指数级的，所以算法至少是指数级的。

c) 旅行商问题：求出一条n个给定城市间的最短路径，使我们在回到出发的城市前，对每个城市都只访问一次。问题的输入是什么？城市的数据么？不对，而是城市的路径数。上述问题可以表述为一个一个图的汉密顿回路。组合问题，约束为不重复，最短路径）

d) 背包问题：给定n个重量为w1…wn的价值为v1…vn的物品和一个承重为W的背包，求这些组合中最有价值的一个。组合问题，约束为总重量。（NP完全问题、NP难问题，无法在多项式时间内求解）

e) 分配问题：有n个任务要分配给n个人执行，每个任务只分配给一个人，每个人只能分配1个任务，找出总成本最小的方案；组合问题，任务和人一一对应，总成本最小；（匈牙利法，可以得到比穷举效率高的多的方法）

f) 问题域的以指数增长的这个事实，不一定意味着没有更有效的解题方法；

g) 深度优先、广度优先查找（穷举查找的重要应用）：

i. 深度优先：以深度的方式遍历图的所有点和所有边；（用邻接矩阵来表示的，算法效率顶点V2，邻接链表表示：V+E；如果稀疏的话，用邻接链表来表示图。深度优先可以检查图的连通性，如果深度优先算法遍历了图的所有顶点，就是连通的，否则就是不连通的；可以检查是否有回路，两次遍历的边集合不同就可以认为是有回路的？）

ii. 广度有限：以广度的方式遍历图的所有点和所有边；算法效率与深度相同；

第四章， 减治算法；

预言：蛮力算法的大力士会直接拔马尾，而瘦弱聪明的士兵则一根根的拔马尾；

减治算法的核心是减少问题域的规模，通过求解一个更小的问题域，叠加解的方式来解决问题；糖衣炮弹，就是逐步的腐蚀一个人的最好方法，一次很难打到，就用小恩小惠多分几次的方式来达到目的；

减治：自顶向下方法（递归），自底向上的方法（迭代）；

减治法的三个主要变化形式：

l 减去一个常量

l 减去一个常量因子

l 减去的规模是可以变的

减常量：每次算法迭代，从实例中减去一个相同的常量F(N)-F(N-1);

减常因子：每次算法迭代，从实例中除去一个常量f(n)-f(n/2)

减去的规模是可变的：每次算法迭代，从实例中减去的规模是变化的gcd(m,n)=gcd(n,m mod n);

1、 插入排序：假设n-2个数已经排好，n-1个数扫描排好序的数，遇到第一个小于n-1的数时插入；（最坏情况下，算法的复杂度n2），类比：冒泡、选择排序；

2、 拓扑排序：

a) 有向图的拓扑排序问题：找到一种排序方式，使得对于图中每一条边，边的起始顶点总是排在边的结束顶点之前。如果有向图有一个有向的回路，则该题无解。

b) 第一种方式：深度优先查找，记住顶点变成死端的顺序，改词序反过来就是；

c) 第二种方式：减治算法的方式，在余下的图中求出一个源，是一个没有输入边的顶点，然后把从它出发的所有边删除，如果这样的源不存在，算法结束；

3、 生成组合对象：

组合对象的数量一般来说呈指数增长，有时会更快；

a) 减少常量算法：

i. 生成排列：运用减治思想，求n!，将n插入n-1！中，从左或者从右边插入；（算法的时间效率，基础运算是交换，算法的复杂度是（n!）

ii. 生成组合：类似背包问题，求一个物品中最有价值的子集。一个集合子集个数是指数的，减治的思想是，可以将an背包问题看成an,an-1两组集合；将an加入到an-1的所有子集就是an的子集。N个元素的子集和2n的位串一一对应；

b) 减常因子算法（通常有对数效率）

i. 折半查找：对于有序数查找，折半查找法是一种优秀的方法；基于递归思想，把每次把输入减少一半（logn）

ii. 假币问题：n枚外观相同的硬币，其中有一枚是假币，问最少几次就可以找出；logn；

iii. 俄式乘法：假设n和m是两个正整数，我们要计算他们的乘积；n*m=n/2*2m偶数时；是奇数时（n-1）/2*2m+m，停止条件为1*m=m；

iv. 约瑟夫斯问题：n个人围城一圈，每次消去第二个人，直到留下一个幸存者；那个幸运号码是多少。J（k）=j(k/2)+1;J(k/2)-1；

c) 减可变规模算法：

i. 每次减少的规模都不同；

ii. 选择问题：求一个ｎ个数列表中第Ｋ个最小元素问题；称为第ｋ个顺序统计量；快速选择法求解：将集合划分为两个部分，当ｓ＜ｋ－１时，ｋ小在右侧，（Ｋ－Ｓ）个元素中，当ｓ＞ｋ－１，ｋ在左侧（１－Ｓ）中。最好情况下（效率是ｎ），最坏情况下为（ｎ２）划分方法的效率依赖于平均情况，

iii. 插值查找：查找有序数组的算法，总是把查找键和给定有序数组的中间元素进行比较，因此问题减少了。

iv. 二叉树的查找：对于二叉树来讲，每一次迭代要么就等于节点，要么在左子树，要么在右子树，对输入规模都是减半的。（最坏效率是只有一边，平均为ｌｏｇｎ）

v. 拈游戏：有一堆ｎ个棋子，两个玩家轮流从堆中拿走最少１个最多ｍ个棋子，如果每个玩家都做了最优的选择，那个玩家能最后胜利？先走的还是后走的。当且仅当ｎ不是ｍ＋１的倍数时，ｎ个棋子是一个胜局；

第五章， 分治算法；

1、 将一个问题划分为同一类型的若干字问题，子问题的规模相同，对子问题求解，有必要的话合并子问题的解；不是所有的分治算法都比蛮力算法更高效，但是分治算法可以将问题分为两个子问题，实现并行计算来提高效率。分治算法的通用递推公式f(n)=af(n/b)+a(n);有定理可以证明，分治算法的效率，而不需要指导具体的算法；（如果fn=(O(nd),nd,ndlogn,nlogba）

2、 合并排序：是分治算法的一个典型的完美例子；对于一个要排序的数字，合并排序将其一分为二，对两个子数组分别排序，然后合并。理论上的效率（nlogn）

3、 快速排序:快速排序按照元素值进行集合划分，而不是位置，与合并排序有所区别；将集合划分为大于S和小于S的，算法的主要工作都在集合的划分上，而合并排序主要在排序上；算法复杂度（n2，nlogn），处理随机排列的数组时，比合并排序快；

4、 二叉树的遍历：分治算法遍历二叉树；遍历左子树，遍历右子树，遍历中间节点；前序、中序、后序；

5、 大数乘法和strassen矩阵乘法：

a) 大数乘法：蛮力算法（n*n，n2）,分治理算法处理：将大数分成为前半部分和后半部分a1a0*b1b0，求出算法的效率nlog23<n2

b) 同理，矩阵的乘法也可以用分治的思路进行优化：用7次乘法，18次加法，替代8次乘法；当矩阵的阶无穷大的时候，算法表现出卓越的性能；

6、 用分治算法解最近对问题和凸包问题：

a) 最近对问题：蛮力算法（n2）,可以将最近对分为两边，分别求最近距离，以及与中间的的距离进行比较；关键是分治策略的合并项的算法往往是线性的，优于直接计算；

b) 凸包问题：快包解法，就是把原来的凸包分成上包和下包，两个子问题，分别求解；解决划分的问题，效率与快速排序差不多（n2）,快包算法的平均效率是线性的。

c)

第六章， 变治算法；

1、 变治算法是基于变换six爱那个，变换同样问题的一个更简单或者更方便的形式，比如信号处理的傅立叶变换，将时域变换为频域的表示；称之为实例简化；羊毛出在猪身上让狗买单的商业模式，不正是变治思想的很好应用么？如何做好产品，似乎也可以形式化为一个标准；

2、 预排序：

a) 预排序是一个很古老的思想，排序算的兴趣根源来自于如果一个事情是有序的，许多关于列表的问题更容易求解。显然，由于包括了排序操作，这种算法的时间效率依赖于所选用的算法的效率。排序算法中选择、插入、冒泡都是n2的，快速和合并排序是nlogn的，还有没有更快的方法呢？

b) 检验元素中的唯一性：排序后，有没有连续出现的元素；

c) 模式计算：排序后，发现等值元素；

d) 查找问题：排序后，用折半的方法来进行查找；

将一个看上去复杂的问题转化为排序问题进行求解；

3、 高斯消去法：

a) 线性方程组有很多解法，高斯消去法是应用线性变换将方程组的系数矩阵变成上三角矩阵后，自下而上的迭代求解；也是对原来的问题进行了变换以后进行求解；

b) 适用范围：方程组有唯一解的时候可以用；最大的问题在于累计的误差，因为计算机的精度会导致舍入误差的累计；

c) 变形：LU分解，AX=B等价于 LUX=B；L：主对角线上的值都变为一的下三角矩阵；U是高斯消去的结果；y=UX，LY=B；就是LU分解。

d) 算法效率：高斯消元法分为两个阶段，第一是消去，第二是代入（反向替换），第二步的时间效率是（n2）

e) 主要应用：计算矩阵的逆矩阵，逆矩阵实际上就是矩阵的倒数；如果拟矩阵不存在成为退化矩阵；用高斯消去法检查是否退化；理论上N个变量就要有N个方程才可解，如果N个变量，只有N-1个方程，则方程组无解或无穷多个解（N个变量有N-1个自由度，有一个变量无约束）；计算矩阵的行列式：一个上三角矩阵的行列式等于它主对角线上元素的乘积；

4、 平衡查找树：

a) 如果二叉树是不平衡的，极端情况下全部在一个分支，则二叉树的算法效率变差（logn – n）,解决这个问题就是在构建二叉树的时候使其达到平衡，提升二叉树的查找效率；

b) 简化方案：1、实例简化，将不平衡的二叉树变为平衡，左右子树高度差不能超过1，AVL，变换的方式-旋转；2、改变表现的类型，允许查找树的单个节点中包括不止一个值；2-3树，2-3-4树；B树；

c) 核心就是：解决查找树的不平衡问题，2

5、 堆和堆排序

a) 堆：适合表示优先队列；堆是一颗二叉树，树的节点满足：完全性，每一层都是满的；父母优势：节点键值大于子女的键值；可以用数组来实现堆；

b) 应用场景：操作系统的作业调度、通信网络中流量的管理；

c) 堆构造：自底向上、自顶向下（算法效率n）

d) 堆排序：包括两部，第一是构造堆，第二步删除最大；算法效率（n+nlogn），比快排慢，与合并排序可比；

堆排序，首先将问题构造成为一个堆，再进行排序；这就是堆排序的核心思想，变治思想；

6、 霍纳法则和二进制幂

a) 问题：多项式的高效计算。在数学上，某点的函数值可以用在该点的泰勒展开式来近似，这个展开式就是一个多项式。目前最重要一种算法是快速傅立叶变换的方法，基本思想是用多项式在某些特定点上的值来表示该多项式；p(x)=an(xn)+an-1（xn-1）。。。+a0

b) 霍纳法则：是一个古老的计算多项式的算法，是一个很好的改变表现的技术；p(x)=(。。。（anx+an-1）x)+….)x+a0；算法效率（n）;

c) 二进制幂：在求n的二进制幂的时候，将霍纳法则变成a为底的指数表达式；

7、 问题简化：

a) 是一种重要的策略，解决一个问题可以将其化简为我们知道如何求解的其他问题；原则是简化后的解题效率要比我们直接解题简单；

b) 求最小公倍数：求两个数的最小公倍数；化简为计算两个数的乘积除以最大公约数的算法；

c) 计算图中的几何路径：求I,j之间的长度为K的路径数量问题，转化为求该图邻接矩阵k次方的I,j元素的值的问题；矩阵乘法；

d) 优化问题的求解：假设我们必须求某个函数FX的最小值，并且我们知道最大值的求法，可用minf(x)=-max[-f(x)]来转化；求函数极值点的过程也是一个标准的化简过程，通过求函数的导数，并另其为0，得出的。新的问题主要是解方程；

e) 线性规划：许多决策最优化问题都可以简化为线性规划问题的一个实例；线性规划问题是一个多变量线性函数的最优化问题，这些变量满足的一些约束是以线性等式或线性不等式的形式出现的；通常的形式是一个需要求解的优化函数（模型），和一组约束（等式、不等式）构成的；解决线性问题的经典算法单纯形法，最差效率为指数级、多项式（最新）的，但是在典型输入时表现很好；（只能处理变量范围为连续的问题），对于整数线性规划问题要难的多，目前还没有一个多项式级的解法输出(0,1)背包问题；

f) 简化为图问题：

i. 可以把许多问题简化为一种标准的图问题，比如google的pagerank算法，就是将检索问题变成了一个图问题；可以变成一个求初始状态顶点到目标状态定点之间路径的问题；（农夫、羊、狼、白菜，过河的问题，农夫每次只能带一样东西过去，问如何走才能全部带过去），羊吃白菜、狼吃羊；变成了一个图的最短路径问题；

第七章， 时空均衡算法；

算法中的时空权衡是一个核心问题：计算函数值的问题，可以将计算的结果记录在表中，通过查表求的；也可以用算法来直接计算函数值；存储结果使用的就是空间，通过增加中间的存储环节，可以优化算法的时间效率；可以看成是对问题的部分或者全部输入做预处理，也成为输入增强。空间换时间的典型例子就称为：动态规划，它的基础策略是把给定问题中重复的子问题的解记录在表中，然后求的解。时间和空间也不是完全对立的，必须要牺牲空间才能提升效率，某些情况下也可以联合起来，达到无论是时间还是空间都被优化的情况，如图遍历的问题，遍历的效率依赖于表示图的数据结构，邻接表对边的数量不多（稀疏矩阵）的情况下，可以同时优化时间空间O（V+E）.另外，数据压缩的主要目的是节约空间，而不是作为解决问题的一项技术。

1、 计数排序：策略，针对带排序列表中的每一个元素，算出列表中小于该元素的元素个数；并把结果记录在表中；设计一张计数表，每遇到个小于它的数就会加一，最后按照最后的计数排序；(比较计数排序)，算法效率（n2）,移动次数最少，直接得到了它的位置；分布计数排序：利用输入出现频率进行排序称为分布排序，

2、 字符串匹配输入增强技术：

a) 传统的字符串匹配技术采用蛮力法，将待匹配的字符串逐个后移动；

b) 增强的字符串匹配技术，采用一个跳跃计数表，比如遇到某个待匹配字符串的时候移动多少个位置，可一个大大加快扫描速度；

c) Horspool算法：根据模式匹配的情况移动字符串，最坏情况下O(nm)；

d) Boyer-Moor算法：会参考两个值来移动，坏符号移动，与Horspool，好后缀移动；增加了两个表来优化算法。算法效率(O(n))

e) 散列法：把键值分布在一个称为散列表的一维数组中，通过计算每个键值的散列函数来完成这种分布；散列算法需要处理碰撞问题，包括两种，一种是开散列、一种是闭散列；开散列是将每个散列值的存贮为一个列表，冲突的元素存储在列表中，查找的效率取决于链表的长度；闭散列，不使用链表，冲突后将元素顺序存储在后面那个单元格里（称为线性探查，但是如何避免当下空，后续不空的情况那？），查找和插入是简单的，但是删除是困难的；还有一种机制就是重散列，将前序键重新放到一个更大的表中；与平衡树查找相比，不适合按序遍历和按范围查找的需求；最好效率为O(1),最差效率O（n）,平衡树均为(logn)；常见的应用：符号表，人工智能象棋程序可以很快的查询某个位置是不是已经被考虑过，改进后可以用于存储非常大型的字典；可扩充散列法：在可扩充散列中的散列函数计算出的是一个存储地址，将该地址段的内容读入内存后再查找；

f) B树：包含数量庞大的记录，并记录在磁盘上。利用额外的空间很重要，就是加索引；大型数据的索引都是用B树来存储的。所有的记录存在叶子节点，父母节点作为索引。大型的存贮中，B树的节点和磁盘的页面对应，在B树中查找是logn的。当所有的存储在叶子和上面层中的键组成了一颗作为索引的B树，整个结构被称为B+树；

第八章， 动态规划；

如果一个问题是由交叠的子问题构成的，我们就可以用动态规划的计数来解决它。一般这样的子问题出现在对给定问题求解的递推关系中，这个递推关系包含了相同类型的更小子问题的解。与其对交叠问题一次又一次的求解，不如对每个较小的问题只求解一次，并把结果记录在表中，这样就可以从表中得出最原始的解。动态规划的应用大多数都是在求解最优化问题。遵循最优法则：优化问题任一实例的最优解，都是由其子实例的最优解构成的。

1、 三个基本例子：

a) 币值最大问题

b) 找零问题

c) 硬币收集问题

2、 背包问题和记忆功能

a) 动态规划方法通常包括自顶向下，自底向上两种；但是不可避免的要做一些无冗余的操作；要找到一种方法，只对必要的子问题求解一次，已记忆功能为主。但算法的主题思想应还是自顶向下，但是维护一个自底向上动态规划算法使用的表格；对算法提升的效率是常数的，对于一个无法在常数时间内完成的计算，性能改善可能显著；自底向上算法的空间优化版本，记忆功能算法的空间效率是低的。

3、 最优二叉查找树

a) 如果集合中元素的查找概率是已知的，找到一个最优的二叉查找树：查找的平均键值比较次数是最低的。

4、 Warshall算法和Floyd算法

a) 用于计算有向图传递闭包的两个算法；一个有向图的邻接图矩阵是一个布尔矩阵，当且仅当从第i个顶点到第j个顶点之间有一条有向边，对于给定图的顶点之间是否存在任意长度的有向路径，使我们能够在常数时间内判断第j个顶点是否可从第i个顶点到达。

b) 深度优先查找和广度优先查找，生成有向图的传递包；从0阶包开始生成；

第九章， 贪婪算法；

1、 找零问题，给定一组硬币d1<…..<dn，本能的从这一堆硬币中找到一个开似乎，确定一个最佳选择序列的逻辑策略，从最少的开始选；贪婪算法给出一个最优解；贪婪算法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得完整的解；

2、 贪婪和动态规划有什么区别呢？动态规划是构造一个与原问题相同的子问题交错；贪婪算法是给出当前步骤的解，会不会陷入局部最优的问题？因为只能看到当前的步骤；

a) 必须满足以下三个条件：必须满足约束条件是可行的；是局部最优的；不可取消；通过找局部最优，求得整体最优问题的解；

b) 我们的人生就是一个贪婪求解的过程，我们无法看到整体的情况，也就是无法对问题整体建立模型；也就是邓小平说的摸着石头过河的道理；

c) 针对某些通过构造局部解，求的整体解的问题是可以用贪婪算法；

d) 也是求解最优化问题；

e) 困难的是如何证明一个贪婪算法取得最优解，通常用数学归纳法来进行证明；第二种方式是证明，每一步至少不比其他步骤差；第三种证明方法是基于算法的输出而不是它执行的操作；（贪婪背后的理论-拟阵的抽象组合结构）

3、 Prim算法：

a) 问题：给定一个点，把它们按照一种代价最低的方式连接起来，使得任意两点之间都存在一条路径；应用-网络设计；

b) 本质上变成了图中的最小生成树问题；如果试图用穷举法来构造一颗最小生成树会遇到很大的障碍；生成树的数目指数增长，给出这个集合也非常困难；

c) Prim算法通过不断扩张的子树来构造一颗最小生成树；每一次迭代，用贪婪的方式来扩张生成子树，即将与树中顶点距离最近的顶点加入树中；对这种算法，需要设计顶点信息的格式，记录自己的同时记录最近的点；

d) Prim算法是否总是能生成最小树呢，答案是肯定的。

4、 Kruskal算法

a) 发明算法的人，是个二年级的研究生；算法把一个加权连通图的最小生成树看作一个无环子图，边的权重和是最小的。该算法通过对子图的一系列扩展来构造一棵最小生成树；

b) 不相交子集和并查算法

i. 要求把一个n个元素集合S动态划分为一系列不相交的子集S1-SNK,可以用kruskal算法；

5、 Dijstra算法

a) 问题描述：单起点最短路径问题：对于加权连通图的一个成为起点的给定顶点，求出它到所有其他顶点之间的一系列最短路径；（路径规划、商旅问题）

b) Dijkstra算法：按照从给定起点到图中顶点的距离，顺序求出最短路径；首先求出从起点到最接近起点的顶点之间的最短路径，然后求出第二近似，以此类推；与PRIM算法不同，DIJSTRA算法会比较所有路径，然后选择最短的，prim只会比较当前权重；算法效率（V2，顶点个数的平方）

6、 哈夫曼树及编码

a) 问题：假设我们必须为文本中的每个字符赋予一串代码，由N个不同的字符组成，并且这些字符都来自于某张字母表；可以用定长赋予字符，就是传统的ASII码；如何产生最短的位串？

b) 前缀码算法：用一个二叉树来表示字符，所有左边的都是0，右边的都是1；

c) 如何构造一个将较短位串分配给高频字符，将较长位串赋给低频字符的树呢？用贪婪法构造哈夫曼树；

d) 1、初始化n个单节点的树，标上字母表中的字符。把每个字符的概率记在树根中指出权重；2、找到两个权重最小的树作为新树的左右子树，根节点为概率之和；3、重复上述步骤；这样的话，权重小的就被分在了新树的下层，大的分在高层；可以用于数据压缩；

e) 解决加权最短路径的问题；（决策树）

第十章， 迭代改进；

1、 迭代改进是从一个可行解出发，重复应用一些简单步骤来不断改进它，与我们工作当中的先完成、再完美的理念相同，先做完再优化，写文章也是一样的，异曲同工之妙，神经网络是不是也是求出一个可行解？然后再迭代优化；与贪婪策略一点一点的构造最优解，每次将一个局部最优加到一个部分构造解；与动态规划不同是将问题变为原问题的一个子集来迭代求解；

a) 几个条件：1、需要一个初始可行解；2、对可行解如何改变并不是一目了然，我们不知道怎么优化可行解；3、避免局部最优的问题；比如爬山，因为迷雾重重，要找到最高点是困难的；

b) 需要用迭代改进来优化的问题：最重要的就是线性规划问题；

2、 单纯形法：

a) 线性规划问题：要求根据一系列线性约束求一个包含若干变量的线性方程组的最优解；

b) 单纯性法是美国数学家丹齐格发明的，认为是线性规划理论之父；

c) 线性规划的几何解释：就是待求优化函数与约束条件构成区域的交点的集合；如果约束条件不构成区域，成为不可行，不具有最优解；约束条件构成区域无界，极点个数可能有无穷多个？怎么办？单纯形法只需要检测可行区域极点中的一小部分求出最优；

d) 算法描述：先在可行区域找到一个极点，然后检查一下是不是在邻接极点处可以让目标函数取值更佳，如果不是，当前顶点就是最优，算法停止；如果是处理那个更佳的邻接顶点；有限步后，该算法要么发现了最优极点，要么发现最优解不存在；

e) 约束：必须是一个最大化的问题；所有约束都必须用线性方程形式表示；所有变量都必须要求是非负的；

第十一章， 算法能力的极限；

1、 智力用来区分可行和不可行，理智用来判别有意义和无意义。所以即使是可行的、也不一定是有意义的；

2、 算法的能力是有极限的，有些问题是无法用任何算法来求解的；有些问题是可以用算法来求解的，但是无法在多项式时间获得答案；有些问题可以在多项式时间内可以求解，但往往局限于最优情况；一个算法的下届是在讨论问题中，可以期望获得多少改进；如果该边界是紧密的，则如果有一个和算法下界差不多的算法，我们可期望的改进最多也就是一个常量因子；如果与算法的下界有不少差距，说明还有很大的改进空间，要么存在一个匹配更快的算法，要么有一个更好的下界；

3、 如何求下界：

a) 平凡下界：确定下界最简单的方法是对问题的输入中必须要处理的项进行计数，同时对必须要输出的项进行计数；因为任何算法必须读入必须处理的项，必须写出必须输出的项，这样的计数就产生了一个平凡的下界；如任何生成n个不同排列的算法必定属于n!，因为输出的规模是n!；而且这个下界是紧密的；同样的计算两个方正乘积的算法的平凡下界属于n2;因为必须要处理2n2个元素，并生成n2个元素，但这个边界的紧密性不知；平凡下界往往过小，因而用处不大。如商旅问题，平凡的边界是n2，但是目前还没有找到一个多项式的算法做到；并不是所有的输入都需要处理的，如有序数组查找问题。

b) 信息论下界：平凡下界考虑的是输入输出的规模，信息论方法是试图根据算法必须处理的信息量来建立效率；某人在1和n之间选择一个正数，我们可以向他提一些能够回答是或者否的问题，来推导这个数，任何求解改问题的算法都必须解决一定数量的不确定性，这个数量就是logn；平凡下界是n；通过决策树的机制，可以更精确的实现这种方法的内在思想；排序和查找是典型的问题；

c) 敌手下界：如果有人扮演一个希望该算法尽可能多提问的敌对角色，在最坏情况下，该算法必须有logn个问题；合并排序，最坏情况下比较次数2n-1，

d) 简化法：把一个问题转化为已知下界的问题；

4、 决策树：通过决策树可以分析排序树的算法下界是nlogn；查找的算法下界是log2n+1

a) 排序算法：可以堪称为一个列表的元素按照升序排列；比较次数不小于logn!；史特林公式得：算法的复杂度为nlogn；

b) 查找有序数组的决策树：分为三段，左、右、中（三叉树）；

c) 通过决策树的方法来寻找算法的下界；

5、 P、NP和NP完全问题：

a) 可以在多项式时间内求解的问题称为易解，反之成为难解；

b) P和NP问题：所有可以在多项式时间内求解的问题成为p问题；（只有判定问题才属于P，即可以回答是或者否的问题）（polynomial）；不能在多项式时间内解决的问题会产生指数级的输出；例如：求一个给定集合的所有子集或者n个不同项的全排列；NP问题是一类可以用不确定多项式算法求解的判定问题，大多数判定问题都是属于NP类的。是P问题的超集；不确定算法指（判定生成的解是否是解，而不是求解）：对任意生成的实例候选解可以在多项式时间内被检验是否正确；NP完全问题：一个NP完全问题是NP中的一个问题，它和该类型中任何其他问题的难度都一样，NP中的任何问题都可以在多项式时间内化简为这种问题；NP完全问题的多项式解，都可以多项式转化为所讨论的问题；得到一个NP完全问题的多项式解，也就是说所有NP问题都能用多项式时间内求出；

c) NP完全问题；哈密顿回路、旅行商问题、背包问题等都是NP完全问题；无多项式解；

6、 数值算法的挑战：数值分析关心那些求解数学问题的算法，这些问题是连续数学问题，例如解方程和联立方程组，求类似sinx和lnx这种函数，以及求积分；

a) 求解一个数学问题面对的主要障碍，大多数数值分析的问题无法求的精确解；通过函数的泰勒展开来逼近某个函数值在某点的值；积分：泰勒展开的几何意义是用矩形面积求和来替代积分，这种逼近带来的误差称为截断误差；另一种误差称为舍入误差：计算机表示的实数有限，不能表示无理数，这种数被表示为浮点数；浮点表示的精度大部分计算机支持单精度（6-7位）、双精度（13-14位）、扩展精度（20），使用更高精度的数会降低运算速度；当计算超出了浮点运算所表示的范围时发生上溢、下溢；遇到这种问题时需要做一些等价变换来解决这类问题，如计算一个表达式的对数；

b) 减法抵消：浮点数相减的时候会导致相对误差大大增加；如果将这样一个低精度的误差作为除数来使用，会显著放大舍入误差；

c) 不稳定性：算法操作中的舍入误差在传递中会有递增效应，称为不稳定，有些问题对于他们的输入显示出很高的敏感度，以至于无法设计一个稳定的算称为坏脾气的；

d) 牛顿法计算平方根；

第十二章， 超越极限-NP难问题；

有几种处理难解问题的算法，回溯法和分支界限法；

1、 回溯法

a) 回溯法相比穷举法是一个更聪明的变化形式；构造一个状态树，采用深度遍历的方式，寻找可能的解，每个节点包括了所有的可能分量，一层层试探下去；走不通就返回上一层；典型问题：N皇后问题，n>4的n皇后问题都可以在线性时间内求解；

b) 哈密顿回路问题：从某个节点开始寻找，某个节点就是根，依次探索下去；

c) 子集和问题：求n个正整数构成的一个给定集合A的子集，子集和要等于一个给定的正整数d；

d) 回溯法用于困难的组合问题，通常无法高效求解；回溯法和穷举查找不同，穷举法注定是非常缓慢的，回溯法至少可以希望在一些规模不是很小的实例中时间可接受，通过剪枝的方式可以优化；即使回溯法没有消去一个问题的状态空间中的任何一个元素，本身也存在一定价值；

2、 分支界限法

a) 不同于回溯法，分支界限法需要计算出每一个节点下各种可能性的最佳分支界限，选择最优的那个继续拓展；不满足约束的进行回溯；一种选择当前最优的方法，选择的标准是计算当前选择最大的可能性，然后选择一个最优的进行试探；

b) 分配问题：给定约束的组合问题

c) 背包问题：给定约束的组合问题

d) 商旅问题：给定约束的组合问题

3、 NP困难问题的近似解·

a) NP完全问题：组合最优难题称为NP困难问题，如背包问题、旅行商问题等等；除了上述两种方法以外，可以用快速的算法对它们近似求解；

b) 启发式算法：一种来自于经验，而不是来自于数学证明的常识性规则；在旅行商问题中，我们可以访问最近的未访问城市，这是一个很好的概念；TSP贪婪算法：任意选择一个城市开始，选择最近访问的城市最近的城市；多片段启发算法：求一个给定加权完全图的最小权重边集合，使得所有顶点连通度为2；基于最小生成树的算法；

4、 解非线性方程的三种方法

a) 平分法：如果一个连续函数在a,b取得的值相反，那么该函数在这两点至少与X轴相交一次；x=(a+b)/2，如果等于0就终止，如果不等于0，更新端点；收敛速度很慢；

b) 试位法：求下一个点用a,b点的函数值与x轴的截距来迭代xn；收敛速度会加快；

c) 牛顿法：最重要的解方程通用算法之一

第十三章：总结

1、 随即算法：在执行时做出随机选择的算法，例如对数组进行排序，可以随机选择一个数组元素作为快速排序的中轴；

2、 顺序算法和并行算法：目前的冯诺依曼计算机是顺序的，但是出现了并行计算的可能性，基于量子计算和DNA计算，可能会对未来的计算能力和算法产生大量影响；

3、 量子计算：试图使同一种原子处于两种状态的量子物理现象，n个这样的原子包括了2n信息；

4、 DNA计算：利用基因选择机制达到相同的目的；对于哈密尔顿回路问题，先生成代表途中路径的DNA链，从中舍弃那些不满足定义的路径，类似穷举查找，但庞大的生化并行过程发生，使我们有望在可接受时间内解决；美国2002年宣布，DNA计算机可以评估100万个备选答案保证满足24个不同约束；2011年，加州技术学院的发布了迄今为止最复杂的生化电路。

好了，这篇文章的内容营销圈就和大家分享到这里，如果大家对网络推广引流和网络创业项目感兴趣，可以添加微信：Sum8338 备注：营销圈引流学习，我拉你进直播课程学习群，每周135晚上都是有实战的推广引流技术和网络创业项目课程分享，当然是免费学！