欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    算法复杂性和常见问题幻灯片.ppt

    • 资源ID:87510613       资源大小:1.09MB        全文页数:22页
    • 资源格式: PPT        下载积分:18金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要18金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    算法复杂性和常见问题幻灯片.ppt

    算法复杂性和常见问题第1页,共22页,编辑于2022年,星期一第1章 算法复杂性和常用数学工具1.运行时间的上界、下界和准确界2.最优算法3.常见问题第2页,共22页,编辑于2022年,星期一1.运行时间的上界、下界和准确界1.1 运行时间的上界1.2 运行时间的下界1.3 运行时间的准确界1.4 更小阶和常见复杂度类型第3页,共22页,编辑于2022年,星期一1.1 运行时间的上界v函数f(n)和g(n)都是整数到正实数集合的映射,如果存在正整数n0和正常数c,使得对所有n n0,都有f(n)cg(n),就称f(n)的阶至多是O(g(n)。v这个定义的意义是:f(n)的增长至多像g(n)那样快。v例如,f(n)=2n2+3,g(n)=n2。则可以取n0=3,c=3。第4页,共22页,编辑于2022年,星期一1.2 运行时间的下界v函数f(n)和g(n)都是整数到正实数集合的映射,如果存在正整数n0和正常数c,使得对所有n n0,都有f(n)cg(n),就称f(n)的阶至少是(g(n)。v这个定义的意义是:f(n)的增长至少像g(n)那样快。v例如,f(n)=2n2+3,g(n)=n2。则可以取n0=1,c=2。第5页,共22页,编辑于2022年,星期一1.3 运行时间的准确界v函数f(n)和g(n)都是整数到正实数集合的映射,如果存在正整数n0和正常数c1和c2(c1 c2),使得对所有n n0,都有c1 g(n)f(n)c2 g(n),就称f(n)的阶是(g(n)。v这个定义的意义是:f(n)的增长像g(n)一样快。v关系“具有相同准确界”构成一个等价类满足自反性、对称性和传递性(试证传递性)v例如,f(n)=2n2+3,g(n)=n2。则可以取n0=3,c1=1,c2=3。第6页,共22页,编辑于2022年,星期一1.4 更小阶和常见复杂度类型v函数f(n)和g(n)都是整数到正实数集合的映射,如果对于任意正常数c,都存在正整数nc,使得对所有n n0,都有f(n)b-d-c-a第14页,共22页,编辑于2022年,星期一3.5 n皇后问题(待续)8皇后问题是高斯1850年提出的一个著名问题:国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子,问在88=64格的棋盘上如何能摆上八个皇后而使她们都不能互相吃。现已知此问题共有92种解,但只有12种是独立的,其余的都可以由这12种利用对称性或旋转而得到。n皇后问题:如果棋盘是nn的格的,又如何摆放这些皇后?下面是4皇后问题的答案:第15页,共22页,编辑于2022年,星期一3.5 n皇后问题(续)1#主对角线主对角线3#主对角线主对角线5#主对角线主对角线0#次对角线次对角线2#次对角线次对角线4#次对角线次对角线6#次对角线次对角线1#次对角线次对角线3#次对角线次对角线5#次对角线次对角线0#主对角线主对角线2#主对角线主对角线4#主对角线主对角线6#主对角线主对角线0 1 2 3 0123第16页,共22页,编辑于2022年,星期一3.6 假币问题v一堆钱币共有n个,其中一个是假币,比其他钱币轻,给你一架没有砝码的天平,如何用最少的次数把假币找出来?v如果事先只知道假币和真币不一样中,而不知道它是轻还是重呢?如果是这种情况,给你12个钱币,其中一个是假币,你能使用天平3次把假币找出吗?第17页,共22页,编辑于2022年,星期一3.7 凸包问题v给定n个点构成的平面上的点集,求出其凸包v凸包是包含点集的最小凸集v最小的意义是:其它凸集若能覆盖点集,则能覆盖凸包v平面上的凸集是这样的集合:凸集上任意两点间线段上的任意一点都属于该集合v凸包有一个重要的性质:凸包是由某些点构成的多边形注意不用人的直觉,而是用计算机怎样解决这个问题!第18页,共22页,编辑于2022年,星期一3.8 平面上的最近点问题v一个二维平面上给出n个点,如何找到这n的点之间的存在的最小距离?有没有小于O(n2)的方案?第19页,共22页,编辑于2022年,星期一3.9 排序问题v怎样给一个一维数组快速排序?v你目前能想到几种办法?复杂度分别是多少?堆排序是怎样操作的?第20页,共22页,编辑于2022年,星期一3.10 多段最短路径问题多段图是一个带权的有向连通图,顶点能够划分为k部分,第一部分和第k部分各是一个顶点,分别是始点和终点,第j部分结点发出的所有有向弧都指向了第j+1部分的结点。要求在多段图中寻找一条从始点到终点的路径,使得路径的权值之和最小。下例的最优值是160123456789423988874756866573第21页,共22页,编辑于2022年,星期一3.11 任务分配问题v把n项任务分配给n个人,每个人完成每项任务的成本不同,要求分配总成本最小的分配方案。v例如,下面的问题的最优方案成本是13任务1任务2任务3任务4人员a人员b人员c人员d9278643758187694第22页,共22页,编辑于2022年,星期一

    注意事项

    本文(算法复杂性和常见问题幻灯片.ppt)为本站会员(石***)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

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

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开