《{企业效率管理}能有效率地排序小数字的演算法》由会员分享，可在线阅读，更多相关《{企业效率管理}能有效率地排序小数字的演算法（15页珍藏版）》请在金锄头文库上搜索。
1、Chapter 2,Getting Started,1,Getting Started,2.1 Insertion Sort: 能有效率地排序小數字的演算法 範例:,524613,254613,245613,245613,124563,123456,2,Getting Started,2.2 Analyzing Algorithms RAM: Random-access machine, 在此機器上執行記憶體存取只需一單位的時間，且指令是依序一個一個執行。 Running time: 執行的步驟的總數量，以 input size 的函數來表示之。,3,Getting Started,範例: I
2、nsertion Sort Insertion-Sort(A) 1 for j 2 to lengthA 2 do key Aj 3 insert Aj into the sortedsequence A1.j - 1 4i j 1 5while i 0 and Ai key 6do Ai + 1 Ai 7i i 1 8Ai + 1 key T(n) = c1n+(c2+c4+c8)(n-1)+c5 +(c6+c7),cost c1 c2 0 c4 c5 c6 c7 c8,times n n - 1 n - 1 n - 1 n - 1,4,Getting Started,Best-case:
3、Each tj=1. (輸入 A 是排序好的) T(n) =(c1+c2+c4+c5+c8)n-(c2+c4+c5+c8) =(n) (rate of growth, order of growth) Worst-case: (upper bound) Each tj=j. T(n) =k1n2 + k2n + k3 =(n2),5,Getting Started,Average-case: (Expected running time) Each tj=j/2 T(n) =t1n2 + t2n + t3 =(n2) (rate of growth, order of growth),6,Ge
4、tting Started,2.3 Designing Algorithms Divide-and-Conquer: Divide:(把大問題切成幾個比較小的相同問題) Conquer:(解決問題) Combine:(把小問題的解合成大問題的解),7,Getting Started,範例: Merge Sort,8,Getting Started,12234566,2456,1236,25,46,13,26,5,2,4,6,1,3,6,2,sorted sequence,merge,merge,merge,merge,merge,merge,merge,被合併起來的排序好的數列長度會由下往上遞
5、增。(例如：最底層為 1，倒數第二層為 2，最上層則為 8),9,Getting Started,Analysis: (recurrence) T(n)= = (nlog n),10,Getting Started,Exercises,Problem 1: 給定一行文字，請你幫忙列出 ASCII 字元的出現頻率。你可以假設 ASCII 前 32 個字元以及後 128 個字元不會出現。每一行文字的後面可能會以 n 和 r 結束，但是不用把那些字元考慮進去。 輸入：會給好幾行文字。每一行的長度最大會到 1000。輸入以檔案結尾為結束。 輸出：對於每一行輸入，根據出現的頻率高低印出 ASCII 字元
6、的 ASCII 值以及該字元出現的頻率(頻率高的先印)。在每組輸出之間要印一個空行。如果兩個 ASCII 字元有相同的頻率，那麼 ASCII 值比較小的優先印出。,11,Getting Started,以下是一個輸出入的實例:,12,Getting Started,Exercises,Problem 2: 測量一個序列“亂”的程度的方法是算出有幾對數字不是依照順序排好的。例如，在序列”DAABEC”中，依照上面的度量方法亂度是 5，因為 D 比它右邊的四個字母還大，E 也比右邊的一個字母大。其實這亂度的算法就是這個序列的 inversion 數目。序列”AACEDGG”只有一個 inversi
7、on (E 和 D)，幾乎是排序好的；然而”ZWQM”有六個 inversion (幾乎沒有排序，事實上正好是排序好的相反) 。 你負責要分類一堆 DNA 序列（序列只由 A, T, C, G 四個字母構成）。然而，你不是要根據字典順序排序這些序列，而是要根據他們的”不亂程度”，從”最接近排序好的序列”到”幾乎沒有排序好的序列”依序列出。所有的序列都有相同的長度。,13,Getting Started,Exercises,輸入：第一行是一個整數 M，然後在一個空行之後會接著 M 組測資。在每組測資之間會有一個空行當作間隔。每組測資的第一行包含兩個兩個正整數：n (0 n 50) 表示序列的長度；m (0 m 100) 表示序列的總數。接下來會有 m 行，每一行都是長度為 n 的 DNA 序列。 輸出：對於每一組測資，從”最接近排序好”的序列排到”幾乎沒有排序過”的序列。如果兩個序列的亂度相同，先在輸入檔出現的要先印出。,14,Getting Started,以下是一個輸出入的實例:,15,Getting Started,
