




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
算法设计与分析郭丹计算机与信息学院guodan@:2021年10月1精选ppt课堂内容2精选ppt算法分析篇第七章概率分析第八章摊销分析第九章竞争分析3精选ppt第九章竞争分析9.1什么是竞争分析?9.2在线算法和离线算法9.3竞争力9.4线性表更新问题9.5聚类问题4精选ppt第九章竞争分析9.1什么是竞争分析?概率分析VS.摊销分析VS.竞争分析概率分析:引入概率分布的平均情况分析摊销分析:关注数据结构的平均最坏情况分析竞争分析:比较算法和最优算法的差距5精选ppt第九章竞争分析9.1什么是竞争分析?竞争5年前,叶芙还是一个不为人所知的,没有申请过任何国家科研经费的研究人员。由于她对文学和哲学非常有兴趣,她用故事来讲述理论,提出的研究课题也经常与众不同。但是叶芙的这种研究风格并不被各种“专家们〞所理解:1、"研究的具体步骤是什么呢?"2、"所定义函数中的参数如何定义、度量没有阐述.没有提出本工程的关键科学问题"3、"影响系统可靠性的最重要因素还是系统本身,与系统运行相关环境的研究对开发高可靠系统没有任何智助……“即便叶芙后来获得了成功!但她的事例也告诉我们:要想快速获得成功,就得尽量按照最优标准答案来!6精选ppt第九章竞争分析9.1什么是竞争分析?竞争这个世界里充满竞争。各种评优、各种打分、各种奖励等层出不穷。如果你申请工程未果,其给出的理由通常会包括一句类似"这次的工程评选竞争十分剧烈……"的话。7精选ppt第九章竞争分析9.1什么是竞争分析?竞争的目的是什么?评优。那么如何评比才能是真正的选优呢?当然是以最优的可能性或者"完美"为评判标准,井且到达这个最优标准的某一个程度(如百分比)才能被称为优秀。两个普通算法不是竞争分析!一个算法和最优算法的比较才算竞争分析!8精选ppt第九章竞争分析9.2在线算法和离线算法游戏——俄罗斯方块:一块块不同形状的拼版从上面掉下,玩家需要将这些拼版尽量拼整齐,目标是让每一行都尽量填满,不留空格。而填满的行就会销掉,从而腾出空间来接收后面的拼版。如果玩家来不及消除足够的行数而导致拼版累积到框顶,游戏廉价告结束。9精选ppt第九章竞争分析9.2在线算法和离线算法提问:俄罗斯方块游戏是在线的还是离线的?—在线算法〔在线处理〕:如果一个算法输入或请求是一个一个出砚,但每个请求和输入必须立即得到处理,且在处理一个输入请求的时候不知道后面的请求和输入,这种处理算法就是在线算法。—离线算法:这种算法可以事先就得知所有的输入和请求,这样就可以对所有的输入和请求进行最优的规划。10精选ppt第九章竞争分析9.2
在线算法和离线算法提问:俄罗斯方块游戏是在线的还是离线的?—在线算法:1、一次只提供操作序列S
里面的一个操作.2、对于每个操作,算法必须立即执行所需的操作(在不知道将来的操作是什么的情况下)。—离线算法:离线算法可以事先看到整个操作序列S。提问:在线和离线,哪种方式更容易得到最优算法?—在线算法不可能得到最优!—离线算法有可能得到最优!11精选ppt第九章竞争分析9.2
在线算法和离线算法算法例子—很多人将人生比喻一个在线算法,从而判断人生无法活出最优!—操作系统里面的磁盘调度……12精选ppt第九章竞争分析9.2在线算法和离线算法算法例子—人生:一个在线算法,从而判断人生无法活出最优!—操作系统里面的磁盘调度〔在线,离线,在线+离线〕……13精选ppt第九章竞争分析9.3竞争力竞争力〔CompetitiveRatio〕算法的本钱除以最优离线算法的本钱。如果设最优的离钱算法本钱为o,讨论中的在线算法本钱为x。那么该在线算法的竞争力CR=x/o。提问:CR的值是大好呢?还是小好?当然是小好,为什么?14精选ppt第九章竞争分析9.3竞争力定义:一个在线算法A如果满足以下条件,那么被称为α-竞争力的。存在一个常数k,对于任意一个操作序列S,有CA(S)≤α﹡COPT(S)+kOPT是我们的最优离线算法,也可称为上帝的算法.。15精选ppt第九章竞争分析9.4线性表更新问题线性表更新问题——衡量本钱的例子给定一个线性表和一组访问请求,如果访问位置靠前的元素比位置靠后的元素本钱低。当然,在每次访问结束后,允许算法对线性表进行重新排列。提问:如何设计算法使得访问线性表的本钱最低?提示:衣橱!衣橱里的衣服一件件叠放着(一个线性表)。每天出门的时候我们从这摞衣服里面取出一套穿上(访问线性表)。晚上回来后再把衣服放回到衣橱(不用洗衣服)。16精选ppt第九章竞争分析9.4线性表更新问题前置移动算法(Move-To-Front,MTF):1、将最常穿的衣服放在较上面的位置。2、每次拿最上面的衣服。3、回来脱下来的衣服也放在最上面。提问:以前的分析能判断这个算法的总本钱会是最低吗?
17精选ppt第九章竞争分析9.4线性表更新问题前置移动算法(Move-To-Front,MTF):定理:线性表的MTF算法是4-竞争力。推论:如采我们把元素x移动到表头的本钱记为0,即我们能够用常数时间将x从L里面切割出来附加在头上(链表),那么MTF算法就是2-竞争力。所以,我们宣称MTF算法是O(1)-竞争力的。证明:竞争分析怎么比较?选择最优算法->考量离线算法〔假设已经知道我们一生要穿什么衣服的算法〕
18精选ppt第九章竞争分析9.4线性表更新问题前置移动算法(Move-To-Front,MTF):证明:一次操作本钱就是移动元素的次数。估算实际操作本钱与离线本钱的距离借鉴势能分析来估算两者距离。19精选ppt第九章竞争分析9.4
线性表更新问题前置移动算法(Move-To-Front,MTF):证明:
势能分析得到范围值之后,再做一个换算,得如下结论。因此,线性表的MTF算法是4-竞争力。20精选ppt第九章竞争分析9.5
聚类问题聚类——衡量结果的例子聚类就是对大量未知标注的数据集,按数据的内在相似性将数据集划分为多个类别,使类别内的数据相似度较大而类别间的数据相似度较小。
21精选ppt第九章竞争分析9.5
聚类问题聚类的应用例子
对相似的文档或超链接进行聚类,由于类别数远小于文档数,能够加快用户寻找相关信息的速度。22精选ppt第九章竞争分析9.5聚类问题聚类的应用例子采用网络数据集单个TCP连接的根本属性。进行聚类分类:DOS——拒绝效劳攻击类型;U2R——非授权得到超级用户权限;R2L——从远程计算机进行非授权的访问;Probing——扫描或者对其它系统漏洞的探测。
特征名称特征描述duration连接时间的长短protocol_type协议类型,比如tcp,udp等Service,…….……23精选ppt第九章竞争分析9.5
聚类问题聚类的特点:无训练语料。聚类的难度:即使离线,也无法判定什么是最优!24精选ppt第九章竞争分析9.5
聚类问题求解思想:在一片空间的所有数据点上划分出给定个数的区间,使得每个区间里面最远两点的距离最小。25精选ppt第九章竞争分析9.5聚类问题聚类问题的次优解算法:CLUSTERJNG-LGORITHM(X)如下:1、首先随机选择一个点u1作为第1个区问C1的中心。2、接着按下面的规那么依次选择u2,u3,…,uk向分别作为区间C2,C3,…,Ck的中心:对于2≤m≤k,um是距离u1,u2,…,um-1最远的点。3、把其它每个点指派给距离它最近的区间,即点x所属区问为Cy这里y=min{d(x,uy)}。26精选ppt第九章竞争分析9.5
聚类问题求解思想:k=41、随机选一个类的中心点,2、依次选择3个离已选择的点距离最远的点,作为新的类的中心点。3、把其它点放入离四个类中心点最近的类别中。27精选ppt第九章竞争分析9.5
聚类问题CLUSTERING-ALGORITHM算法的竞争分析这个直径与最优划分的直径相比质量如何呢?设x为距离我们选出的k个中心点u1,u2,…,
u
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年中考新疆化学试卷及答案
- 悉尼驾考笔试题目及答案
- 2025年危险货品运输考试题及答案
- 小学五年级数学易错题详解
- 农产品电商推广活动策划方案
- 光的直线传播教学设计
- 幼儿保育技能笔试题目及答案
- 出售樱桃苗木合同范本
- 再生建材出售合同范本
- 公司外聘教师合同范本
- 2025河北承德市市直事业单位卫生类招聘85人考试参考试题及答案解析
- 医院用消毒剂的配制课件
- 腰大池引流管护理查房
- 国网网络信息安全培训课件
- 《丹青意蕴》第三课《国色新尚》课件 2025-2026学年+人教版(2024)初中美术八年级上册
- 口腔辐射安全培训记录课件
- 跨境资金池管理办法
- 校企挂职锻炼协议书范本
- 2025年健身运动与体能训练技术考试试题及答案解析
- 心理韧性:在困境中绽放的力量+课件-2025-2026学年高一上学期时代楷模主题班会
- 高分子材料概论橡胶课件
评论
0/150
提交评论