海量數據計算研究中心MassiveDataComputingLab@HIT算法設計與分析第一章

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

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

Input

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

注意問題定義了輸入和輸出的關系。

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

….

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

Input,<b1,…,bn>

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

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

<a1,....,an>

ai是整數

output=

<b1,....,bn>

bi是整數,且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個數output:A

1,.....,n

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

程序正確性證明:

程序調試只能證明程序有錯，不能證明程序無錯誤!

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

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

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

Complexity(size(y))

y

Input

最小復雜性Min

Complexity(size(y))

y

Input

平均復雜性設y∈Input,y作為算法A的輸入出現的概率是py，A的平均復雜性為

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

c1n28插入排序的分析(續)最好代價:有序的數組tj=1,且6和7行執行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‘最壞代價:逆序數組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平均代價:隨機數平均來看,tj=j/