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

多项式时间-人们可以接受的时间复杂度（不会长到没尽头）。P问题-可以在多项式时间内解决的问题。NP问题可以猜到答案，并可在多项式时间内验证是否正确的问题。NPC（完全）问题是NP问题，且其它所有NP问题都可约化到它的问题。NP-Hard（难）问题-不一定是NP问题，但其它所有NP问题都可约化到它的问题。时间复杂度的概念，给定算法的运行时间增长趋势，一般输入规模看成很大。（渐进）阶从低到高：1<Iogn<n<nlogn<n2<n3<2n<n!<nn大0阶表示法的计算原那么：保存最高阶，去头去尾。头：最高阶项的系数。尾：非最高阶项与常数。比方：6n3+4n2+10000=0（n3）IOn2+2n=0（2n）随机化算法分类：数值随机化算法舍伍德算法拉斯维加斯算法蒙特卡罗算法棋盘覆盖（分治策略前提：棋盘必须正好有2kX2kIk=自然数）个格子。步骤：1、将棋盘划分成4个子棋盘。2、除了有特殊格的子棋盘外，其它3个盘里各取离结合点最近的格子，组成骨牌。3、将每个子棋盘再划分成4个子棋盘，同样执行步骤2。4、递归终止条件：子棋盘的普通格只剩3个。比方一个8X8的棋盘（书p21页例子）：划为4等份:不看有特殊格那份，其它3份取离结合点最近的格子，拉黑，就形成了一块骨牌。现在每份都有1块特殊格，然后每份再划4等份:每一小份重新执行上面的算法(递归了)，无视特殊份，拉黑离结合点近的。然后继续递归，重复刚刚的步骤(子问题结构完全相同)。当然这里棋盘比拟小，到这里已经可以看出结果。递归中止条件：当子棋盘(划出的小份)只剩下3个普通格时。七种常用排序算法的时间复杂度:最好情况0(?)平均情况0(7)最坏情况0(7)稳定性冒泡nn2n2稳定选择n2n2n2稳定插入nn2112稳定希尔n13nlognn2n2不稳定堆nlognlognlog不稳定归并nlognlognnlogn稳定快速nlognnlognn2不稳定其中最坏情况最重要。稳定性的意思：假设有一个数组2,5,2f7tl其中第一个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个物品的重量(Jt)vn-第n个物品的价值(元)。F(n,C)-将前n个物品放入容量为C的背包时，能获取的总价值。如果不放第n个物品：公式：F(n-l,C)如果放第n个物品公式：F(n-1,C-wn)+vn简单来说，就是把C、wn.vn代入公式，看2个公式哪个得出的结果大，就选哪个。然后可以构造出一张表：背包容量为C时，能选择的最大价值。重量价值C=IC=2C=3C=4C=5C=6C=7C=8C=9C=IOA3斤4元AXX44444444B4斤5元A+BXX45559999C5斤6元A+B+CXX45669101111解释下，X表示放不下，因为这里最轻的物品也要3斤，C=I或2时肯定放不下。关键是后面绿色的值是怎么得到的，它是行行构造出来的。A行表示只有物品A时，怎么放能得到最大价值。A+B行表示只有A与B时，怎么放能得到最大价值。A+B+C行表示有ABC时，怎么放能得到最大价值。先看A行，因为就物品A,也没有什么比拟公式，很显然C大于3时就可以放进A,因为每种物品就一个，所以不管背包多大，最大价值都是4元。再看A+B行，从这行开始可以套公式了。比方C=3时：F(n-l,C):就是A行C=3时的价值，也就是4元。F(n-lzC-wn)+vn:C-wn=3-4=-1,显然4斤的B根本放不进3斤的包。所以最大价值是4元再比方C=8时，F(n-l,C)：还是4元。F(n-l,C-wn)+vn:C-wn=8-4=4,F(n-l,4),也就是A行的C=4,为4,再力口上vn=5,最终结果是9元。最大价值选大的，9元。再看A+B+C行，一样的，就举C=9时的例子吧：F(n-l,C):A+B放在C=9,查表得9元。F(n-lzC-wn)+vn：F(A+B,9-5)+6=11TEo选大的，11元。最终整表的右下角那个，就是整道题的最优解，即11元。所谓动态规划，就是在算法中，逐步建立起这张表。填表过程中，后面的值可能会依赖前面的值，这时只要去查表就行了，而不用去临时计算。换言之，不做重复的子计算。这种算法效率高了，但存表需要空间，典型的空间换时间的做法。矩阵连乘(动态规划)：矩阵连乘怎么算不重要，这里不写了。关键3点：1、相乘的矩阵，前面一个的列数要与后面一个的行数相等。比方3行5列与5行2列的可以乘。而3行5列与4行2列的没法乘。2、a行b列与b行C列相乘，会得到一个a行C列的矩阵。3、a行b列与b行C列相乘，元素相乘次数=a×b×c(次)。换言之，假设有不同的矩阵A、B、Co那么(A×B)XC与AX(BXC),会产生不同的相乘次数。而这个问题就是要找到，相乘次数最少的顺序。举例来说，约定A(3,5)表示一个3行5列的矩阵，假设有：A(3,5)B(5,4)C(4,7)如果按(AXB)XC的顺序：AXB=(3,4),相乘次数=3×5×4=60(3z4)×C,相乘次数=3×4×7=84最终，整个连乘过程中，次数为60+84=144(次)如果按AX(BXC)的顺序：BXC=(5,7),相乘次数=5X4X7=120AX(5,7)XC,相乘次数=3×5×7=105最终，整个连乘过程中，次数为120+105=225(次)显然第一种乘得少，乘得少代表效率高，这就是我们追求的。算法执行过程中，也会逐步建立2张表(书上p48的(b)和(C)表)按书上的例子，有6个矩阵A1A6,最终填表得：AI到A6怎么断？查表为3,也就是在A3左边断，得:(A1×A2×A3)X(A4×A5×A6)Al到A3查表为1,得：(A1×(A2×A3)X(A4×A5×A6)A4到A6查表为5,得：(A1×(A2×A3)×(A4×A5)×A6)于是这就是答案，按这个顺序，元素相乘的次数最少。相乘次数表:AlA2A3A4A5A6Al015750787593751187515125A2026254375712510500A3075025005375A4010003500A505000A60比方，A3A4A5连乘，就查A3A5,得2500,表示这3个矩阵连乘，最少元素相乘次数为2500次。那么，我们最终要的答案当然就是A1A6,也就是15125,6个矩阵相乘最少15125次，这就是整体最优解。动态规划法的常规步骤：1、分析最优解的结构。2、建立递归关系。3、计算最优值。4、构造最优解。单源最短路径（贪心）：用的迪杰斯特拉算法。以书PlOl页的图为例:有2个集合：集合S放已启用的顶点，集合U放未启用的顶点。具体看例子。一开始集合S=A,只有起点。A->BA->CA->DA->E最短路径A->B还到不了A->DA->E最短路径长度1030100所在集合UUUU查表可知，A的邻点中，到B的距离最短，所以将B参加集合SS=A,B现在A可以到C了：A->B->C,填进去:A->BA->CA->DA->E最短路径A->BA->B->CA->DA->E最短路径长度106030100所在集合SUUU查表S=A,B,D)现在发现，A到其它点的路径选择多了。比方A到E：A->E=100A->D->E=90显然后一条虽然经过的点多，但总路径短了，于是更新此表:（A到其它点也是，只要有更短路径就换上去）A->BA->CA->DA->E最短路径A->BA->D->CA->DA->D->E最短路径长度10503090所在集合SUSU查表，在集合U中，选A过去最近的，发现是A->C=50（路径A->D->C）S=A,BzD,C参加C后，继续找A到其它点有没有更短的走法，有的话就更新表A->BA->CA->DA->E最短路径A->BA->D->CA->DA->D->C->E最短路径长度10503060所在集合SSSU到此，集合U中只剩下E,参加S路径A->D->C->E):S=A,B,D,CzE)最后次更新表IE没有出去的方向，所以实际上本次无更新）A->BA->CA->DA->E最短路径A->BA->D->CA->DA->D->C->E最短路径长度10503060所在集合SSSS最终集合U中元素全部到了S中，表那么如上所示。实际编程中，可以用一个数组表示此表，比方数组arr,a2保存A->B的最短路径长度，arr3M呆存A->C的以此类推。最终：arr2=10arr3=50arr4=30arr5=60那么，如果我现在想知道A到C怎么走最短，那么查表（数组）就可知：走路径A->D->C最短，长度为50可以看到，每次迭代，集合U都往集合S中送一个点。而考虑上那个点并更新表后，每次都会获得当前最优的解。当全部迭代完成，最终得到的表就是整体最优解表。这一点要注意，贪心法解题，很多都只能获得近似解，但迪杰斯特拉算法可以获得最优解。将以上步骤抽出来：1、初始时，集合S只包含源点。，集合U包含除了源点的其它顶点。2、从U中选取一个距离源点最短的顶点参加S中。3、以S中现有顶点组成路径，审查。到其它点是否有更短路径，有那么更新。4、重复2、3步。最优装载（贪心）：比方有艘轮船，可以装10吨货物。假设现在有5件货物，重量分别是3、1、7、4、9吨。装最多货物的思路：1、先对货物按重量从