算法設(shè)計與分析復(fù)習(xí)

1、18第1章算法概述算法概述算法是若干指令的有窮序列，滿足性質(zhì)：(1)輸入(2)輸出(3)確定性(4)有限性。算法復(fù)雜性分析主要包括空間復(fù)雜性和時間復(fù)雜性。算法復(fù)雜性分析（1）漸近上界記號OO(g(n))=f(n)|存在正常數(shù)c和n0使得對所有n?n0有：0?f(n)?cg(n)（2）漸近下界記號??(g(n))=f(n)|存在正常數(shù)c和n0使得對所有n?n0有：0?cg(n)?f(n)（3）緊漸近界記號??(g(n))=f(n)|存在正

2、常數(shù)c1c2和n0使得對所有n?n0有：c1g(n)?f(n)?c2g(n)定理1：?(g(n))=O(g(n))??(g(n))最常見的多項式時間算法的漸近時間復(fù)雜度O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n2)＜O(n3)最常見的指數(shù)時間算法的漸近時間復(fù)雜度O(2n)＜O(n！)＜O(nn)通用分治遞推式大小為n的原問題分成若干個大小為nb的子問題，其中a個子問題需要求解，而cnk是合并各個子問題的解需要的工作量。

3、NP完全性理論P是所有可在多項式時間內(nèi)用確定算法求解的判定問題的集合。NP是所有可在多項式時間內(nèi)用不確定算法求解的判定問題的集合。（NP難度）對于問題Q以及任意問題Q1?NP，都有Q1∝Q，則Q是NP難度（NPhard）的。其中∝表示約化，Q1∝Q，表示Q1可以在多項式時間轉(zhuǎn)化為問題Q，從而可通過調(diào)用問題Q的算法求解。（NP完全）對于問題Q?NP，Q是NP難度的，則稱Q是NPC（NPcomplete）的。PNPNPC的關(guān)系38voidQ

4、uickStQuickSt(Typea[]intpintr)if(pTypeRomizedRomized(Typea[]intpintrintk)if(p==r)returna[p]inti=RomizedPartition(apr)j=ip1if(k=j)returnRomized(apik)elsereturnRomized(ai1rkj)在最壞情況下，算法romizedromized需要O(n2)計算時間。但算法romizedro

5、mized可以在O(n)平均時間內(nèi)找出n個輸入元素中的第k小元素。進一步改進：?將n個輸入元素劃分成?n5?個組，每組5個元素，只可能有一個組不是5個元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共?n5?個。?遞歸調(diào)用來找出這?n5?個元素的中位數(shù)。如果?n5?是偶數(shù)，就找它的2個中位數(shù)中較大的一個。以這個元素作為劃分基準。?所以按此基準劃分所得的2個子數(shù)組的長度都至少縮短14。第3章動態(tài)規(guī)劃動態(tài)規(guī)劃算法的思想: