算法設(shè)計與分析 ch1 學(xué)習(xí)課件

海量數(shù)據(jù)計算研究中心MassiveDataComputingLab@HIT算法設(shè)計與分析第一章

緒論哈爾濱工業(yè)大學(xué)王宏志wangzh@請各位評審老師提出寶貴建議！謝謝！本講內(nèi)容1.1什么是算法？1.2計算機(jī)科學(xué)中算法的位置1.3算法分析引論1.4算法設(shè)計引論2請各位評審老師提出寶貴建議！謝謝！在數(shù)學(xué)和計算機(jī)科學(xué)之中，算法/算則法（Algorithm）為一個計算的具體步驟，常用于計算、數(shù)據(jù)處理和自動推理。(Wikipedia)算法的例子劉徽割圓術(shù)四則運(yùn)算最小生成樹快速排序什么是算法？3請各位評審老師提出寶貴建議！謝謝！可由一個給定計算模型機(jī)械地執(zhí)行的規(guī)則或計算步驟序列稱為該計算模型的一個計算注意一個計算機(jī)程序是一個計算（計算模型是計算機(jī)）計算可能永遠(yuǎn)不停止——不是算法。計算的定義4請各位評審老師提出寶貴建議！謝謝！算法是一個滿足下列條件的計算：

有窮性/終止性：有限步內(nèi)必須停止，確定性：每一步都是嚴(yán)格定義和確定的動作，能行性：每一個動作都能夠被精確地機(jī)械執(zhí)行，輸入：有一個滿足給定約束條件的輸入，輸出：滿足給定約束條件的結(jié)果。算法的定義5請各位評審老師提出寶貴建議！謝謝！關(guān)于算法6“算法”的來源中文名稱：周髀算經(jīng)英文名稱“Algorithm”來自于9世紀(jì)波斯數(shù)學(xué)家花拉子米（al-Khwarizmi）“算法”原為“algorism”，即“al-Khwarizmi”的音轉(zhuǎn)，意思是“花拉子米”的運(yùn)算法則在18世紀(jì)演變?yōu)椤癮lgorithm”最早的算法歐幾里德的“求最大公因子算法”請各位評審老師提出寶貴建議！謝謝！問題的定義7算法的目的是求解問題。什么是問題？問題設(shè)Input和Output是兩個集合。一個問題是一個關(guān)系R

Input

Output，Input稱為問題R的輸入集合，Input的每個元素稱為R的一個輸入，Output稱為問題R的輸出或結(jié)果集合，Output的每個元素稱為R的一個結(jié)果。

注意問題定義了輸入和輸出的關(guān)系。

請各位評審老師提出寶貴建議！謝謝！問題的例子8SORT問題定義如下：輸入集合Input={<a1,…,an>|ai是整數(shù)}輸出集合Output={<b1,…,bn>|bi是整數(shù),b1

….

bn}問題SORT={(<a1,…,an>,<b1,…,bn>)|<a1,…,an>

Input,<b1,…,bn>

Output,{a1,…,an}={b1,…,bn}}問題實例問題P的一個實例是P的一個二元組。注意一個算法面向一個問題，而不是僅求解一個問題的一個或幾個實例。

請各位評審老師提出寶貴建議！謝謝！算法示例9問題定義Input=

<a1,....,an>

ai是整數(shù)

output=

<b1,....,bn>

bi是整數(shù),且b1

...

bn

R=

(<a1,...,an>,<b1,...,bn>)

<a1,...,an>

Input,<b1,...,bn>

output,

a1,...,an

=

b1,...,bn}算法的思想—撲克牌游戲請各位評審老師提出寶貴建議！謝謝！算法演示10A

1,......,n

=5,2,4,6,1,3A

1,......,n

=5,2,4,6,1,3A

1,......,n

=2,5,4,6,1,3A

1,......,n

=2,4,5,6,1,3A

1,......,n

=2,4,5,6,1,3A

1,......,n

=1,2,4,5,6,3A

1,......,n

=1,2,3,4,5,6請各位評審老師提出寶貴建議！謝謝！算法描述11Insertion-sort(A)Input:A

1,.....,n

=n個數(shù)output:A

1,.....,n

=n個sorted數(shù)FORj=2TonDokey

A

j

;i

j-1WHILEi>0ANDA

i

>keyDoA

i+1Ai

;i

i-1;A

i+1

key;實例：A

1,......,n

=5,2,4,6,1,3請各位評審老師提出寶貴建議！謝謝！本講內(nèi)容1.1什么是算法？1.2計算機(jī)科學(xué)中算法的位置1.3算法分析引論1.4算法設(shè)計引論1270年代前計算機(jī)科學(xué)基礎(chǔ)的主題沒有被清楚地認(rèn)清。70年代Knuth出版了《TheArtofComputerProgramming》以算法研究為主線確立了算法為計算機(jī)科學(xué)基礎(chǔ)的重要主題1974年獲得圖靈獎。70年代后算法作為計算機(jī)科學(xué)核心推動了計算機(jī)科學(xué)技術(shù)飛速發(fā)展算法是計算機(jī)科學(xué)基礎(chǔ)的重要主題解決一個計算問題的過程可計算否能行可計算否軟件系統(tǒng)用計算機(jī)語言實現(xiàn)算法算法設(shè)計與分析計算機(jī)科學(xué)的體系可計算理論計算模型可計算問題/不可計算問題計算模型的等價性--圖靈/Church命題計算復(fù)雜性理論在給定的計算模型下研究問題的復(fù)雜性固有復(fù)雜性上界下界平均復(fù)雜性問題的分類:P=NP?抽象復(fù)雜性研究算法設(shè)計和分析可計算問題的算法的設(shè)計與分析設(shè)計算法的理論、方法和技術(shù)分析算法的理論、方法和技術(shù)計算機(jī)軟件系統(tǒng)軟件工具軟件應(yīng)用軟件請各位評審老師提出寶貴建議！謝謝！本講內(nèi)容1.1什么是算法？1.2計算機(jī)科學(xué)中算法的位置1.3算法分析引論1.4算法設(shè)計引論17算法正確性一個算法是正確的，如果它對于每一個輸入都最終停止,而且產(chǎn)生正確的輸出。不正確算法：①不停止(在某個輸入上)②對所有輸入都停止，但對某輸入產(chǎn)生不正確結(jié)果近似算法①對所有輸入都停止②產(chǎn)生近似正確的解或產(chǎn)生不多的不正確解算法的正確性分析算法正確性證明證明算法對所有輸入都停止證明對每個輸入都產(chǎn)生正確結(jié)果調(diào)試程序

程序正確性證明:

程序調(diào)試只能證明程序有錯，不能證明程序無錯誤!

20循環(huán)不變量在每次循環(huán)的開始，子數(shù)組A[1..j-1]包含原來數(shù)組中A[1..j-1]但是已經(jīng)有序證明初始化:j=2,A[1..j-1]=A[1..1]=A[1],已經(jīng)有序.維護(hù)：每一層循環(huán)維護(hù)循環(huán)不變量.終止:j=n+1,soA[1..j-1]=A[1..n]有序.插入排序的正確性目的：預(yù)測算法對不同輸入所需資源量復(fù)雜性測度：時間，空間，I/O等,是輸入大小的函數(shù)用途：為求解一個問題選擇最佳算法、最佳設(shè)備需要的數(shù)學(xué)基礎(chǔ)離散數(shù)學(xué)，組合數(shù)學(xué)，概率論，代數(shù)等需要的數(shù)學(xué)能力建立算法復(fù)雜性的數(shù)學(xué)模型數(shù)學(xué)模型化簡算法的復(fù)雜性分析輸入的大小設(shè)Input是問題R的輸入集合，R的輸入大小是一個函數(shù)F：Input

N，N是正整數(shù)集合。示例：矩陣問題的輸入大小=矩陣的維數(shù)圖論問題的輸入大小=圖的邊數(shù)/結(jié)點數(shù)算法復(fù)雜性分析的度量時間復(fù)雜性一個算法對特定輸入的時間復(fù)雜性是該算法對該輸入產(chǎn)生結(jié)果需要的原子操作或“步”數(shù)注意時間復(fù)雜性是輸入大小的函數(shù)我們假設(shè)每一步的執(zhí)行需要常數(shù)時間，實際上每步需要的時間量可能不同。

算法復(fù)雜性分析的度量空間復(fù)雜性一個算法對特定輸入的空間復(fù)雜性是該算法對該輸入產(chǎn)生結(jié)果所需要的存儲空間大小。算法復(fù)雜性分析的度量最壞復(fù)雜性設(shè)Input是問題R的輸入集合，Complexity(X)是求解R的算法A的復(fù)雜性函數(shù)，Size(y)是確定R中輸入大小的函數(shù)，A的最壞復(fù)雜性是Max

Complexity(size(y))

y

Input

最小復(fù)雜性Min

Complexity(size(y))

y

Input

平均復(fù)雜性設(shè)y∈Input,y作為算法A的輸入出現(xiàn)的概率是py，A的平均復(fù)雜性為

算法復(fù)雜性分析的度量26算法分析的模型隨機(jī)訪問模型(Random-Access-Model,RAM)單處理機(jī)，串行執(zhí)行，無并發(fā)基本數(shù)據(jù)類型基本操作(每個操作常數(shù)時間)并行多處理機(jī)模型(PRAM)27插入排序的分析

c1n28插入排序的分析(續(xù))最好代價:有序的數(shù)組tj=1,且6和7行執(zhí)行0次T(n)=c1n+c2(n-1)+c4(n-1)+c5(n-1)+c8(n-1)=(c1+c2+c4+c5+c8)n–(c2+c4+c5+c8)=cn+c‘最壞代價:逆序數(shù)組tj=j,

j=2ntj=

j=2nj=n(n+1)/2-1,且

j=2n(tj–1)=

j=2n(j

–1)=n(n-1)/2T(n)=c1n+c2(n-1)+c4(n-1)+c5(n(n+1)/2-1)+c6(n(n-1)/2)+c7(n(n-1)/2)+c8(n-1)=((c5+c6+c7)/2)n2+(c1+c2+c4+c5/2-c6/2-c7/2+c8)n-(c2+c4+c5+c8)=an2+bn+c平均代價:隨機(jī)數(shù)平均來看,tj=j/