数据结构算法总结.docx

1、数据结构算法总结多项式时间 - 人们可以接受的时间复杂度（不会长到没尽头）。P问题 - 可以在多项式时间内解决的问题。NP问题 - 可以猜到答案，并可在多项式时间内验证是否正确的问题。NPC（完全）问题 - 是NP问题，且其它所有NP问题都可约化到它的问题。NP-Hard（难）问题 - 不一定是NP问题，但其它所有NP问题都可约化到它的问题。时间复杂度的概念： 给定算法的运行时间增长趋势，一般输入规模看成很大。（渐进）阶从低到高： 1 logn n nlogn n2 n3 2n n! BA - CA - DA - E最短路径A - B还到不了A - DA - E最短路径长度1030100所在集

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

3、 E最短路径长度10503090所在集合SUSU查表，在集合U中，选A过去最近的，发现是A - C = 50（路径A - D - C）S = 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 -

4、D - CA - DA - D - C - E最短路径长度10503060所在集合SSSS最终集合U中元素全部到了S中，表则如上所示。实际编程中，可以用一个数组表示此表，比如数组arr，arr2保存A - B的最短路径长度，arr3保存A - C的以此类推。最终： arr2 = 10 arr3 = 50 arr4 = 30 arr5 = 60那么，如果我现在想知道A到C怎么走最短，那么查表（数组）就可知：走路径A - D - C最短，长度为50可以看到，每次迭代，集合U都往集合S中送一个点。而考虑上那个点并更新表后，每次都会获得当前最优的解。当全部迭代完成，最终得到的表就是整体最优解表。这一点

5、要注意，贪心法解题，很多都只能获得近似解，但迪杰斯特拉算法可以获得最优解。 将以上步骤抽出来：1、 初始时，集合S只包含源点o，集合U包含除了源点的其它顶点。2、 从U中选取一个距离源点最短的顶点加入S中。3、 以S中现有顶点组成路径，审查o到其它点是否有更短路径，有则更新。4、 重复2、3步。最优装载（贪心）： 比如有艘轮船，可以装10吨货物。假设现在有5件货物，重量分别是3、1、7、4、9吨。 装最多货物的思路：1、 先对货物按重量从小到大排序：1、3、4、7、9吨。2、 依次装船，直到装不下。这里装上1、3、4后就放不了7了。所以最多装3个。简言之，先装轻的，再装重的，当然能装的就最多。注意：虽然是贪心法，但本题得到的一定是最优解。 动态规划与贪心的关系： 动态规划建表查表需花费时间、空间开销，效率比贪心低，但肯定能获得最优解。 贪心每次只取局部最优解，效率高，但整体不一定（注意是不一定）是最优解。