《数据结构(算法)总结.docx》由会员分享，可在线阅读，更多相关《数据结构(算法)总结.docx（11页珍藏版）》请在课桌文档上搜索。
1、多项式时间-人们可以接受的时间复杂度（不会长到没尽头）。P问题-可以在多项式时间内解决的问题。NP问题可以猜到答案，并可在多项式时间内验证是否正确的问题。NPC（完全）问题是NP问题，且其它所有NP问题都可约化到它的问题。NP-Hard（难）问题-不一定是NP问题，但其它所有NP问题都可约化到它的问题。时间复杂度的概念，给定算法的运行时间增长趋势，一般输入规模看成很大。（渐进）阶从低到高：1Iognnnlognn2n32nn!BA-CA-DA-E最短路径A-B还到不了A-DA-E最短路径长度1030100所在集合UUUU查表可知，A的邻点中，到B的距离最短，所以将B参加集合SS=A,B现在A可
2、以到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-
3、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怎么走最短，
4、那么查表（数组）就可知：走路径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、先对货物按重量从小到大排序：1、3、4、7、9吨。2、依次装船，直到装不下。这里装上1、3、4后就放不了7了。所以最多装3个。简言之，先装轻的，再装重的，当然能装的就最多。注意：虽然是贪心法，但此题得到的一定是最优解。动态规划与贪心的关系：动态规划建表查表需花费时间、空间开销，效率比贪心低，但肯定能获得最优解。贪心每次只取局部最优解，效率高，但整体不一定（注意是不定）是最优解。
