数据结构与算法分析总结

在算法设计中，顺序表主要用于检索，而利用栈中的递归思想在算法中则应用非常广泛，如递归排序，分治算法等。

树结构：是一种非常重要的非线性数据结构，它是由一个根结点和若干叶结点组成的树状结构，除了根结点每个结点只能有一个父节点，可以有若干子结点，若干个树结构还可以构成森林，树的存储结构也分为顺序存储和链式存储，最典型的是左孩子右兄弟法。在树结构中比较重要的算法就是周游（遍历）树，有先根次序、后根次序以及中根次序。

树结构中有几类非常重要的特殊树结构，如二叉树，b树，b+树等，其中，二叉树应用最为广泛。

二叉树：是指每个结点最多有两个子结点的树结构，具体细分，根据叶子结点的特性可分为满二叉树、完全二叉树等。二叉树的遍历也分为深度优先和广度优先。

另外，二叉树有几条非常重要的性质，这也使得它的应用非常广泛。

在算法设计中，典型的利用树的深度优先遍历的算法是回溯法，而典型的广度优先搜索算法是分枝定界法。

图：是一种较线性表和树更为复杂的数据结构。一般来讲，数据的逻辑结构可表示为结点的有穷集合k和k上的一个关系r,如果对k中结点相对于r的前驱、后继个数加以限制，则可以分别定义线性结构、树形结构和图结构，即：

线性结构：惟一前驱，惟一后继，反映一种线性关系；

树形结构：惟一前驱，多个后继，反映一种层次关系；

图结构：不限制前驱的个数，亦不限制后继的个数，反映一种网状关系。

通常用g=(v,e)代表一个图，其中v是顶点集，e是边集。图分为有向图和无向图，图的存储方式有邻接表和邻接矩阵法。和树类似的，图中也需要周游，同样有深度优先搜索和广度优先搜索，而比树的周游要更复杂，也更重要。

在这一块中，有两种比较典型的求最短路径和最小支撑树的算法需要注意，它们分别是dijkstra算法和prim算法。另外需要注意的是图的连通性。

在算法设计中，典型的用到图论的算法有贪心算法和动态规划算法。

对于计算机科学来说，算法的概念至关重要。通俗的讲，算法是指解决问题的一种方法或一个过程，或者严格来讲，是由若干条指令组成的有穷序列，且满足以下4条性质；

1）输入：有零个或多个由外部提供的量作为算法的输入。

2）输出：算法产生至少一个量作为输出。

3）确定性：组成算法的每条指令是清晰的，无歧义的。

4）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

我们研究一个算法或者评价一个算法主要是通过估计该算法的复杂性，包括时间复杂性和空间复杂性。空间复杂性是指使用该算法的程序在运行时需要占用多少内存空间，具体包括指令空间、数据空间和环境栈空间。时间复杂性是指执行该程序所需要的时间量级，通常是估算的时间，包括编译时间和运行时间。

同**价一个算法的好坏还要看其时间复杂性和空间复杂性随着输入规模的增长趋势，一般能接受的最好是线性增长。在算法设计这本书中，每介绍一个算法都会分析其算法复杂度，由此可看出它的重要性。

首先，从递归的分治算法开始。分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将各个子问题的解合并得到原问题的解。

该算法的主要应用有大整数乘法，矩阵乘法、合并排序等。可以大大降低算法的时间复杂度，但使用递归栈可能增加程序的空间规模。

动态规划算法和贪心算法：与分治算法类似，动态规划的基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治算法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。

动态规划算法适用于解最优化问题。通常可按以下4个步骤：

1）找出最优解的性质，并刻画其结构特征。

2）递归的定义最优值。

3）以自底向上的方式计算出最优值。

4）根据计算最优值时得到的信息，构造最优解。

动态规划算法的基本要素是最优子结构性质和子问题重叠性质。

最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

子问题重叠性质。子问题重叠性质是指在用递归演算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个**中，当再次需要计算已经计算过的子问题时，只是在**中简单地查看一下结果，从而获得较高的效率。

另外一点要素是备忘录方法，它作为动态规划算法的变形，用**保存已解决问题的答案，在下次需要解此子问题时，只要简单查看子问题的解答，而不必重新计算。与动态规划不同的是备忘录方法的递归是自顶向下的，而动态规划则是自底向上的。

动态规划算法设计策略典型的应用案例有：矩阵连乘、最大字段和、流水作业调度等。

有时满足动态规划条件的问题可以有更好的算法，比如贪心算法。贪心算法即总是做出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑，它所做的总是做出的选择只是在某种意义上的局部最优。

这种启发式的策略并不能总是奏效，然而对某些特定的问题确能达到预期目的。比如活动安排的例子。

贪心算法的基本要素主要有贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法与动态规划的主要区别，它们的共同点是都要求问题具有最优子结构性质。

贪心算法的典型案列是：活动安排、最优装载问题、最短路径和最优生成树问题。

回溯法和分枝定界法：回溯法有“通用的解题法”之称。用它可以系统的搜索一个问题的所有解或任一解。

它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。其算法框架包含递归回溯和迭代回溯，两个特别的解空间树为子集树和排列树。

典型的回溯法的案例有：批处理作业调度、图的m着色、旅行售货员问题、0-1背包问题等。

分枝定界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分治定界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有的解，而分枝定界法的求解目标则是找出满足约束条件的一个解，或是满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

由于求解目标不同，导致分支定界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分枝定界法则以广度优先或以最小耗费优先的方式搜索解空间。

另外，在算法分析中一定要提的是np问题。首先需要介绍p(polynomial,多项式)问题。p问题是可以在多项式时间内被确定机(通常意义的计算机)解决的问题。

np(non-deterministic polynomial, 非确定多项式)问题，是指可以在多项式时间内被非确定机(他可以猜，他总是能猜到最能满足你需要的那种选择，如果你让他解决n皇后问题，他只要猜n次就能完成---每次都是那么幸运)解决的问题。这里有一个著名的问题---千禧难题之首，是说p问题是否等于np问题，也即是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解。

np完全(np complete,npc)问题是指这样一类np问题，所有的np问题都可以用多项式时间划归到他们中的一个。所以显然np完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的np－完全问题也可以在多项式时间内求解。

这样一来，只要我们找到一个npc问题的多项式解，所有的np问题都可以多项式时间内划归成这个npc问题，再用多项式时间解决，这样np就等于p了。

小结一下，在算法设计这么课中学了这么几大类典型的算法，里面也涉及到具体的应用案例，但我觉得学算法的目的远不是学会这几种固定的特殊问题的解法而已，事实上领会这些巧妙算法背后的思想然后学会迁移到其他新的问题中去才是领会了算法设计的精髓。

数据结构与算法分析总结

数据结构与算法分析总结

数据结构与算法分析总结

数据结构与算法分析

其他用户还读了