能有效率地排序小數(shù)字的演算法

Chapter2GettingStarted1GettingStarted2.1InsertionSort:能有效率地排序小數(shù)字的演算法範(fàn)例:5246132546132456132456131245631234562GettingStarted2.2AnalyzingAlgorithms

RAM:Random-accessmachine,在此機(jī)器上執(zhí)行記憶體存取只需一單位的時(shí)間，且指令是依序一個(gè)一個(gè)執(zhí)行。

Runningtime:

執(zhí)行的步驟的總數(shù)量，以inputsize

的函數(shù)來表示之。3GettingStarted範(fàn)例:InsertionSort Insertion-Sort(A) 1for

j

←2to

length[A] 2 do

key

←

A[j] 3 ?insertA[j]intothesorted

sequenceA[1..j-1] 4 i

←

j–1 5 while

i>0andA[i]>key 6 do

A[i+1]←

A[i] 7 i

←

i–1 8 A[i+1]←

key

T(n)=c1n+(c2+c4+c8)(n-1)+c5+(c6+c7)costc1c20c4c5c6c7c8timesnn-1n-1n-1n-14GettingStartedBest-case: Eachtj=1.(輸入A

是排序好的)

T(n)= (c1+c2+c4+c5+c8)n-(c2+c4+c5+c8) =

(n) (rateofgrowth,orderofgrowth)Worst-case:(upperbound) Eachtj=j.

T(n)= k1n2+k2n+k3 =

(n2)5GettingStartedAverage-case:

(Expectedrunningtime) Eachtj=j/2

T(n)= t1n2+t2n+t3 =

(n2) (rateofgrowth,orderofgrowth)6GettingStarted2.3DesigningAlgorithmsDivide-and-Conquer: Divide:(把大問題切成幾個(gè)比較小的相同問題) Conquer:(解決問題) Combine:(把小問題的解合成大問題的解)7GettingStarted範(fàn)例:MergeSort8GettingStarted12234566245612362546132652461362sortedsequencemergemergemergemergemergemergemerge被合併起來的排序好的數(shù)列長度會(huì)由下往上遞增。(例如：最底層為1，倒數(shù)第二層為2，最上層則為8)9GettingStartedAnalysis:(recurrence)T(n) = =

(nlog

n)10GettingStartedExercisesProblem1:

給定一行文字，請你幫忙列出ASCII字元的出現(xiàn)頻率。你可以假設(shè)ASCII前32個(gè)字元以及後128個(gè)字元不會(huì)出現(xiàn)。每一行文字的後面可能會(huì)以’\n’和’\r’結(jié)束，但是不用把那些字元考慮進(jìn)去。

輸入：會(huì)給好幾行文字。每一行的長度最大會(huì)到1000。輸入以檔案結(jié)尾為結(jié)束。

輸出：對於每一行輸入，根據(jù)出現(xiàn)的頻率高低印出ASCII字元的ASCII值以及該字元出現(xiàn)的頻率(頻率高的先印)。在每組輸出之間要印一個(gè)空行。如果兩個(gè)ASCII字元有相同的頻率，那麼ASCII值比較小的優(yōu)先印出。11GettingStarted以下是一個(gè)輸出入的實(shí)例:SampleInputSampleOutputAAABBC12233367166265349150251312GettingStartedExercisesProblem2:

測量一個(gè)序列“亂”的程度的方法是算出有幾對數(shù)字不是依照順序排好的。例如，在序列”DAABEC”中，依照上面的度量方法亂度是5，因?yàn)镈比它右邊的四個(gè)字母還大，E也比右邊的一個(gè)字母大。其實(shí)這亂度的算法就是這個(gè)序列的inversion數(shù)目。序列”AACEDGG”只有一個(gè)inversion(E和D)，幾乎是排序好的；然而”ZWQM”有六個(gè)inversion(幾乎沒有排序，事實(shí)上正好是排序好的相反)。

你負(fù)責(zé)要分類一堆DNA序列（序列只由A,T,C,G四個(gè)字母構(gòu)成）。然而，你不是要根據(jù)字典順序排序這些序列，而是要根據(jù)他們的”不亂程度”，從”最接近排序好的序列”到”幾乎沒有排序好的序列”依序列出。所有的序列都有相同的長度。13GettingStartedExercises

輸入：第一行是一個(gè)整數(shù)M，然後在一個(gè)空行之後會(huì)接著M

組測資。在每組測資之間會(huì)有一個(gè)空行當(dāng)作間隔。每組測資的第一行包含兩個(gè)兩個(gè)正整數(shù)：n(0<n

≤50)表示序列的長度；m(0<m≤100)表示序列的總數(shù)。接下來會(huì)有m

行，每一行都是長度為n

的DNA序列。

輸出：對於每一組測資，從”最接近排序好”的序列排到”幾乎沒有排序過”的序列。如果兩個(gè)序列的亂度相同，先在輸入檔出現(xiàn)的要先印出。14GettingStarted以下是一個(gè)輸出入的實(shí)例:SampleInputSampleOutput1106