数据结构总结.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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构总结 数据结构 总结
限制150内