1、算法設計與分析2022年7月18日講授內容：動態規劃I教師：胡學鋼、吳共慶至今為止，我們見過的排序都是 比較排序 : 僅僅運用比較來比較各項的相對順序 . 比如：插入排序,合并排序,快速排序, 堆排序.我們見過的比較排序的最好的最壞運轉時間是O(nlgn). O(nlgn)是不是我們能做到的極限? 決策樹 可以協助我們回答這個問題 . 排序可以做到多快？排序a1, a2, , an每個內部節點標識為 i:j i, j 1, 2, n.左子樹表示當ai aj時的比較序列 .右子樹表示當ai aj時的比較序列 .決策樹舉例排序 a1, a2, a3= 9 , 4 , 6 :每個內部節點標識為i:j

2、,i,j1, 2, n.左子樹表示當aiaj時的比較序列 .右子樹表示當aiaj時的比較序列 .決策樹舉例每個內部節點標識為i:j,i,j1, 2, n.左子樹表示當aiaj時的比較序列 .右子樹表示當aiaj時的比較序列 .排序 a1, a2, a3= 9 , 4 , 6 :決策樹舉例每個內部節點標識為i:j,i,j1, 2, n.左子樹表示當aiaj時的比較序列 .右子樹表示當aiaj時的比較序列 .排序 a1, a2, a3= 9 , 4 , 6 :決策樹舉例每個內部節點標識為i:j,i,j1, 2, n.左子樹表示當aiaj時的比較序列.右子樹表示當aiaj時的比較序列.排序 a1,

3、a2, a3= 9 , 4 , 6 :決策樹舉例 決策樹可以模擬任何的比較排序的執行過程:每個輸入大小為n的序列都可以用這棵樹表示. 將算法視為每次兩個項相比后就分叉.樹包含了一切能夠比較的指令途徑.算法的運轉時間 = 途徑的長度.最壞運轉時間 = 樹的高度.決策樹模型定理.對n個項排序的任何決策樹的高度是(nlgn).證明. 樹一定包含n!個葉子, 由于有n!種能夠的陳列. 高度h 的二叉樹有2h個葉子. 因此,n! 2h.(lg 單調遞增)(Stirlings 公式)決策樹排序的下界 推論.在最差情況下，任何一種比較排序至少需求O(nlogn)比較操作。這是比較操作所獲的信息有限所導致的，

4、或者說是全序集的模糊代數構造所導致的。從這個意義上講，堆排序和合并排序是漸進最正確的比較排序算法 .比較排序的下界計數排序: 各項之間不進展比較.輸入: A1 . . n, Aj1, 2, , k.輸出: B1 . . n, 有序.輔助存儲: C1 . . k.線性時間排序for i1 to k do Ci 0for j1 to n do CAj CAj + 1 Ci = |key = i|for i2 to k do Ci Ci + Ci1 Ci = |key i|for jn downto1 do BCAj Aj CAj CAj 1計數排序計數排序舉例for i1 to k do Ci 0

5、循環1for j1 to n do CAj CAj + 1 Ci = |key = i|循環2for j1 to n do CAj CAj + 1 Ci = |key = i|循環2for j1 to n do CAj CAj + 1 Ci = |key = i|循環2for j1 to n do CAj CAj + 1 Ci = |key = i|循環2for j1 to n do CAj CAj + 1 Ci = |key = i|循環2for i2 to k do Ci Ci + Ci1 Ci = |key i|循環3for i2 to k do Ci Ci + Ci1 Ci = |ke

6、y i|循環3for i2 to k do Ci Ci + Ci1 Ci = |key i|循環3for jn downto 1 do BCAj Aj CAj CAj 1循環4for jn downto 1 do BCAj Aj CAj CAj 1循環4for jn downto 1 do BCAj Aj CAj CAj 1循環4for jn downto 1 do BCAj Aj CAj CAj 1循環4for jn downto 1 do BCAj Aj CAj CAj 1循環4forforforfortototodowntododododo分析假設 k = O(n), 那么計數排序用的時

7、間為 (n).但是, 排序的時間是(nlgn)!問題出在什么地方?答案:比較排序 的時間是 (nlgn) .計數排序不是 比較排序.實踐上, 各項之間根本沒有比較!運轉時間計數排序是一種穩定排序: 它會堅持相等的項的相對順序. 練習:哪種其他的排序有這種特征?穩定排序 發源 : Herman Hollerith 為 1890年美國人口普查設計的卡排序機 (參考附錄)一位一位的排序. Hollerith 最初(不好)的想法:從最高位開場排序.好的想法:運用輔助的穩定排序方法從 最低位開場排序 .基數排序基數排序過程數位推導 假設數字曾經按照其低階t 1位排序. 按照t位排序 基數排序的正確性數位

8、推導假設數字曾經按照其低階t1位排序.按照t位排序 兩個在位t不同的數被正確排序.基數排序的正確性數位推導假設數字曾經按照其低階t 1位排序.按照t位排序 兩個在位t不同的數被正確排序. 兩個t 位一樣的數堅持與輸入一樣的次序 正確的順序.基數排序的正確性假設運用計數排序作為輔助的穩定排序方法。 對n個b比特字進展排序。每個字可以看成有b/r個以2r為基的數.例子: 32-位字r =8b/r=4遍基于28位的計數排序; 或者r=16b/r=2遍基于216位的計數排序.我們要作多少遍?基數排序分析回想: 計數排序運用 (n + k)的時間對n個范圍在0到k1的數進展排序。假設每個b-位字分成r-

9、比特份,每遍計數排序破費 (n + 2r).由于有b/r遍,我們有選擇r使得T(n,b)最小:添加r意味著更少的遍數,但是由于 rlgn,時間成指數增長。基數排序分析續經過求導并將方程置0求得最小值T(n,b) 。.或者, 察看我們不要2rn ,在滿足這個限制的條件下選擇盡能夠大的r對對稱性沒有影響。選擇r =lgn意味著T(n,b)= (bn/lgn). 對于界于在0到nd1的數,我們有b =dlgn 基數排序運轉時間為 (dn).選擇r實踐上, 在大量輸入的情況下，基排序速度很快，算法也很容易編碼和維護 .例子 (32-比特數): 對 2000個數排序適宜最多走3遍. 合并排序和快速排序至

10、少要 lg2000 =11遍. 缺陷: 與快速排序不同, 基排序根本上沒有援用部分性, 這樣在現代的處置器上一個調優的快速排序，利用內存的分層體系，可以在性能上超越基數排序。結論Herman Hollerith (1860-1929)穿孔卡Hollerith 的制表系統排序工人的操作基數排序來源“現代的IBM卡片關于穿孔卡技術的網絡資源 附錄: 穿孔技術在1880年美國人口普查破費了近10年的時間處置.在 MIT擔任講師期間,Hollerith發明了穿孔卡技術的原型.他的機器,包括一個“卡排序員 ,使得1890的統計結果在6個周的時間內就處置完了。他在1911年創建了制表機器公司，這個公司在1

11、924年和其他公司合并后組成了國際商用機器公司(IBM).Herman Hollerith(1860-1929)穿孔卡 = 數據記錄.洞 = 值. 算法 = 機器 +操作員.1900 美國人口普查運用的穿孔卡的復制品. Howells 2000穿孔卡Holleriths 制表系統圖片請參考Howells 2000. 穿孔 手壓閱讀器 轉盤計數器 排序盒圖片請參考Howells 2000.圖片請參考Howells 2000. 操作員插入一個卡片。 按住穿過穿孔卡的孔的鍵，使得電流接觸卡下面的水銀杯. 每當一個數位被穿孔后, 對應排序盒的蓋子升起。 操作員將卡片放入盒子并且合上蓋子. 當一切的卡片

12、處置終了后, 前端的面板翻開 ,卡片曾經安裝順序排放, 完成了一遍穩定排序。排序員的操作Hollerith在1889年的最初專利展現了最高位優先的基數排序:“The most complicated combinations can readily be counted with comparatively few counters or relays by first assorting the cards according to the first items entering into the combinations, then reassorting each group according to the second item entering into the combination, and so on, and finally counting on a few counters the last item of the combination for each group of cards.最低位優先的基數排序好似是由一位機器操作員發明的。基數排序的來源 每列一個字符.請看 WWW Virtual Punch