算法第九章算法设计与分析

算法设计与分析郭丹计算机与信息学院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