能有效率地排序小数字的演算法

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,Getting Started,*,Chapter 2,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,範例,:,Insertion Sort,Insertion-,Sort(,A,),1,for,j,2,to,length,A,2,do,key,A,j,3 insert,A,j,into the sortedsequence,A,1.,j,-1,4,i,j,1,5,while,i,0 and,A,i,key,6,do,A,i,+1,A,i,7,i,i,1,8,A,i,+1,key,T,(,n,)=,c,1,n,+(,c,2,+,c,4,+,c,8,)(,n,-1)+,c,5,+(,c,6,+,c,7,),cost,c,1,c,2,0,c,4,c,5,c,6,c,7,c,8,times,n,n,-1,n,-1,n,-1,n,-1,4,Getting Started,Best-case:,Each,t,j,=1.(,輸入,A,是排序好的,),T,(,n,)=(,c,1,+,c,2,+,c,4,+,c,5,+,c,8,),n,-(,c,2,+,c,4,+,c,5,+,c,8,),=,(,n,),(,rate of growth,order of growth,),Worst-case:,(upper bound),Each,t,j,=,j,.,T,(,n,)=,k,1,n,2,+,k,2,n,+,k,3,=,(,n,2,),5,Getting Started,Average-case:,(Expected running time),Each,t,j,=,j,/2,T,(,n,)=,t,1,n,2,+,t,2,n,+,t,3,=,(,n,2,),(,rate of growth,order of growth,),6,Getting 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,被合併起來的排序好的數列長度會由下往上遞增。,(,例如：最底層為,1,，倒數第二層為,2,，最上層則為,8),9,Getting Started,Analysis:(,recurrence,),T,(,n,)=,=,(,n,log,n,),10,Getting Started,Exercises,Problem 1:,給定一行文字，請你幫忙列出,ASCII,字元的出現頻率。你可以假設,ASCII,前,32,個字元以及後,128,個字元不會出現。每一行文字的後面可能會以,n,和,r,結束，但是不用把那些字元考慮進去。,輸入：,會給好幾行文字。每一行的長度最大會到,1000,。輸入以檔案結尾為結束。,輸出：,對於每一行輸入，根據出現的頻率高低印出,ASCII,字元的,ASCII,值以及該字元出現的頻率,(,頻率高的先印,),。在每組輸出之間要印一個空行。如果兩個,ASCII,字元有相同的頻率，那麼,ASCII,值比較小的優先印出。,11,Getting Started,以下是一個輸出入的實例,:,Sample Input,Sample Output,AAABBC,122333,67 1,66 2,65 3,49 1,50 2,51 3,12,Getting Started,Exercises,Problem 2:,測量一個序列,“,亂”的程度的方法是算出有幾對數字不是依照順序排好,的。例如，在序列,”,DAABEC”,中，依照上面的度量方法亂度是,5,，因為,D,比它右邊的四個字母還大，,E,也比右邊的一個字母大。其實這亂度的算法就是這個序列的,inversion,數目。序列,”,AACEDGG”,只有一個,inversion(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,以下是一個輸出入的實例,:,Sample Input,Sample Output,1,10 6,AACATGAAGG,TTTTGGCCAA,TTTGGCCAAA,GATCAGATTT,CCCGGGGGGA,ATCGATGCAT,CCCGGGGGGA,AACATGAAGG,GATCAGATTT,ATCGATGCAT,TTTTGGCCAA,TTTGGCCAAA,15,Getting Started,