算法第九章算法設計與分析

算法設計與分析郭丹計算機與信息學院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.競爭分析概率分析：引入概率分布的平均情況分析攤銷分析：關注數據結構的平均最壞情況分析競爭分析：比較算法和最優(yōu)算法的差距5精選ppt第九章競爭分析9.1什么是競爭分析？競爭5年前，葉芙還是一個不為人所知的，沒有申請過任何國家科研經費的研究人員。由于她對文學和哲學非常有興趣，她用故事來講述理論，提出的研究課題也經常與眾不同。但是葉芙的這種研究風格并不被各種“專家們〞所理解：1、"研究的具體步驟是什么呢?"2、"所定義函數中的參數如何定義、度量沒有闡述.沒有提出本工程的關鍵科學問題"3、"影響系統可靠性的最重要因素還是系統本身，與系統運行相關環(huán)境的研究對開發(fā)高可靠系統沒有任何智助……“即便葉芙后來獲得了成功！但她的事例也告訴我們：要想快速獲得成功，就得盡量按照最優(yōu)標準答案來！6精選ppt第九章競爭分析9.1什么是競爭分析？競爭這個世界里充滿競爭。各種評優(yōu)、各種打分、各種獎勵等層出不窮。如果你申請工程未果，其給出的理由通常會包括一句類似"這次的工程評選競爭十分劇烈……"的話。7精選ppt第九章競爭分析9.1什么是競爭分析？競爭的目的是什么？評優(yōu)。那么如何評比才能是真正的選優(yōu)呢?當然是以最優(yōu)的可能性或者"完美"為評判標準，井且到達這個最優(yōu)標準的某一個程度(如百分比)才能被稱為優(yōu)秀。兩個普通算法不是競爭分析！一個算法和最優(yōu)算法的比較才算競爭分析！8精選ppt第九章競爭分析9.2在線算法和離線算法游戲——俄羅斯方塊：一塊塊不同形狀的拼版從上面掉下，玩家需要將這些拼版盡量拼整齊，目標是讓每一行都盡量填滿，不留空格。而填滿的行就會銷掉，從而騰出空間來接收后面的拼版。如果玩家來不及消除足夠的行數而導致拼版累積到框頂，游戲廉價告結束。9精選ppt第九章競爭分析9.2在線算法和離線算法提問：俄羅斯方塊游戲是在線的還是離線的？—在線算法〔在線處理〕：如果一個算法輸入或請求是一個一個出硯，但每個請求和輸入必須立即得到處理，且在處理一個輸入請求的時候不知道后面的請求和輸入，這種處理算法就是在線算法?！x線算法：這種算法可以事先就得知所有的輸入和請求，這樣就可以對所有的輸入和請求進行最優(yōu)的規(guī)劃。10精選ppt第九章競爭分析9.2

在線算法和離線算法提問：俄羅斯方塊游戲是在線的還是離線的？—在線算法：1、一次只提供操作序列S

里面的一個操作.2、對于每個操作，算法必須立即執(zhí)行所需的操作(在不知道將來的操作是什么的情況下)。—離線算法：離線算法可以事先看到整個操作序列S。提問：在線和離線，哪種方式更容易得到最優(yōu)算法？—在線算法不可能得到最優(yōu)！—離線算法有可能得到最優(yōu)！11精選ppt第九章競爭分析9.2

在線算法和離線算法算法例子—很多人將人生比喻一個在線算法，從而判斷人生無法活出最優(yōu)!—操作系統里面的磁盤調度……12精選ppt第九章競爭分析9.2在線算法和離線算法算法例子—人生：一個在線算法，從而判斷人生無法活出最優(yōu)!—操作系統里面的磁盤調度〔在線，離線，在線+離線〕……13精選ppt第九章競爭分析9.3競爭力競爭力〔CompetitiveRatio〕算法的本錢除以最優(yōu)離線算法的本錢。如果設最優(yōu)的離錢算法本錢為o，討論中的在線算法本錢為x。那么該在線算法的競爭力CR=x/o。提問：CR的值是大好呢？還是小好？當然是小好，為什么？14精選ppt第九章競爭分析9.3競爭力定義：一個在線算法A如果滿足以下條件，那么被稱為α-競爭力的。存在一個常數k，對于任意一個操作序列S，有CA(S)≤α﹡COPT(S)+kOPT是我們的最優(yōu)離線算法，也可稱為上帝的算法.。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)-競爭力的。證明：競爭分析怎么比較？選擇最優(yōu)算法->考量離線算法〔假設已經知道我們一生要穿什么衣服的算法〕

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

聚類問題聚類的特點：無訓練語料。聚類的難度：即使離線，也無法判定什么是最優(yōu)！24精選ppt第九章競爭分析9.5

聚類問題求解思想：在一片空間的所有數據點上劃分出給定個數的區(qū)間，使得每個區(qū)間里面最遠兩點的距離最小。25精選ppt第九章競爭分析9.5聚類問題聚類問題的次優(yōu)解算法：CLUSTERJNG-LGORITHM(X)如下:1、首先隨機選擇一個點u1作為第1個區(qū)問C1的中心。2、接著按下面的規(guī)那么依次選擇u2,u3,…,uk向分別作為區(qū)間C2,C3,…,Ck的中心:對于2≤m≤k，um是距離u1,u2,…,um-1最遠的點。3、把其它每個點指派給距離它最近的區(qū)間，即點x所屬區(qū)問為Cy這里y=min{d(x,uy)}。26精選ppt第九章競爭分析9.5

聚類問題求解思想：k=41、隨機選一個類的中心點，2、依次選擇3個離已選擇的點距離最遠的點，作為新的類的中心點。3、把其它點放入離四個類中心點最近的類別中。27精選ppt第九章競爭分析9.5

聚類問題CLUSTERING-ALGORITHM算法的競爭分析這個直徑與最優(yōu)劃分的直徑相比質量如何呢?設x為距離我們選出的k個中心點u1,u2,…,

u