数据结构总结.docx

《数据结构总结.docx》由会员分享，可在线阅读，更多相关《数据结构总结.docx（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结多项式时间- 人们可以接受的时间复杂度（不会长到没终点）。P 问题 - 可以在多项式时间内解决的问题。NP 问题 - 可以猜到答案,并可在多项式时间内验证是否正确的问题。NPC（完全）问题- 是 NP 问题,且其它全部NP 问题都可约化到它的问题。NP-Hard（难）问题- 不肯定是 NP 问题,但其它全部NP 问题都可约化到它的问题。时间复杂度的概念：给定算法的运行时间增长趋势,一般输入规模看成很大。（渐进）阶从低到高：1 logn n nlogn n2 n3 2n n. BA - CA - DA - E最短路径 最短路径长度所在集合A - B 10U仍到不了UA - D 3

2、0UA - E 100U一开头集合 S = A ,只有起点。查表可知, A 的邻点中,到B 的距离最短,所以将B 加入集合 S S = A, B 可编辑资料 - - - 欢迎下载精品名师归纳总结最短路径A - BA - BA - CA - B - CA - DA - DA - EA - E最短路径长度106030100所在集合SUUU现在 A 可以到 C 了： A - B - C,填进去：查表S = A, B, D 可编辑资料 - - - 欢迎下载精品名师归纳总结最短路径A - BA - BA - CA - D - CA - DA - DA - EA - D - E最短路径长度10503090

3、所在集合SUSU现在发觉, A 到其它点的路径挑选多了。比如A - E = 100A - D - E = 90A 到 E：明显后一条虽然经过的点多,但总路径短了,于是更新此表：（A 到其它点也是,只要有更短路径就换上去）查表,在集合U 中,选 A 过去最近的,发觉是A - C = 50（路径 A - D - C） S = A, B, D, C 可编辑资料 - - - 欢迎下载精品名师归纳总结加入 C 后,连续找 A 到其它点有没有更短的走法,有的话就更新表最短路径A - BA - BA - CA - D - CA - DA - DA - EA - D - C - E最短路径长度10503060

4、所在集合SSSU到此,集合 U 中只剩下 E,加入 S（路径 A - D - C - E）： S = A, B, D, C, E 可编辑资料 - - - 欢迎下载精品名师归纳总结最终次更新表（ E 没有出去的方向,所以实际上本次无更新）最短路径A - BA - BA - CA - D - CA - DA - DA - EA - D - C - E最短路径长度10503060所在集合SSSS最终集合 U 中元素全部到了 S中,表就如上所示。实际编程中,可以用一个数组表示此表, 比如数组 arr , arr2 储存 A - B 的最短路径长度,arr3 储存 A - C的以此类推。最终：arr2

5、= 10arr3 = 50arr4 = 30arr5 = 60那么,假如我现在想知道A 到 C 怎么走最短,那么查表（数组）就可知： 走路径 A - D - C最短,长度为50可以看到,每次迭代,集合U 都往集合 S 中送一个点。而考虑上那个点并更新表后,每次都会获得当前最优的解。当全部迭代完成,最终得到的表就是整体最优解表。这一点要留意,贪心法解题,许多都只能获得近似解,但迪杰斯特拉算法可以获得最优解。将以上步骤抽出来：1、 初始时,集合S 只包含源点 o,集合 U 包含除了源点的其它顶点。2、 从 U 中选取一个距离源点最短的顶点加入S 中。3、 以 S中现有顶点组成路径,审查o 到其它点

6、是否有更短路径,有就更新。4、 重复 2、 3 步。最优装载（贪心） ：比如有艘轮船,可以装10 吨货物。假设现在有 5 件货物,重量分别是3、1、 7、4、9 吨。装最多货物的思路：1、 先对货物按重量从小到大排序：1、 3、4、7、9 吨。2、 依次装船, 直到装不下。 这里装上 1、3、4 后就放不了 7 了。所以最多装 3 个。简言之,先装轻的,再装重的,当然能装的就最多。可编辑资料 - - - 欢迎下载精品名师归纳总结留意：虽然是贪心法,但此题得到的肯定是最优解。动态规划与贪心的关系：动态规划建表查表需花费时间、空间开销,效率比贪心低,但确定能获得最优解。贪心每次只取局部最优解,效率高,但整体不肯定（留意是不肯定 ）是最优解。可编辑资料 - - - 欢迎下载