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

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

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

3、NP完全性理論P(yáng)是所有可在多項(xiàng)式時(shí)間內(nèi)用確定算法求解的判定問題的集合。NP是所有可在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判定問題的集合。（NP難度）對(duì)于問題Q以及任意問題Q1?NP，都有Q1∝Q，則Q是NP難度（NPhard）的。其中∝表示約化，Q1∝Q，表示Q1可以在多項(xiàng)式時(shí)間轉(zhuǎn)化為問題Q，從而可通過調(diào)用問題Q的算法求解。（NP完全）對(duì)于問題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)計(jì)算時(shí)間。但算法romizedro

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