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

《算法复杂性和常见问题幻灯片.ppt》由会员分享，可在线阅读，更多相关《算法复杂性和常见问题幻灯片.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法复杂性和常见问题第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)那样

2、快。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），使

3、得对所有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皇后问题是高斯

4、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#主对角

5、线主对角线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平面上的凸集是这样的集合

6、：凸集上任意两点间线段上的任意一点都属于该集合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年，星期一