計(jì)算理論導(dǎo)引w2時(shí)間復(fù)雜性a np及證明

1計(jì)算理論第7章時(shí)間復(fù)雜性2引言Church-Turing論題：能夠用總停機(jī)的Turing機(jī)計(jì)算的函數(shù)和識(shí)別的語(yǔ)言是可計(jì)算的（可判定的）；理論可計(jì)算計(jì)算復(fù)雜性理論研究計(jì)算模型在各種資源（主要是時(shí)間、空間等）限制下的計(jì)算能力；

實(shí)際可計(jì)算一個(gè)可以計(jì)算的問題需要多少時(shí)間和空間？64層次梵塔，1秒鐘移動(dòng)1000片（計(jì)算機(jī)作），要多少時(shí)間？(264-1)/1000=5.846億年3引言復(fù)雜度和時(shí)間：每秒作106的基本運(yùn)算需要的時(shí)間N=10N=20N=30N=40N=50N=60N10-5秒2*10-5秒3*10-5秒4*10-5秒5*10-5秒6*10-5秒N210-4秒4*10-4秒9*10-4秒16*10-525*10-436*10-4N310-3秒8*10-3秒27*10-4秒64*10-30.125秒0.216秒N510-1秒3.224秒1.7分5.2分13分2N10-3秒118.9分12.7天35.7年366世紀(jì)3N0.059秒58分6.5年3855世紀(jì)2億世紀(jì)1.3*1013世紀(jì)4引言Complexity：Hamilton回路問題（HC）：任給一個(gè)無向圖G，問G中有Hamilton回路嗎？Hamilton回路是指經(jīng)過每一個(gè)頂點(diǎn)且每一個(gè)頂點(diǎn)只經(jīng)過一次的回路。設(shè)G有n個(gè)頂點(diǎn)，由于回路沒有始點(diǎn)和終點(diǎn)，可以任意定一個(gè)頂點(diǎn)作為排列的第一個(gè)頂點(diǎn)，共有（n-1）！個(gè)排列。當(dāng)n=25時(shí)，24！=6.2*1023.假設(shè)用一臺(tái)超級(jí)計(jì)算機(jī)計(jì)算，每秒可以檢查1億個(gè)排列。每年有3.15*107秒，不停地工作，每年可以檢查3.15*1015個(gè)排列。檢查完所有的排列需要1.97*108年，即1億9千7百年！計(jì)算復(fù)雜性理論就是要研究計(jì)算模型在各種資源限制下的計(jì)算能力。將問題劃分成HardandEasy兩大類。5主要內(nèi)容7.1度量復(fù)雜性 大O和小o記法、分析算法、模型間的復(fù)雜性關(guān)系7.2P類 多項(xiàng)式時(shí)間、P中的問題舉例7.3NP類

NP中的問題舉例、P與NP問題7.4NP完全性 多項(xiàng)式時(shí)間可歸約性、NP完全性的定義、庫(kù)克-列文定理7.5幾個(gè)NP完全問題（自學(xué)） 頂點(diǎn)覆蓋問題、哈密頓路徑問題、子集和問題6度量復(fù)雜性考察下列例子： 語(yǔ)言A={0k1k|k

≥0}，顯然A是一個(gè)可判定的語(yǔ)言。 考察下面判定A的單帶TMM1

M1=“對(duì)于輸入串w：1)掃描帶子，如果在1的右邊發(fā)現(xiàn)0，就拒絕。2)如果帶上既有0也有1，就重復(fù)下一步。3)掃描帶子，刪除一個(gè)0和一個(gè)1。4)如果所有1都被刪除以后還有0，或者所有0都被刪除以后還有1，就拒絕。否則，如果在帶上既沒有剩下0也沒有剩下1，就接受。考察判定A的圖靈機(jī)M1的算法所需的時(shí)間。7度量復(fù)雜性把算法的運(yùn)行時(shí)間純粹作為表示輸入字符串的長(zhǎng)度來計(jì)算，而不考慮其它參數(shù)。最壞情況分析（worst-caseanalysis）：考慮在某特定長(zhǎng)度的所有輸入上的最長(zhǎng)運(yùn)行時(shí)間。平均情況分析（average-caseanalysis）：考慮在某特定長(zhǎng)度的所有輸入上的運(yùn)行時(shí)間的平均值。8度量復(fù)雜性定義8.1令M是一個(gè)在所有輸入上都停機(jī)的確定型圖靈機(jī)。M的運(yùn)行時(shí)間或者時(shí)間復(fù)雜度，是一個(gè)函數(shù)

f:N

N，其中N是非負(fù)整數(shù)集合，f(n)是M在所有長(zhǎng)度為n的輸入上運(yùn)行時(shí)所經(jīng)過的最大步數(shù)。若f(n)是M的運(yùn)行時(shí)間，則稱M在時(shí)間f(n)內(nèi)運(yùn)行，M是時(shí)間圖靈機(jī)。通常使用n表示輸入的長(zhǎng)度。9漸進(jìn)分析因?yàn)樗惴ǖ木_運(yùn)行時(shí)間通常是一個(gè)復(fù)雜的表達(dá)式，所以一般是估計(jì)它的趨勢(shì)和級(jí)別。通過一種稱為漸進(jìn)分析

(asymptoticanalysis)的方便的估計(jì)形式，可以試圖了解算法在長(zhǎng)輸入上的運(yùn)行時(shí)間。只考慮算法運(yùn)行時(shí)間的表達(dá)式的最高項(xiàng)，而忽略該項(xiàng)的系數(shù)和其它低次項(xiàng)，因?yàn)樵谠陂L(zhǎng)輸入上，最高次項(xiàng)的影響相比其它項(xiàng)占據(jù)主導(dǎo)地位。例如，函數(shù)f(n)=6n3+2n2+20n+45

稱f漸進(jìn)地不大于n3，表達(dá)這種關(guān)系的漸進(jìn)記法或大O記法是f(n)=O(n3)。10大O和小o記法定義8.2設(shè)f和g

是兩個(gè)函數(shù)f，g：N

R+。稱f(n)=O(g(n))，若存在正整數(shù)c和

n0，使得對(duì)所有

n≥n0

有f(n)≤cg(n)當(dāng)f(n)=O(g(n))時(shí)，稱g(n)是f(n)的上界，或更準(zhǔn)確地說，

g(n)是f(n)的漸近上界，以強(qiáng)調(diào)沒有考慮常數(shù)因子。11大O和小o記法例8.3

f1(n)是函數(shù)5n3+2n2+22n+6。保留最高次項(xiàng)5n3，并且舍去它的系數(shù)5，得到f1=O(n3)。驗(yàn)證該結(jié)果是否滿足上面的形式定義。令c=6，n0=10，則對(duì)于所有n

≥10，有5n3+2n2+22n+6≤6n3。此外，有f1=O(n4)，因?yàn)閚4比n3大，它也是f1的一個(gè)漸近上界。但是f1不等于O(n2)，不論給c和n0賦什么值，始終不滿足定義的要求。12大O和小o記法例8.4

大O記法以一種特別的方式與對(duì)數(shù)相互影響。通常寫對(duì)數(shù)時(shí)必須指明基數(shù)(或稱為對(duì)數(shù)的底)，如x=log2n

。這里基數(shù)2表明該等式等價(jià)于等式2x=n。logbn的值隨著基數(shù)b的改變而乘以相應(yīng)的常數(shù)倍，因?yàn)橛泻愕仁絣ogbn=log2n/log2b。所以，寫f(n)=O(logn)

時(shí)不必再指明基數(shù)，因?yàn)樽罱K要忽略常數(shù)因子。13大O和小o記法令f2(n)是函數(shù)3nlog2n+5nlog2log2n+2。此時(shí)f2(n)

=O(nlogn)，因?yàn)?/p>

logn比loglogn更占支配位置。f(n)

=O(n2)+O(n)等價(jià)于f(n)

=O(n2)當(dāng)O出現(xiàn)在指數(shù)位置，如f(n)=2O(n)，代表著2cn的一個(gè)上界。f(n)=2O(logn)，代表nc。（由n=2logn

得nc=2clog2n）2O(1)代表了同樣的界，因?yàn)楸磉_(dá)式O(1)代表不超過某個(gè)固定常數(shù)的上界。14大O和小o記法我們經(jīng)常導(dǎo)出nc

的界，c是大于0的常數(shù)。這種界稱為多項(xiàng)式界(polynamialbound)。形如的界，當(dāng)是大于0的實(shí)數(shù)時(shí)，稱為指數(shù)界(exponentialbound)。大O記法指一個(gè)函數(shù)漸近地不大于另一個(gè)函數(shù)。小o記法是漸進(jìn)的小于另一個(gè)函數(shù)。大O記法與小o記法的區(qū)別類似于≤和＜之間的區(qū)別。15大O和小o記法定義8.5設(shè)f和g是兩個(gè)函數(shù)f,g:N

R+，如果則稱f(n)=o(g(n))。換言之，f(n)=o(g(n))意味著對(duì)于任何實(shí)數(shù)c＞0，存在一個(gè)數(shù)n0，使得對(duì)所有n≥n0，f(n)＜cg(n)。16大O和小o記法例8.6

容易驗(yàn)證下面的等式。

1)