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

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

Runningtime:

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

的函數(shù)來(lái)表示之。3GettingStarted2.2AnalyzingAlgorithms3Getti範(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-14GettingStarted範(fàn)例:InsertionSortcosttimes4GeBest-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)5GettingStartedBest-case:5GettingStartedAverage-case:

(Expectedrunningtime) Eachtj=j/2

T(n)= t1n2+t2n+t3 = (n2) (rateofgrowth,orderofgrowth)6GettingStarted6GettingStarted2.3DesigningAlgorithmsDivide-and-Conquer: Divide:(把大問(wèn)題切成幾個(gè)比較小的相同問(wèn)題) Conquer:(解決問(wèn)題) Combine:(把小問(wèn)題的解合成大問(wèn)題的解)7GettingStarted2.3DesigningAlgorithms7Getti範(fàn)例:MergeSort8GettingStarted8GettingStarted12234566245612362546132652461362sortedsequencemergemergemergemergemergemergemerge被合併起來(lái)的排序好的數(shù)列長(zhǎng)度會(huì)由下往上遞增。(例如：最底層為1，倒數(shù)第二層為2，最上層則為8)9GettingStarted122345662456123625461326524613Analysis:(recurrence)T(n) = =(nlogn)10GettingStartedAnalysis:(recurrence)10GettinExercisesProblem1: 給定一行文字，請(qǐng)你幫忙列出ASCII字元的出現(xiàn)頻率。你可以假設(shè)ASCII前32個(gè)字元以及後128個(gè)字元不會(huì)出現(xiàn)。每一行文字的後面可能會(huì)以’\n’和’\r’結(jié)束，但是不用把那些字元考慮進(jìn)去。

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

輸出：對(duì)於每一行輸入，根據(jù)出現(xiàn)的頻率高低印出ASCII字元的ASCII值以及該字元出現(xiàn)的頻率(頻率高的先印)。在每組輸出之間要印一個(gè)空行。如果兩個(gè)ASCII字元有相同的頻率，那麼ASCII值比較小的優(yōu)先印出。11GettingStartedExercisesProblem1:11GettingS以下是一個(gè)輸出入的實(shí)例:SampleInputSampleOutputAAABBC12233367166265349150251312GettingStarted以下是一個(gè)輸出入的實(shí)例:SampleInputSampleExercisesProblem2: 測(cè)量一個(gè)序列“亂”的程度的方法是算出有幾對(duì)數(shù)字不是依照順序排好的。例如，在序列”DAABEC”中，依照上面的度量方法亂度是5，因?yàn)镈比它右邊的四個(gè)字母還大，E也比右邊的一個(gè)字母大。其實(shí)這亂度的算法就是這個(gè)序列的inversion數(shù)目。序列”AACEDGG”只有一個(gè)inversion(E和D)，幾乎是排序好的；然而”ZWQM”有六個(gè)inversion(幾乎沒(méi)有排序，事實(shí)上正好是排序好的相反)。 你負(fù)責(zé)要分類一堆DNA序列（序列只由A,T,C,G四個(gè)字母構(gòu)成）。然而，你不是要根據(jù)字典順序排序這些序列，而是要根據(jù)他們的”不亂程度”，從”最接近排序好的序列”到”幾乎沒(méi)有排序好的序列”依序列出。所有的序列都有相同的長(zhǎng)度。13GettingStartedExercisesProblem2:13GettingSExercises

輸入：第一行是一個(gè)整數(shù)M，然後在一個(gè)空行之後會(huì)接著M組測(cè)資。在每組測(cè)資之間會(huì)有一個(gè)空行當(dāng)作間隔。每組測(cè)資的第一行包含兩個(gè)兩個(gè)正整數(shù)：n(0<n≤50)表示序列的長(zhǎng)度；m(0<m≤100)表示序列的總數(shù)。接下來(lái)會(huì)有m行，每一行都是長(zhǎng)度為n的DNA序列。

輸出：對(duì)於每一組測(cè)資，從”最接近排序好”的序列排到”幾乎沒(méi)有排序過(guò)”的序列。如果兩個(gè)序列的亂度相同，先在輸入檔出現(xiàn)的要先印出。14GettingStartedExercises14GettingStarted以下是一個(gè)輸出入的實(shí)例:SampleInputSampleOutput1106AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCATCCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAATTTGGCCAAA15GettingStarted以下是一個(gè)輸出入的實(shí)例:SampleInputSampleChapter2GettingStarted16GettingStartedChapter2GettingStarted1Getti2.1InsertionSort:能有效率地排序小數(shù)字的演算法範(fàn)例:52461325461324561324561312456312345617GettingStarted2.1InsertionSort:能有效率地排序小數(shù)字2.2AnalyzingAlgorithms

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

Runningtime:

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

的函數(shù)來(lái)表示之。18GettingStarted2.2AnalyzingAlgorithms3Getti範(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-119GettingStarted範(fàn)例:InsertionSortcosttimes4GeBest-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)20GettingStartedBest-case:5GettingStartedAverage-case:

(Expectedrunningtime) Eachtj=j/2

T(n)= t1n2+t2n+t3 = (n2) (rateofgrowth,orderofgrowth)21GettingStarted6GettingStarted2.3DesigningAlgorithmsDivide-and-Conquer: Divide:(把大問(wèn)題切成幾個(gè)比較小的相同問(wèn)題) Conquer:(解決問(wèn)題) Combine:(把小問(wèn)題的解合成大問(wèn)題的解)22GettingStarted2.3DesigningAlgorithms7Getti範(fàn)例:MergeSort23GettingStarted8GettingStarted12234566245612362546132652461362sortedsequencemergemergemergemergemergemergemerge被合併起來(lái)的排序好的數(shù)列長(zhǎng)度會(huì)由下往上遞增。(例如：最底層為1，倒數(shù)第二層為2，最上層則為8)24GettingStarted122345662456123625461326524613Analysis:(recurrence)T(n) = =(nlogn)25GettingStartedAnalysis:(recurrence)10GettinExercisesProblem1: 給定一行文字，請(qǐng)你幫忙列出ASCII字元的出現(xiàn)頻率。你可以假設(shè)ASCII前32個(gè)字元以及後128個(gè)字元不會(huì)出現(xiàn)。每一行文字的後面可能會(huì)以’\n’和’\r’結(jié)束，但是不用把那些字元考慮進(jìn)去。

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

輸出：對(duì)於每一行輸入，根據(jù)出現(xiàn)的頻率高低印出ASCII字元的ASCII值以及該字元出現(xiàn)的頻率(頻率高的先印)。在每組輸出之間要印一個(gè)空行。如果兩個(gè)ASCII字元有相同的頻率，那麼ASCII值比較小的優(yōu)先印出。26GettingStartedExercisesProblem1:11GettingS以下是一個(gè)輸出入的實(shí)例:SampleInputSampleOutputAAABBC12233367166265349150251327GettingStarted以下是一個(gè)輸出入的實(shí)例:SampleInputSampleExercisesProblem2: 測(cè)量一個(gè)序列“亂”的程度的方法是算出有幾對(duì)數(shù)字不是依照順序排好的。例如，在序列”DAABEC”中，依照上面的度量方法亂度是5，因?yàn)镈比它右邊的四個(gè)字母還大，E也比右邊的一個(gè)字母大。其實(shí)這亂度的算法就是這個(gè)序列的inversion數(shù)目。序列”AACEDGG”只有一個(gè)inversion(E和D)，幾乎是排序好的；然而”ZWQM”有六個(gè)inversion(幾乎沒(méi)有排序，事實(shí)上正好是排序好的相反)。 你負(fù)責(zé)要分類一堆DNA序列（序列只