数据结构(算法)总结.doc

数据结构(算法)总结 多项式时间-人们可以接受的时间复杂度（不会长到没尽头）。 P问题-可以在多项式时间内解决的问题。 NP问题-可以猜到答案，并可在多项式时间内验证是否正确的问题。 NPC（完全）问题-是NP问题，且其它所有NP问题都可约化到它的问题。 NP-Hard（难）问题-不一定是NP问题，但其它所有NP问题都可约化到它的问题。 时间复杂度的概念给定算法的运行时间增长趋势，一般输入规模看成很大。 （渐进）阶从低到高1 头最高阶项的系数。 尾非最高阶项与常数。 比如6n3+4n2+10000=O(n3)10n2+2n=O（2n）随机化算法分类数值随机化算法舍伍德算法拉斯维加斯算法蒙特卡罗算法棋盘覆盖（分治策略）前提棋盘必须正好有2k2k（k=自然数）个格子。 步骤 1、将棋盘划分成4个子棋盘。 2、除了有特殊格的子棋盘外，其它3个盘里各取离结合点最近的格子，组成骨牌。 3、将每个子棋盘再划分成4个子棋盘，同样执行步骤2。 4、递归终止条件子棋盘的普通格只剩3个。 比如一个88的棋盘（书p21页例子）划为4等份不看有特殊格那份，其它3份取离结合点最近的格子，拉黑，就形成了一块骨牌。 现在每份都有1块特殊格，然后每份再划4等份每一小份重新执行上面的算法（递归了），忽视特殊份，拉黑离结合点近的。 然后继续递归，重复刚才的步骤（子问题结构完全相同）。 当然这里棋盘比较小，到这里已经可以看出结果。 递归中止条件当子棋盘（划出的小份）只剩下3个普通格时。 七种常用排序算法的时间复杂度最好情况O(?)平均情况O(?)最坏情况O(?)稳定性冒泡n n2n2稳定选择n2n2n2稳定插入n n2n2稳定希尔n1.3nlog nn2n2不稳定堆nlog nnlog nnlog n不稳定归并nlog nnlog nnlog n稳定快速nlog nnlog nn2不稳定其中最坏情况最重要。 稳定性的意思假设有一个数组2,5,2,7,1其中第一个2假设叫a元素，第二个2叫b元素吧。 对其排序后得1,2,2,5,7原本a在b前面，如果排序后，a还在b前面，就是稳定的。 它们调换了就是不稳定的。 也就是说稳定性，决定了同值元素的顺序会不会变动。 理论上，希尔和堆排序不会考，因为上课没讲过。 0-1背包（动态规划）假设有3个物品物品A重3斤，价值4元；物品A重4斤，价值5元；物品A重5斤，价值6元。 考虑方式当放了n-1个物品时，第n个物品放还是不放？设C-当前背包容量（斤）wn-第n个物品的重量（斤）vn-第n个物品的价值（元）。 F(n,C)-将前n个物品放入容量为C的背包时，能获取的总价值。 如果不放第n个物品公式F(n-1,C)如果放第n个物品公式F(n-1,C-wn)+vn简单来说，就是把C、wn、vn代入公式，看2个公式哪个得出的结果大，就选哪个。 然后可以构造出一张表背包容量为C时，能选择的最大价值。 重量价值C=1C=2C=3C=4C=5C=6C=7C=8C=9C=10A3斤4元A XX44444444B4斤5元A+B XX45559999C5斤6元A+B+C XX45669101111解释下，X表示放不下，因为这里最轻的物品也要3斤，C=1或2时肯定放不下。 关键是后面绿色的值是怎么得到的，它是一行行构造出来的。 A行表示只有物品A时，怎么放能得到最大价值。 A+B行表示只有A与B时，怎么放能得到最大价值。 A+B+C行表示有ABC时，怎么放能得到最大价值。 先看A行，因为就物品A，也没有什么比较公式，很显然C大于3时就可以放进A，因为每种物品就一个，所以不管背包多大，最大价值都是4元。 再看A+B行，从这行开始可以套公式了。 比如C=3时F(n-1,C)就是A行C=3时的价值，也就是4元。 F(n-1,C-wn)+vnC-wn=3-4=-1，显然4斤的B根本放不进3斤的包。 所以最大价值是4元再比如C=8时，F(n-1,C)还是4元。 F(n-1,C-wn)+vnC-wn=8-4=4，F(n-1,4)，也就是A行的C=4，为4，再加上vn=5，最终结果是9元。 最大价值选大的，9元。 再看A+B+C行，一样的，就举C=9时的例子吧F(n-1,C)A+B放在C=9，查表得9元。 F(n-1,C-wn)+vnF(A+B,9-5)+6=11元。 选大的，11元。 最终整表的右下角那个，就是整道题的最优解，即11元。 所谓动态规划，就是在算法中，逐步建立起这张表。 填表过程中，后面的值可能会依赖前面的值，这时只要去查表就行了，而不用去临时计算。 换言之，不做重复的子计算。 这种算法效率高了，但存表需要空间，典型的空间换时间的做法。 矩阵连乘（动态规划）矩阵连乘怎么算不重要，这里不写了。 关键3点 1、相乘的矩阵，前面一个的列数要与后面一个的行数相等。 比如3行5列与5行2列的可以乘。 而3行5列与4行2列的没法乘。 2、a行b列与b行c列相乘，会得到一个a行c列的矩阵。 3、a行b列与b行c列相乘，元素相乘次数=abc（次）。 换言之，假设有不同的矩阵A、B、C。 那么（AB）C与A（BC），会产生不同的相乘次数。 而这个问题就是要找到，相乘次数最少的顺序。 举例来说，约定A（3,5）表示一个3行5列的矩阵，假设有A（3,5）B（5,4）C（4,7）如果按（AB）C的顺序AB=（3,4），相乘次数=354=60(3,4)C，相乘次数=347=84最终，整个连乘过程中，次数为60+84=144（次）如果按A（BC）的顺序BC=（5,7），相乘次数=547=120A(5,7)C，相乘次数=357=105最终，整个连乘过程中，次数为120+105=225（次）显然第一种乘得少，乘得少代表效率高，这就是我们追求的。 算法执行过程中，也会逐步建立2张表（书上p48的（b）和（c）表）按书上的例子，有6个矩阵A1A6，最终填表得断开位置表A1A2A3A4A5A6A1011333A202333A30333A4045A505A60所谓断开位置，就是如何加括号（结合律）原式A1A2A3A4A5A6A1到A6怎么断？查表为3，也就是在A3左边断，得（A1A2A3）（A4A5A6）A1到A3查表为1，得（A1（A2A3）（A4A5A6）A4到A6查表为5，得（A1（A2A3）（A4A5）A6）于是这就是答案，按这个顺序，元素相乘的次数最少。 相乘次数表A1A2A3A4A5A6A1015750787593751187515125A2026254375712510500A3075025005375A4010003500A505000A60比如，A3A4A5连乘，就查A3A5，得2500，表示这3个矩阵连乘，最少元素相乘次数为2500次。 那么，我们最终要的答案当然就是A1A6，也就是15125，6个矩阵相乘最少15125次，这就是整体最优解。 动态规划法的常规步骤 1、分析最优解的结构。 2、建立递归关系。 3、计算最优值。 4、构造最优解。 单源最短路径（贪心）用的迪杰斯特拉算法。 以书p101页的图为例有2个集合集合S放已启用的顶点，集合U放未启用的顶点。 具体看例子。 一开始集合S=A，只有起点。 A-B A-C A-D A-E最短路径A-B还到不了A-D A-E最短路径长度1030100所在集合U U U U查表可知，A的邻点中，到B的距离最短，所以将B加入集合S S=A,B现在A可以到C了A-B-C，填进去A-B A-C A-D A-E最短路径A-B A-B-C A-D A-E最短路径长度106030100所在集合S UUU查表S=A,B,D现在发现，A到其它点的路径选择多了。 比如A到E A-E=100A-D-E=90显然后一条虽然经过的点多，但总路径短了，于是更新此表（A到其它点也是，只要有更短路径就换上去）A-B A-C A-D A-E最短路径A-B A-D-C A-D A-D-E最短路径长度10503090所在集合S US U查表，在集合U中，选A过去最近的，发现是A-C=50（路径A-D-C）S=A,B,D,C加入C后，继续找A到其它点有没有更短的走法，有的话就更新表A-B A-C A-D A-E最短路径A-B A-D-C A-D A-D-C-E最短路径长度10503060所在集合S S S U到此，集合U中只剩下E，加入S（路径A-D-C-E）S=A,B,D,C,E最后次更新表（E没有出去的方向，所以实际上本次无更新）A-B A-C A-D A-E最短路径A-B A-D-C A-D A-D-C-E最短路径长度10503060所在集合S SSS最终集合U中元素全部到了S中，表则如上所示。 实际编程中，可以用一个数组表示此表，比如数组arr，arr2保存A-B的最短路径长度，arr3保存A-C的以此类推。 最终arr2=10arr3=50arr4=30arr5=60那么，如果我现在想知道A到C怎么走最短，那么查表（数组）就可知走路径A-D-C最短，长度为50可以看到，每次迭代，集合U都往集合S中送一个点。 而考虑上那个点并更新表后，每次都会获得当前最优的解。 当全部迭代完成，最终得到的表就是整体最优解表。 这一点要注意，贪心法解题，很多都只能获得近似解，但迪杰斯特拉算法可以获得最优解。 将以上步骤抽出来 1、初始时，集合S只包含源点o，集合U包含除了源点的其它顶点。 2、从U中选取一个距离源点最短的顶点加入S中。 3、以S中现有顶点组成路径，审查o到其它点是否有更短路径，有则更新。 4、重复 2、3步。 最优装载（贪心）比如有艘轮船，可以装10吨货物。 假设现在有5件货物，重量分别是 3、 1、 7、 4、9吨。 装最多货物的思路