測(cè)度和復(fù)雜性分類

《測(cè)度和復(fù)雜性分類》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、語言與計(jì)算理論導(dǎo)引可計(jì)算函數(shù)第五部分計(jì)算復(fù)雜性導(dǎo)引到現(xiàn)在，在我們討論決策問題時(shí)，我們只考慮問題是否具有可解的性質(zhì)。在現(xiàn)實(shí)生活中，用于解決問題的計(jì)算資源是有限的：可獲得的時(shí)間和空間都是有限的。結(jié)果，一些可解的問題的中等規(guī)模的實(shí)例在實(shí)際中都變得很難以解決。在第5部分，我們考慮鑒別難解問題的方法，主要通過描述解決問題的一定規(guī)模的實(shí)例時(shí)，所需要的時(shí)間和內(nèi)存的數(shù)量。雖然，強(qiáng)調(diào)的重點(diǎn)是運(yùn)行時(shí)間，我們也給出有關(guān)空間的基本定義，并提到涉及空間的最基本的結(jié)果。在第14章，我們首先引入涉及增長(zhǎng)率的記號(hào)和術(shù)語，這允許我們?cè)诤竺嬲鹿?jié)以合理的方式討論象“多少時(shí)間？”這樣的問題。我們把這些數(shù)量問題與我們特

2、定的計(jì)算模型相聯(lián)系，然后討論一些基本的復(fù)雜類。這也是根據(jù)問題和語言內(nèi)在的復(fù)雜性對(duì)它們分類的方法。為了區(qū)分易解問題和難解問題（注意，前面我們討論的可解問題和無解問題），正如我們將在第15章討論的，常用的標(biāo)準(zhǔn)是在圖林機(jī)上是多項(xiàng)式時(shí)間可解的。根據(jù)這個(gè)標(biāo)準(zhǔn)，許多問題是易解的，也有些問題是難解的。我們可以修改第12章的規(guī)約技術(shù)得到這兩類問題的例子。也許更有趣的問題是根據(jù)這個(gè)標(biāo)準(zhǔn)，至今仍然無法判斷的一些問題，沒有人發(fā)現(xiàn)這些問題的多項(xiàng)式時(shí)間解決方法，但是也沒有人能夠證明不存在多項(xiàng)式時(shí)間解決方法。NP完全的概念就是接近這個(gè)主題的一個(gè)方法。在第15章的最后兩節(jié)，我們給出可滿足問題的NP完全性的c

3、ook證明和一些通過多項(xiàng)式時(shí)間規(guī)約被證明是NP完全的組合問題的例子。14測(cè)度和復(fù)雜性分類14.1函數(shù)的增長(zhǎng)率計(jì)算問題的復(fù)雜性能夠通過固定的計(jì)算模型來討論，主要考慮為了解決這個(gè)問題，需要多少機(jī)器的資源（通常指時(shí)間和空間）。為了對(duì)兩個(gè)問題內(nèi)在復(fù)雜性進(jìn)行有意義的比較，有必要考察一定范圍內(nèi)的實(shí)例的解決情況。如果我們把運(yùn)行時(shí)間作為標(biāo)準(zhǔn)，比如，最常用的方法是比較兩個(gè)運(yùn)行時(shí)間的增長(zhǎng)率，每個(gè)運(yùn)行時(shí)間都看成是實(shí)例規(guī)模的函數(shù)。我們引入一些處理運(yùn)行時(shí)間的數(shù)量的增長(zhǎng)率的定義和記號(hào)。我們從一個(gè)比較4個(gè)簡(jiǎn)單函數(shù)的例子開始。例子14.1我們考慮函數(shù)p1(n)=2n2p2(n)=n2+3n+7P3(n)=n3

4、q(n)=2n表14.1顯示了這4個(gè)函數(shù)對(duì)應(yīng)部分變量取值n的各自的函數(shù)值，這些函數(shù)值很清楚顯示了每個(gè)函數(shù)的增長(zhǎng)趨勢(shì)。對(duì)于比較小的值n，p2(n)的值遠(yuǎn)遠(yuǎn)大于p1(n)，但是當(dāng)n=1000時(shí)，p2(n)中低階的項(xiàng)3n+7變得相對(duì)可忽略了，而p1中的因子2幾乎完全決定了p1和p2之間的差別。p3是更高階的多項(xiàng)式，盡管沒有額外的因子和低階項(xiàng)，但是它的值的增長(zhǎng)速度比前兩個(gè)函數(shù)都要快很多。更驚人的增長(zhǎng)趨勢(shì)體現(xiàn)在第4個(gè)指數(shù)函數(shù)q上。我們?cè)俅慰吹綄?duì)于最前面的幾個(gè)小數(shù)值沒有什么特別的地方，但是對(duì)于n=10之后的數(shù)值，它就比其他3個(gè)函數(shù)值都要大了，當(dāng)n=1000時(shí)，p3(n)是1百萬，而q(n)

5、則是難以想象地大了。如果表中數(shù)據(jù)的單位是納秒（nanosecond，又譯毫微秒，一秒的10億分之一），那么p3(1000)表示1秒，而q(1000)表示超過3*10282世紀(jì)。加入表14.113陶曉鵬Copyright2003語言與計(jì)算理論導(dǎo)引可計(jì)算函數(shù)表14.1展示了不同增長(zhǎng)率的效果，p1和p2有不同的規(guī)模，主要是因?yàn)閜1的因子2，但是它們的增長(zhǎng)率是一致的。立方多項(xiàng)式的增長(zhǎng)率更大一些，但是這三個(gè)多項(xiàng)式的增長(zhǎng)率都遠(yuǎn)遠(yuǎn)小于指數(shù)函數(shù)。一旦我們有了能夠精確描述增長(zhǎng)率的定義，其中一個(gè)我們感興趣的主要區(qū)別將是多項(xiàng)式增長(zhǎng)率和指數(shù)增長(zhǎng)率之間的區(qū)別。這個(gè)例子顯示的許多明顯的特征將體現(xiàn)在定義中。

6、定義14.1如果f,g:N?N是部分函數(shù)，每個(gè)函數(shù)除了在有限個(gè)點(diǎn)外，其他值都是有定義的。如果存在常量C和n0，使得對(duì)于每個(gè)n>=n0，f(n)和g(n)都是有定義的，且f(n)<=Cg(n)，那么我們寫f(n)=O(g(n))（或者簡(jiǎn)單地，f=O(g)）如果對(duì)于每個(gè)正常數(shù)C，存在一個(gè)常量n0，使得對(duì)于每個(gè)n>=n0，都有f(n)<=Cg(n)，那么我們寫f(n)=o(g(n))（或者簡(jiǎn)單地，f=o(g)）最后，如果f=O(g)且g=O(f)，則寫成f=Q(g)語句f=O(g)，f=o(g)和f=Q(g)分別讀著“f是g的大O”，“f是g的小o”和“f是g的大Q”。所有這些語句可

7、以用比率f(n)/g(n)來重新描述，假設(shè)g(n)最終會(huì)大于0。說f=o(g)意味著當(dāng)n趨于無窮大時(shí)，這個(gè)比率的極限為0，而f=O(g)表示這個(gè)極限是有界的，而f=Q(g)，如果兩個(gè)函數(shù)都最終是非0的，則表示f/g和g/f的極限值都是有界的，即f/g的極限值介于兩個(gè)固定的正數(shù)之間。如果f=O(g)不成立，則寫成f1O(g)，類似地，得到另外兩個(gè)不成立的表示法。f1O(g)意味著不存在常數(shù)C，使得對(duì)于所有的n的大值，f(n)<=Cg(n)，換句話說，比率f(n)/g(n)是無界的。一個(gè)語句，比