算法和算法復(fù)雜性

算法和算法復(fù)雜性第1頁，共32頁，2023年，2月20日，星期六

圖靈機(jī)中無限長的帶被分成一個個小空格，每格容納一個符號，對每一部圖靈機(jī)而言，帶上允許使用的符號是有限的；

圖靈機(jī)的輸入是由符號組成的有限序列，稱之為符號行，輸入符號行不能含空格符B。

讀寫頭每次左或右移動一格，并根據(jù)控制器的指令閱讀方格中的符號或抹去、重寫方格中的符號，其初始位置是輸入符號行最左邊符號。讀寫頭

帶（B表示空格）B011000B控制器

第2頁，共32頁，2023年，2月20日，星期六

控制器有有限個狀態(tài)，其中啟始狀態(tài)和終止?fàn)顟B(tài)是兩個特殊的狀態(tài)；狀態(tài)可依轉(zhuǎn)移函數(shù)δ進(jìn)行，δ（q，a）=（p，b，v）意為：讀寫頭看到符號a時，處于狀態(tài)q的控制器命令其抹掉a，重寫b，并向v（左或右）移動一格，狀態(tài)改變?yōu)閜；控制器開始處于啟始狀態(tài)，圖靈機(jī)當(dāng)且僅當(dāng)控制器處于終止?fàn)顟B(tài)時停止，此時帶上符號行為輸出。第3頁，共32頁，2023年，2月20日，星期六

顯然，圖靈計(jì)算機(jī)計(jì)算的是從符號行到符號行的函數(shù)，但并不太限制其應(yīng)用范圍,它的計(jì)算時間是指讀寫頭的移動次數(shù),計(jì)算占用的空間是指帶上被訪問過的方格數(shù),當(dāng)輸入符號行是x時,圖靈機(jī)M的計(jì)算時間(或占用空間)記為TimeM(x)(或SpaceM(x))。

對意義明確的數(shù)學(xué)問題是否會不存在算法呢？圖靈精彩地論證了這樣的不可判定問題確實(shí)存在！第4頁，共32頁，2023年，2月20日，星期六

一個典型問題就是“停機(jī)問題”：給定一個帶有輸入的計(jì)算機(jī)程序，它會停機(jī)嗎？圖靈證明了，不存在一個算法能對該問題的一切例子給出正確的答案。

對于給定的問題，如果存在一種算法，可以對該問題的一切例子給出正確的答案，那麼這個問題就是可以計(jì)算的。

可重復(fù)性歸根于因果關(guān)系的確定性，這種確定性也是當(dāng)今世界上存在的各式各樣計(jì)算機(jī)的共同特點(diǎn)。第5頁，共32頁，2023年，2月20日，星期六2、不確定型計(jì)算和算法復(fù)雜性（1）不確定型計(jì)算：

一個不確定型圖靈機(jī)M計(jì)算一函數(shù)f（x）時，必須假定M滿足以下條件：①若f(x)無定義,則對輸入x,M的任何計(jì)算道路都是(時間)無限長的;②若f(x)有定義,則對輸入x,M必有一有限長的道路；并且對任何有限長的計(jì)算道路，計(jì)算結(jié)果都是f(x)。第6頁，共32頁，2023年，2月20日，星期六

對這種圖靈機(jī)M，TimeM（x）表示輸入x時，M可能使用的最短時間，SpaceM（x）表示輸入x時，M可能使用的最少空間?？梢栽诓淮_定型計(jì)算機(jī)上實(shí)施的計(jì)算稱為不確定型計(jì)算。（Non-deterministiccomputation）第7頁，共32頁，2023年，2月20日，星期六

&

算法復(fù)雜性采用該算法得到最終答案時所用的時間。與此有關(guān)的因素有：·計(jì)算機(jī)本身的速度·問題的規(guī)模——一般指問題的輸入長度（2）算法復(fù)雜性與算法分析為了衡量算法的效果所廣泛采用的標(biāo)準(zhǔn)是：第8頁，共32頁，2023年，2月20日，星期六注意：同一規(guī)模的例子用同一算法，同樣的輸入長度所需運(yùn)算時間也可能相差很遠(yuǎn)！

如，用單純形法解LP，即使約束條件的系數(shù)矩陣階數(shù)固定不變，所需的初等運(yùn)算次數(shù)也會隨著參數(shù)A、b、C的不同而有較大差別。當(dāng)取C≤0的極端情況，不需要進(jìn)行旋轉(zhuǎn)運(yùn)算，初始可行解就是最優(yōu)解；但若選取不利的參數(shù)，達(dá)到最優(yōu)解所需要的迭代步驟可能就非常多。第9頁，共32頁，2023年，2月20日，星期六

為了避免由于不同輸入而對算法行為產(chǎn)生巨大差別，考察所有規(guī)模為n的輸入，對這些算法的不同行為中的最壞行為定義為該算法關(guān)于輸入規(guī)模為n的復(fù)雜性。因此，算法復(fù)雜性是輸入規(guī)模的函數(shù)，比如10n3,2n,nlog2n等。第10頁，共32頁，2023年，2月20日，星期六輸入規(guī)模足夠大時，在復(fù)雜性函數(shù)中，增長速度較慢的項(xiàng)（如nlog2n+5n），終將被增長速度很快的項(xiàng)超過（該例中n>>1000時，nlog2n>5n）。在算法復(fù)雜性研究中，只有當(dāng)輸入規(guī)模很大時，研究其計(jì)算行為才有意義，因?yàn)椋褐挥幸?guī)模大的輸入，才能確定算法可應(yīng)用性的限制。比如復(fù)雜性為10n3與復(fù)雜性為9n3的算法間的差別可以忽略不計(jì)，因?yàn)檫@可以通過技術(shù)革新，使計(jì)算機(jī)速度提高10倍而得到補(bǔ)償。第11頁，共32頁，2023年，2月20日，星期六(c)如果存在兩個常數(shù)c,c'>0,使得當(dāng)n足夠大時有c'g(n)≤f(n)≤cg(n),則記f(n)=Θg(n)，用記號f(n)≌g(n)代替f(n)=Θ(g(n)),易見≌是一個等價關(guān)系，在該等價關(guān)系下，f(n)的等價類（即f(n)=Θ(g(n))的所有g(shù)(n)的集合）稱為f(n)的增長速度。定義

設(shè)f(n),g(n)是定義在正整數(shù)上的正實(shí)值函數(shù)(a)如果存在一個常數(shù)c>0,使得當(dāng)n足夠大時,有f(n)≤cg(n),則記f(n)=O(g(n))；(b)如果存在一個常數(shù)c>0,使得當(dāng)n足夠大時有f(n)≥cg(n),則記f(n)=Ω(g(n))；第12頁，共32頁，2023年，2月20日，星期六求出一個算法所需時間比較好上界的過程稱為算法分析。

算法分析中常常使用初等運(yùn)算——算術(shù)運(yùn)算、比較、轉(zhuǎn)移指令等的步數(shù)表示一個算法在假設(shè)的計(jì)算機(jī)上執(zhí)行時所需的時間，即每做一次初等運(yùn)算，需要一個單位時間。而用算法的輸入規(guī)模的函數(shù)度量該算法的復(fù)雜性。第13頁，共32頁，2023年，2月20日，星期六

為了把輸入提供給計(jì)算機(jī)求解，必須用固定字母表（0，1，或打字機(jī)上的符號，或ASCII字母）上的符號串來表示它們，這就是所謂的編碼。當(dāng)把算法的輸入表示為符號串時，那麼輸入規(guī)模就定義為該符號串的長度（符號串中符號的數(shù)目），稱為輸入長度。第14頁，共32頁，2023年，2月20日，星期六例1．以某一個固定數(shù)為基底的運(yùn)算系統(tǒng)（如十進(jìn)制或二進(jìn)制）中，表示一個整數(shù)n的輸入規(guī)模：，因?yàn)閘ogBn=logn/logB,B固定后logB是一個常數(shù)。例2.試分析LP的規(guī)模.

設(shè)A、b、c中的元素均為整數(shù)，則LP的規(guī)模就是表示A、b、c所需符號的數(shù)目。因?yàn)榭梢园讯M(jìn)制（十進(jìn)制）表示的矩陣中元素排成一行，用符號線適當(dāng)?shù)馗糸_以表示矩陣的行或列，從而矩陣也可以表示為符號串。所以，m×n的LP問題規(guī)模為Θ(mn+）其中p是所有非零參數(shù)的乘積。第15頁，共32頁，2023年，2月20日，星期六（3）多項(xiàng)式時間算法①決定一個算法的實(shí)際效用，要看其已知的最好時間上界之增長速度。目前計(jì)算機(jī)科學(xué)家們有一個公認(rèn)的看法：解一個計(jì)算問題的算法，當(dāng)其復(fù)雜性隨輸入規(guī)模的增加而呈多項(xiàng)式地增長時，這個算法才是實(shí)際有效的。第16頁，共32頁，2023年，2月20日，星期六

②定義（多項(xiàng)式算法）設(shè)有解某種問題的一個算法，對于輸入長度為L的具體問題，其計(jì)算步驟有一個上界P（L），若P（y）是y的多項(xiàng)式，則稱此算法是一個多項(xiàng)式時間算法（Polynomial-TimeAlgorithmforLinearProgramming），簡稱多項(xiàng)式算法。第17頁，共32頁，2023年，2月20日，星期六

函數(shù)

近似值NNlognn3106n8

103310001014

1006641000，0001022

1000996610910302nnlognn！

102420993，628，800

1．27×1030

1．93×101310158

1.05×103017.89×10294×102567③特點(diǎn):

表1多項(xiàng)式和指數(shù)函數(shù)增長情況表

當(dāng)輸入規(guī)模增大時，任意一個多項(xiàng)式算法終將變得比指數(shù)算法更有效，見表1。第18頁，共32頁，2023年，2月20日，星期六在某種意義上，它很好地利用了技術(shù)發(fā)展的優(yōu)點(diǎn)。

每次技術(shù)突破，計(jì)算機(jī)速度提高10倍，則多項(xiàng)式算法原來1小時內(nèi)所能解算例子的最大規(guī)?？稍黾覥倍，其中0<C<10,而指數(shù)算法所能解算的例子規(guī)模只能增加一個常數(shù).

表2顯示了多項(xiàng)式算法利用技術(shù)發(fā)展的優(yōu)點(diǎn)情況.第19頁，共32頁，2023年，2月20日，星期六表2多項(xiàng)式算法利用技術(shù)發(fā)展的優(yōu)點(diǎn)情況表

函數(shù)

一天內(nèi)能解例子的規(guī)模計(jì)算機(jī)速度提高10倍后所能解例子的規(guī)模

nnlognn2n3108n4

10120.948×101110610410

10130.87×10123.16×1062.15×10418

2n10nnlognn!

40127914

43139515第20頁，共32頁，2023年，2月20日，星期六

多項(xiàng)式算法有較好的封閉性——n個多項(xiàng)式算法可以結(jié)合起來解同一問題的某些特殊情形；一個多項(xiàng)式算法也可以利用另一個多項(xiàng)式算法作為“子程序”，并且最后的結(jié)果仍然是一個多項(xiàng)式算法。第21頁，共32頁，2023年，2月20日，星期六（4）P類、NP類、NP完全類、

①稱具有多項(xiàng)式時間算法的一類問題為P類問題，簡稱P問題。如：有向圖中的路、最大匹配問題、最小支撐樹問題等；②NP類問題也叫不確定性問題（或稱非多項(xiàng)式確定問題）。如果有一個用于求解此問題的算法，對于它可以找到一個多項(xiàng)式時間算法來驗(yàn)證該算法所得的結(jié)果是否為此問題的解，則稱此問題屬于NP類問題，簡稱NP問題。③NP完備的（NP-Complete）——如果一個判定問題A是NP的，而且所有其他NP問題都能多項(xiàng)式地歸結(jié)到A，則稱A是NP完備的。第22頁，共32頁，2023年，2月20日，星期六

所謂多項(xiàng)式地歸結(jié)，指的是多項(xiàng)式地時間歸結(jié)，其定義是：設(shè)A1、A2都是判定（即是-否）問題，說A1在多項(xiàng)式時間內(nèi)歸結(jié)為A2，當(dāng)且僅當(dāng)A1有個多項(xiàng)式時間算法A1

，并且A1是多次地以單位費(fèi)用把A2的算法A2用作子程序的算法。則把A1叫做A1到A2的多項(xiàng)式時間歸結(jié)。

于是，若問題A是NP完備的，若A有有效算法，則每個NP問題也有有效算法。命題：如果A1多項(xiàng)式歸結(jié)到A2，而A2有多項(xiàng)式算法，則A1也有多項(xiàng)式算法。第23頁，共32頁，2023年，2月20日，星期六

常用的證明一個問題為P的方法一、先設(shè)計(jì)出求解問題Π的一個算法；然后證明其正確性，即可利用該算法精確求解問題Π；最后，通過仔細(xì)分析算法的實(shí)現(xiàn)過程來估計(jì)它所需的總的計(jì)算工作量，即其計(jì)算復(fù)雜性，若所得估計(jì)值可用問題規(guī)模參數(shù)（如輸入長度、問題維數(shù)等）的一個多項(xiàng)式函數(shù)來界定，則表明該算法為多項(xiàng)式時間算法，從而得到問題P屬于Π。如背包問題、排序問題等采用這種方法來證明問題屬于P時，一般總要充分利用所證明問題的具體特性，以便設(shè)計(jì)出適當(dāng)?shù)那蠼馑惴?使得它能夠構(gòu)成求解原問題的多項(xiàng)式時間算法。由于其對于具體問題的依賴性與多變性，很難指定一個通用的證明步驟或方法。第24頁，共32頁，2023年，2月20日，星期六

常用的證明一個問題為P的方法二、通過某種轉(zhuǎn)換或邏輯推理來進(jìn)行。常見的技巧有：證明可采用一些簡單的、可在多項(xiàng)式時間內(nèi)完成的變換方法，將原問題轉(zhuǎn)換為另一已知的P類問題的求解；說明可通過遞推、分解等方法來對原問題進(jìn)行簡化，使簡化后的問題很容易在多項(xiàng)式時間內(nèi)求解，而所采用的分解等策略也可在多項(xiàng)式時間內(nèi)完成；直接考察原問題的可行解所可能存在的各種情形，當(dāng)然這些可能的不同情形不會超過問題規(guī)模的某個多項(xiàng)式，并說明在每種情況下均可在多項(xiàng)式時間內(nèi)求解原問題第25頁，共32頁，2023年，2月20日，星期六

COOK定理為了證明一個問題是NP-完備的，我們必須證明兩件事：(a)該問題是NP的(b)所有其他NP問題多項(xiàng)式轉(zhuǎn)換到該問題實(shí)際上，部分(b)通常用證明某個已知的NP-完備問題可以多項(xiàng)式變換到要證的問題完成的.不過第一個NP-完備性證明必須包含部分(b)的直接證明。為此我們需要在證明中應(yīng)用所有各種NP問題的共性。共性便是對于每個‘是’實(shí)例x至少存在一個證明c(x)和一個證明檢驗(yàn)算法Λ第26頁，共32頁，2023年，2月20日，星期六證明檢驗(yàn)算法Λinstance$certificate符號串程序讀寫頭第27頁，共32頁，2023年，2月20日，