算法和算法復雜性1課件

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

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

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

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

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

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

對意義明確的數(shù)學問題是否會不存在算法呢？圖靈精彩地論證了這樣的不可判定問題確實存在！

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

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

可重復性歸根于因果關系的確定性，這種確定性也是當今世界上存在的各式各樣計算機的共同特點。2、不確定型計算和算法復雜性（1）不確定型計算：

一個不確定型圖靈機M計算一函數(shù)f（x）時，必須假定M滿足以下條件：①若f(x)無定義,則對輸入x,M的任何計算道路都是(時間)無限長的;②若f(x)有定義,則對輸入x,M必有一有限長的道路；并且對任何有限長的計算道路，計算結果都是f(x)。

對這種圖靈機M，TimeM（x）表示輸入x時，M可能使用的最短時間，SpaceM（x）表示輸入x時，M可能使用的最少空間?？梢栽诓淮_定型計算機上實施的計算稱為不確定型計算。（Non-deterministiccomputation）

&

算法復雜性采用該算法得到最終答案時所用的時間。與此有關的因素有：·計算機本身的速度·問題的規(guī)?！话阒竼栴}的輸入長度（2）算法復雜性與算法分析為了衡量算法的效果所廣泛采用的標準是：注意：同一規(guī)模的例子用同一算法，同樣的輸入長度所需運算時間也可能相差很遠！

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

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

設f(n),g(n)是定義在正整數(shù)上的正實值函數(shù)(a)如果存在一個常數(shù)c>0,使得當n足夠大時,有f(n)≤cg(n),則記f(n)=O(g(n))；(b)如果存在一個常數(shù)c>0,使得當n足夠大時有f(n)≥cg(n),則記f(n)=Ω(g(n))；求出一個算法所需時間比較好上界的過程稱為算法分析。

算法分析中常常使用初等運算——算術運算、比較、轉(zhuǎn)移指令等的步數(shù)表示一個算法在假設的計算機上執(zhí)行時所需的時間，即每做一次初等運算，需要一個單位時間。而用算法的輸入規(guī)模的函數(shù)度量該算法的復雜性。

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

設A、b、c中的元素均為整數(shù)，則LP的規(guī)模就是表示A、b、c所需符號的數(shù)目。因為可以把二進制（十進制）表示的矩陣中元素排成一行，用符號線適當?shù)馗糸_以表示矩陣的行或列，從而矩陣也可以表示為符號串。所以，m×n的LP問題規(guī)模為Θ(mn+）其中p是所有非零參數(shù)的乘積。（3）多項式時間算法①決定一個算法的實際效用，要看其已知的最好時間上界之增長速度。目前計算機科學家們有一個公認的看法：解一個計算問題的算法，當其復雜性隨輸入規(guī)模的增加而呈多項式地增長時，這個算法才是實際有效的。

②定義（多項式算法）設有解某種問題的一個算法，對于輸入長度為L的具體問題，其計算步驟有一個上界P（L），若P（y）是y的多項式，則稱此算法是一個多項式時間算法（Polynomial-TimeAlgorithmforLinearProgramming），簡稱多項式算法。

函數(shù)

近似值NNlognn3106n8

103310001014

1006641000，0001022

1000996610910302nnlognn！

102420993，628，800

1．27×1030

1．93×101310158

1.05×103017.89×10294×102567③特點:

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

當輸入規(guī)模增大時，任意一個多項式算法終將變得比指數(shù)算法更有效，見表1。在某種意義上，它很好地利用了技術發(fā)展的優(yōu)點。

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

表2顯示了多項式算法利用技術發(fā)展的優(yōu)點情況.表2多項式算法利用技術發(fā)展的優(yōu)點情況表

函數(shù)

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

nnlognn2n3108n4

10120.948×101110610410

10130.87×10123.16×1062.15×10418

2n10nnlognn!

40127914

43139515

多項式算法有較好的封閉性——n個多項式算法可以結合起來解同一問題的某些特殊情形；一個多項式算法也可以利用另一個多項式算法作為“子程序”，并且最后的結果仍然是一個多項式算法。（4）P類、NP類、NP完全類、

①稱具有多項式時間算法的一類問題為P類問題，簡稱P問題。如：有向圖中的路、最大匹配問題、最小支撐樹問題等；②NP類問題也叫不確定性問題（或稱非多項式確定問題）。如果有一個用于求解此問題的算法，對于它可以找到一個多項式時間算法來驗證該算法所得的結果是否為此問題的解，則稱此問題屬于NP類問題，簡稱NP問題。③NP完備的（NP-Complete）——如果一個判定問題A是NP的，而且所有其他NP問題都能多項式地歸結到A，則稱A是NP完備的。

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

，并且A1是多次地以單位費用把A2的算法A2用作子程序的算法。則把A1叫做A1到A2的多項式時間歸結。

于是，若問題A是NP完備的，若A有有效算法，則每個NP問題也有有效算法。命題：如果A1多項式歸結到A2，而A2有多項式算法，則A1也有多項式算法。

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

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

COOK定理為了證明一個問題是NP-完備的，我們必須證明兩件事：(a)該問題是NP的(b)所有其他NP問題多項式轉(zhuǎn)換到該問題實際上，部分(b)通常用證明某個已知的NP-完備問題可以多項式變換到要證的問題完成的.不過第一個NP-完備性證明必須包含部分(b)的直接證明。為此我們需要在證明中應用所有各種NP問題的共性。共性便是對于每個‘是’實例x至少存在一個證明c(x)和一個證明檢驗算法Λ證明檢驗算法Λ