数据结构(算法)总结.docx

上传人:p** 文档编号:832685 上传时间:2024-03-15 格式:DOCX 页数:11 大小:127.72KB
下载 相关 举报
数据结构(算法)总结.docx_第1页
第1页 / 共11页
数据结构(算法)总结.docx_第2页
第2页 / 共11页
数据结构(算法)总结.docx_第3页
第3页 / 共11页
数据结构(算法)总结.docx_第4页
第4页 / 共11页
数据结构(算法)总结.docx_第5页
第5页 / 共11页
数据结构(算法)总结.docx_第6页
第6页 / 共11页
数据结构(算法)总结.docx_第7页
第7页 / 共11页
数据结构(算法)总结.docx_第8页
第8页 / 共11页
数据结构(算法)总结.docx_第9页
第9页 / 共11页
数据结构(算法)总结.docx_第10页
第10页 / 共11页
亲,该文档总共11页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

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

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!