《数据结构(算法)总结.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、先对货物按重量从