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

《数据结构(算法)总结.docx》由会员分享，可在线阅读，更多相关《数据结构(算法)总结.docx（11页珍藏版）》请在第一文库网上搜索。

1、多项式时间-人们可以接受的时间复杂度不会长到没尽头）。P问题-可以在多项式时间内解决的问题。NP问题-可以猜到答案，并可在多项式时间内验证是否正确的问题。NPC （完全）问题-是NP问题，且其它所有NP问题都可约化到它的问题。NP-Hard （难）问题-不一定是NP问题，但其它所有NP问题都可约化到它的问题。时间复杂度的概念：给定算法的运行时间增长趋势，一般输入规模看成很大。（渐进阶从低到高：1 Iogn n nlogn n2 n3 2n n! vn代入公式，看2个公式哪个得出的结果大，就选哪个。然后可以构造出一张表:背包容量为C时，能选择的最大价值。重量价值C=IC=2C=3C=4C=5C=

2、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行，从这行开始可以套公式了。

3、比方C=3时：F( n-l,C):就是A行03时的价值，也就是4元。F( n-l,C-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行，一样的，就举09时的例子吧：F( n-l,C): A+B放在C=9,查表得9元。F( n-l, C-wn) + vn： F( A+B

4、, 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列相乘，元素相乘次数=

5、aXbBA-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 = IOOA - D - E = 90显然后一条虽然经过的点多，但总路径短了，于是更新此表:S到其它点也是，只要有更短路径就换上去)A- BA-CA-DA-E最短路径A- BA - D

6、 - CA-DA - D - E最短路径长度10503090所在集合SUSU查表，在集合U中，选A过去最近的，发现是A- C = 50路径A-D-OS = A, B, D,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, C,E)最后次更新表E没有出去的方向，所以实际上本次无更新)A-BA-CA-DA-E最短路径A-BA - D - CA-DA - D - C - E最短路径长度10503060所在集合SSSS最终集合U中元素全部到了 S中，表那么如上所示。实际编程中，可以用一个数组表示此表，比方数组 arr, arr2保存A-B的最短路径长度，arr3保存A- C的以此类推。最终：arr2 = 10arr3 = 50arr4 = 30arr5 = 60那么，如果我现在想知道A到C怎么走最短，那么查表数组就可知：走路径A-D-C最短，长度为50可以看到，每次迭代，集合U都往集合S中送一个点。而考虑上那个点并更新表后，每次都会获得当前最优的解。当全部迭代完成，最终得到的表