代數(shù)方程和數(shù)值計(jì)算的復(fù)雜性理論簡(jiǎn)介.pptVIP

Email： 2019年7月9日星期二,計(jì)算的 復(fù)雜性,計(jì)算機(jī)科學(xué)與工程學(xué)院,顧 小 豐,54 - 2,第一章 代數(shù)方程和數(shù)值計(jì)算的復(fù)雜性理論簡(jiǎn)介,代數(shù)方程的不動(dòng)點(diǎn)迭代算法 收斂性和復(fù)雜性算法優(yōu)劣判別的兩個(gè)層次,54 - 3,1.1 代數(shù)方程的不動(dòng)點(diǎn)迭代算法,我們知道，形如 ax2bxc=0，a0 的一元二次方程，它的兩個(gè)根可以按照,這個(gè)求根公式算出來(lái)。,54 - 4,ay3by2cyd=0，a0 可作代換x=yb/3a化為無(wú)平方項(xiàng)的簡(jiǎn)化形式x3pxq=0，對(duì)簡(jiǎn)化形式作代換x=z-p/3z，可將其化為z6qz3-p3/27=0此方程可看作z3的二次方程，不難解出z，再代回去，得到 x1=AB；x2=AB2；x3=A2B 其中,（是的立方根之一）。,一元三次方程的求根公式,54 - 5,x4ax3bx2cxd=0 可以配方成,其中t是待定系數(shù)。令,上式的左邊為f(x，t)2型。為了使上式右邊為g(x，t)2型要選擇適當(dāng)?shù)膖，使判別式為0，即,即 t3bt2(ac4d)ta2d4bdc2=0 先解關(guān)于t的三次方程，求出t，進(jìn)而配方得到g(x，t)2，再解兩個(gè)二次方程f(x，t)g(x，t)=0和f(x，t)g(x，t)=0即可得到結(jié)果。,一元四次方程的求根公式,54 - 6,上述這種把代數(shù)方程的根用方程系數(shù)經(jīng)有限次加、減、乘、除和開(kāi)方運(yùn)算表示出來(lái)的方法，叫做代數(shù)方程的代數(shù)解法（或公式解法）。 但是，數(shù)學(xué)家已經(jīng)證明，五次和更高次方程，就找不到普遍適用的代數(shù)解法，這就是說(shuō)，不會(huì)有用方程系數(shù)經(jīng)有限次加、減、乘、除和開(kāi)方運(yùn)算把方程的根表示出來(lái)的公式。這種“無(wú)公式解”的本性是和五次以下的方程不同的。由于這個(gè)原因，以后我們只把五次和高于五次的代數(shù)方程叫做高次方程。 高次方程雖然沒(méi)有普遍適用的代數(shù)解法，但是卻有一些非代數(shù)的或者說(shuō)非公式的解法。下面先介紹高次方程的不動(dòng)點(diǎn)迭代解法。,高 次 方 程,54 - 7,不動(dòng)點(diǎn)迭代法,代數(shù)方程都可以表示成 f(x)=a0xna1xn-1a2xn-2an-1xan=0，a00 這里f(x)是一個(gè)n次多項(xiàng)式。如果能夠把方程 f(x)=0 改寫(xiě)成 x=(x) 的形式，并能夠找到一個(gè)x*，使得 x*=(x*) 那么，x*就是原代數(shù)方程的一個(gè)解。,54 - 8,不動(dòng)點(diǎn)迭代法,把方程f(x)=0改寫(xiě)成x=(x)的形式，非常容易，也有許多方式。例如，可以寫(xiě)成 x=-a0xna1xn-1a2xn-2(an-11)xan， 也可以寫(xiě)成,等等。因?yàn)樾路匠淌菑膄(x)=0變來(lái)的，所以新方程的解就是原方程的解。 x*是新方程的解，就是說(shuō)x*=(x*)。請(qǐng)看函數(shù)(x)。一個(gè)函數(shù)，就表示一個(gè)對(duì)應(yīng)，或者說(shuō)表示一個(gè)變換。函數(shù)(x)是把x變成(x)的對(duì)應(yīng)。現(xiàn)在x*=(x*)，就是把x*變成(x*)=x*自己，換一個(gè)說(shuō)法，就是x*經(jīng)過(guò)這個(gè)變換沒(méi)有動(dòng)，由于這個(gè)原因，使得x*=(x*)的點(diǎn)x*叫做函數(shù)的不動(dòng)點(diǎn)，形如x=(x)的方程，也就叫做不動(dòng)點(diǎn)方程 。,54 - 9,不動(dòng)點(diǎn)迭代法,從上面可以看出，把代數(shù)方程改寫(xiě)成不動(dòng)點(diǎn)方程是容易的，難的是怎樣得到不動(dòng)點(diǎn)x*。為此，我們采用迭代方法：找一個(gè)點(diǎn)，記作x0，代入函數(shù)，得到(x0)，記作x1，再代入函數(shù)，得到(x1)，記作x2，如此一直做下去，可以得到一個(gè)序列 x0, x1, x2, , xn, 其迭代關(guān)系可以表示成 xn+1=(xn)，n=0,1,2, 有趣的是，這個(gè)迭代序列有時(shí)候可以幫助我們找到所要的不動(dòng)點(diǎn)，這就是不動(dòng)點(diǎn)迭代方法。,54 - 10,不動(dòng)點(diǎn)迭代法例1,考慮5次方程 x517x2=0 首先把它變成不動(dòng)點(diǎn)方程,這里的表示,選x0=0進(jìn)行迭代，得,就是(x)。,x*=0.1176483就是的一個(gè)不動(dòng)點(diǎn)，所以是原方程的一個(gè)解。 熟悉這方面內(nèi)容的讀者可能已經(jīng)看出，2是原方程的一個(gè)解。但是如果你不懂迭代法，或者雖然懂但不去做，就無(wú)論如何看不出0.1176483這個(gè)解。,54 - 11,不動(dòng)點(diǎn)迭代法例1,剛才，我們選x0=0開(kāi)始迭代，獲得成功，這是不是巧合？是不是接受了什么暗示？提出懷疑是完全合理的，應(yīng)當(dāng)多做幾次試驗(yàn)。下面分別從x0=1，x0=-1，x0=2，x0=-2，開(kāi)始迭代，4個(gè)迭代序列如下：,54 - 12,不動(dòng)點(diǎn)迭代法例1,到目前為止，5個(gè)迭代都是成功的，一共找到2個(gè)解。下面，再擴(kuò)大范圍試試，從x0=3和x0=-3開(kāi)始迭代，數(shù)據(jù)如下：,不必再算下去就可以判斷，這兩個(gè)序列都是沒(méi)有極限的。迭代公式是 ，當(dāng)xn已經(jīng)很大時(shí)，xn5就會(huì)非常大，最后除以17，仍然保持很大。所以，從x0=3開(kāi)始的迭代跑向+，從x0=-3開(kāi)始的迭代跑向-，它們都不收斂。我們說(shuō)這樣的迭代序列發(fā)散。,54 - 13,例1的圖示,不動(dòng)點(diǎn)迭代方法非常簡(jiǎn)單，但不一定能夠保證成功。迭代是否成功，怎樣使迭代成功，我們等以會(huì)兒再討論。為了進(jìn)一步把上述迭代的情況研究清楚，可以畫(huà)一張迭代圖幫助我們分析。,圖 1-1,圖1.1-1標(biāo)明了前面所做的7個(gè)迭代過(guò)程的結(jié)果，1個(gè)迭代駐守在2這個(gè)點(diǎn)不動(dòng)，4個(gè)迭代收斂到0.1176483，另外兩個(gè)迭代分別向+和-發(fā)散。,54 - 14,例1的圖啟示,從-3開(kāi)始的迭代發(fā)散，從-2開(kāi)始的迭代收斂。-3和-2之間，應(yīng)當(dāng)有一個(gè)分界點(diǎn)，分界點(diǎn)在哪里？從分界點(diǎn)開(kāi)始的迭代，究竟怎樣進(jìn)行？ 從1開(kāi)始的迭代收斂到0.1176483這個(gè)不動(dòng)點(diǎn)，從2開(kāi)始的迭代駐守在2這個(gè)不動(dòng)點(diǎn)，它們之間也應(yīng)當(dāng)有一個(gè)分界點(diǎn)，也有同樣的問(wèn)題。 2和3之間也有同樣的問(wèn)題。,這個(gè)圖啟發(fā)我們提出進(jìn)一步的問(wèn)題：,54 - 15,為此，我們做3個(gè)迭代，數(shù)據(jù)如下：,看來(lái)，點(diǎn)2向右過(guò)去一點(diǎn)，迭代就發(fā)散到+，點(diǎn)2向左過(guò)去一點(diǎn)，迭代就收斂到0.1176483；而從-2.1開(kāi)始的迭代發(fā)散到-。,54 - 16,更細(xì)致的試驗(yàn)，得出以下數(shù)據(jù)：,54 - 17,兩個(gè)結(jié)論,點(diǎn)2是個(gè)孤立的、很不穩(wěn)定的不動(dòng)點(diǎn)，迭代出發(fā)點(diǎn)x0與點(diǎn)2差一點(diǎn)點(diǎn)，迭代的結(jié)果就完全不同 問(wèn)題(1)的分界點(diǎn)在-2.0590與-2.0589之間,下面我們用另一種不但一學(xué)就會(huì)而且必定成功的迭代法把這個(gè)分界點(diǎn)確定下來(lái)，這就是分區(qū)間迭代法（二分法），現(xiàn)將這種方法介紹如下：,54 - 18,二分法,我們要解的是方程f(x)=0，如果我們已經(jīng)知道兩點(diǎn)ab，使得f(a)f(b)0，即f(a)和f(b)符號(hào)相反，那么在(a,b)中取中點(diǎn)c，計(jì)算f(c)。如果f(c)=0，則解已求得，不必再迭代下去。否則，如果f(a)f(c)0，知f(c)與f(b)同號(hào)，就扔掉原來(lái)的b，把c作為新b，仍如上法迭代；如果f(b)f(c)0，知f(c)與f(a)同號(hào)，就扔掉原來(lái)的a，把c作為新a，仍如上法迭代。這就是同符號(hào)頂替的原則。這樣，每迭代一次，區(qū)間(a,b)的長(zhǎng)度就縮小一半，而在區(qū)間的兩端，函數(shù)f(x)的符號(hào)總是相反的。于是，根據(jù)f(x)的連續(xù)性，這些每次縮短一半的區(qū)間最后套住一個(gè)點(diǎn)，這個(gè)點(diǎn)一定是f(x)=0的解。,54 - 19,二分法求解,現(xiàn)在就來(lái)試一試。前已知道，-2.0590與-2.0589之間應(yīng)當(dāng)有一個(gè)分界點(diǎn)，我們就拿a=-2.0590和b=-2.0589開(kāi)始。f(a)= -3.81710-30，f(b)=3.46910-30，正好符合f(a)f(b)0，取(a,b)中取中點(diǎn)c=-2.05895，計(jì)算f(c)，這時(shí)不必記錄具體結(jié)果，只要知道正負(fù)就可以了，算得f(c)0，與f(a)同號(hào)，所以按照同號(hào)頂替得原則，取c作為新a，下次迭代就取(a,b)=(-2.05895,-2.05890)。如果拘泥于中點(diǎn)，下次就該取c=-2.058925。但對(duì)分區(qū)間有一個(gè)好處，c取偏一點(diǎn)關(guān)系不大，只要不跑出(a,b)就行了。為了不一下子增加數(shù)字的長(zhǎng)度，我們?nèi)=-2.05893，算得f(c)0，再取c=-2.05894，也得f(c)0，接下去,54 - 20,二分法求解,c=-2.058945，f(c)0 c=-2.058947，f(c)0 c=-2.058948，f(c)0 c=-2.0589475，f(c)0 c=-2.0589477，f(c)0 c=-2.0589476，f(c)0,這已經(jīng)很精確了，我們就取c=-2.0589476作為f(x)=0得一個(gè)近似解，這時(shí)f(c)=1.210-6。,54 - 21,f(x)=0的三個(gè)解,至此，我們找到了f(x)=0的三個(gè)解，也就是迭代的三個(gè)不動(dòng)點(diǎn)，即2、0.1176483和-2.0589476。經(jīng)過(guò)這樣一番研究，我們對(duì)迭代的收斂情況有更加準(zhǔn)確的了解，這些情況，總結(jié)如下圖：,圖 1-2,54 - 22,f(x)=0的三個(gè)解,方程f(x)=x5-17x+2=0共有三個(gè)不同的實(shí)數(shù)解，它們是A=-2.058976，B=0.1176483和C=2。從不動(dòng)點(diǎn)迭代的角度來(lái)看，A和C都是孤立的、不穩(wěn)定的不動(dòng)點(diǎn)，在A和C附近開(kāi)始迭代，出發(fā)點(diǎn)差一點(diǎn)點(diǎn)，迭代結(jié)果就會(huì)面目全非。如果以迭代的結(jié)局來(lái)瓜分實(shí)數(shù)軸，那么 (-,A)是-的地盤(pán)，(A,C)是B的地盤(pán)，(C,+)是+的地盤(pán)，而A的地盤(pán)只有它自己一個(gè)點(diǎn)A，C的地盤(pán)也只有它自己一個(gè)點(diǎn)C。,54 - 23,第二個(gè)例子,考慮代數(shù)方程f(x)=x2-3=0。這個(gè)方程太簡(jiǎn)單了，但著眼于方法 的討論，我們?yōu)槭裁捶且獜?fù)雜的方程不可呢？找復(fù)雜的方程來(lái)演 示，會(huì)本末倒置，花費(fèi)許多精力到技術(shù)細(xì)節(jié)上會(huì)妨礙我們對(duì)問(wèn)題實(shí) 質(zhì)的認(rèn)識(shí)，所以，這里寧愿用簡(jiǎn)單的方程。 我們采用4種方案，把f(x)=0變成不動(dòng)點(diǎn)方程： (1) x=x+(x2-3) (2) x=3/x (3) x=(x+3/x)/2 (4) x=x+(x2-3)/4 將不動(dòng)點(diǎn)方程右端的表達(dá)式看作(x)，就可以將迭代公式 xn+1=(xn)具體寫(xiě)下來(lái)： (1) xn+1=xn+(xn2-3) (2) xn+1=3/xn (3) xn+1=(xn+3/xn)/2 (4) xn+1=xn+(x2n-3)/4 這4個(gè)迭代都從x0=2開(kāi)始，迭代情況如下：,54 - 24,第二個(gè)例子,迭代(1)發(fā)散到+，不收斂；迭代(2)振蕩，也不收斂；迭代(3)和(4)都收斂到方程的解。雖然(3)和(4)都收斂，但是很明顯，迭代(3)收斂得比迭代(4)快。,54 - 25,結(jié)論,大家是否注意到，迭代(1)和(4)都可以表示成統(tǒng)一得形 式，那就是： x=x+c(x2-3) 當(dāng)取c=1時(shí)就得(1)，迭代不收斂；當(dāng)取c=-1/4時(shí)就得 (4)，迭代收斂了。這個(gè)c得選擇很有講究。選得好，就收 斂，甚至收斂很快；選得不好，就算得很慢，甚至根本不收 斂。,從上面得例子可以看出，方程f(x)=0可以改寫(xiě)為多種不,動(dòng)點(diǎn)方程，同一個(gè)不動(dòng)點(diǎn)方程也可以選取多個(gè)初值，那么應(yīng) 當(dāng)怎樣構(gòu)造不動(dòng)點(diǎn)方程、怎樣選擇初值呢？下面我們來(lái)建立 求方程x=(x)的根的迭代過(guò)程的收斂性定理和誤差估計(jì)。,54 - 26,定理1-1,設(shè)函數(shù)(x)在有限區(qū)間a,b上滿(mǎn)足如下條件： (1) 當(dāng)xa,b時(shí)，(x)a,b，即a(x)b； (2) 對(duì)任意的x1,x2a,b，恒成立： |(x1)-(x2)|L|x1-x2| （即(x)在a,b上滿(mǎn)足Lipschitz條件，L稱(chēng)為L(zhǎng)ipschitz常數(shù)）且L1，則方程x=(x)在a,b上的解存在且唯一，并且對(duì)任意x0a,b，由迭代過(guò)程xn+1=(xn)產(chǎn)生的序列xk收斂到。,54 - 27,定理1-1的證明,首先證明x=(x)的解存在且唯一。作函數(shù) g(x)=x-(x) 顯然g(x)在a,b上連續(xù)。由條件(1)可知 g(a)=a-(a)0，g(b)=b-(b)0 由連續(xù)函數(shù)根的存在定理可知：必有a,b使g()=0，即=()。因此，是方程x=(x)的解。 其次證明唯一性，假設(shè)存在兩個(gè)解1,2，則 1=(1)，2=(2)，1,2a,b,因此，由條件(2)有 |1-2|=|(1)-(2)|L|1-2|， 因?yàn)長(zhǎng)1，所以必有1=2=。 再證xk的收斂性。按迭代過(guò)程xn+1=(xn)，有 xk-=(xk)-() 由條件(2)得 |xk-|=|(xk-1)-()|L|xk-1-|Lk|x0-|， 因L1，所以,。,54 - 28,推論1-1,若條件(2)改為(x)在a,b上有界，且 |(x)|L1，當(dāng)xa,b時(shí) 則定理結(jié)論成立。,上面證明迭代過(guò)程的收斂性，理論上要得到精確解， 一般需要進(jìn)行無(wú)窮次迭代循環(huán)，這當(dāng)然是不現(xiàn)實(shí)的，實(shí)際 應(yīng)用中也只需求得滿(mǎn)足精度要求得近似值，為此，我們要 估計(jì)經(jīng)過(guò)n次迭代后的誤差n=xn-。,54 - 29,定理1-2,設(shè)函數(shù)(x)在有限區(qū)間a,b上滿(mǎn)足如下條件： (1) 當(dāng)xa,b時(shí)，(x)a,b，即a(x)b； (2) (x)在a,b上滿(mǎn)足Lipschitz條件，且L1； 則成立誤差估計(jì)式,54 - 30,定理1-2的證明,對(duì)任意正整數(shù)mn，有,由Lipschitz條件得 |xk+1-xk|=|(xk)-(xk-1)|L|xk-xk-1|Lk|x1-x0| 所以,在上式中，令m，由定理1-1，,，所以,。,54 - 31,定理1-2的說(shuō)明,在實(shí)際計(jì)算中，上式也可用來(lái)估計(jì)達(dá)到要求精度所需要的迭代循環(huán)次數(shù)，由要求,得,這里，,表示不大于x的最大整數(shù)。,54 - 32,1.2 收斂性和復(fù)雜性 算法優(yōu)劣判別的兩個(gè)層次,數(shù)學(xué)討論最終還是要解決實(shí)際問(wèn)題。如果面對(duì)的是方程求解問(wèn)題，那么首先就要回答方程有沒(méi)有解這個(gè)所謂解的存在性問(wèn)題。方程有多少個(gè)解、解在什么地方等等，也都屬于這類(lèi)問(wèn)題。 存在性討論有兩種基本方式：一種是構(gòu)造性的證明方法，那就是具體設(shè)計(jì)一種方法把解找出來(lái)，從而說(shuō)明解是存在的。找到了的東西當(dāng)然是存在的東西，這就是構(gòu)造性方式的哲學(xué)；另一種是非構(gòu)造性的證明方法，其代表就是反證法：假定沒(méi)有解，然后通過(guò)推理，引出與已知事實(shí)的矛盾。,54 - 33,反證法,反證法在邏輯上常常是漂亮的，但是帶給人們的信息較少。例如，面對(duì)3只雛雞，你看也不看就可以作出“其中必有兩只雛雞的性別相同”這樣一個(gè)存在性的判斷，因?yàn)椴蝗坏脑?huà)，就和雞只有雌雄兩個(gè)性別的已知事實(shí)矛盾。這個(gè)判斷過(guò)程，就是非構(gòu)造性的。徜若你是一個(gè)識(shí)雞的行家，確實(shí)辨認(rèn)出其中有兩只雌雞或雄雞，并由此得到“有兩只雛雞的性別相同”的判斷，這個(gè)判斷的論證過(guò)程就是構(gòu)造性的。兩相比較：構(gòu)造性的判斷方式具體指出了兩只雌雞或雄雞，所以提供的信息較多，而前面所說(shuō)的非構(gòu)造性的判斷，在我們這個(gè)雛雞識(shí)別的問(wèn)題里，沒(méi)有提供一點(diǎn)有實(shí)用價(jià)值的信息。,54 - 34,反證法,但是在數(shù)學(xué)發(fā)展的漫長(zhǎng)進(jìn)程之中，非構(gòu)造性的討論方法作用很 大，功不可沒(méi)。我們知道，社會(huì)要求和內(nèi)部動(dòng)力是數(shù)學(xué)發(fā)展的兩大 激勵(lì)因素。非構(gòu)造性的討論方式，常常就是數(shù)學(xué)大系統(tǒng)的內(nèi)部動(dòng)力 的體現(xiàn)。另外，除了沒(méi)有構(gòu)造性方法時(shí)自然歡迎非構(gòu)造性方法外， 我們還要注意，人類(lèi)的認(rèn)識(shí)都是相互聯(lián)系的，非構(gòu)造性方法得到的 結(jié)論，常?？梢越o研究構(gòu)造性方法指引方向。最典型的例子，就是 數(shù)學(xué)家已經(jīng)用非構(gòu)造性的方法證明了，不存在用圓規(guī)和直尺三等分 任意角的通用方法，不存在高次方程的代數(shù)解法，這就使后人可以 避免在尋求三等分角和高次方程代數(shù)解方面空耗精力（論證某種東 西不存在，和論證某種東西存在一樣，都屬于存在性問(wèn)題）。相 反，如果對(duì)于一個(gè)問(wèn)題，數(shù)學(xué)家已經(jīng)用非構(gòu)造性方法證明了解是一 定存在的，這就指引后人更明確地去尋求把解具體找出來(lái)的構(gòu)造性 方法。最典型的例子，就是代數(shù)基本定理。,54 - 35,代數(shù)基本定理,多項(xiàng)式有沒(méi)有根，有多少個(gè)根，在二百年前就已經(jīng)清楚了。論述這一事實(shí)的定理，就是著名的代數(shù)基本定理： 任一n次（復(fù)系數(shù)）多項(xiàng)式恰好有n個(gè)（復(fù)）根。 大家知道，法國(guó)數(shù)學(xué)家高斯從1799年到1850年前后跨越半個(gè)世紀(jì)的時(shí)間里，曾經(jīng)提出代數(shù)基本定理的四種證明。更早，牛頓、麥克勞林、達(dá)朗貝爾、歐拉和拉格朗日，都從事過(guò)這一工作，他們提供的證明，基本上都是非構(gòu)造性的證明，主要思路就是如果沒(méi)有根，會(huì)引出什么樣的矛盾。,54 - 36,代數(shù)基本定理,隨著科學(xué)的發(fā)展，各方面對(duì)數(shù)學(xué)的要求，越來(lái)越傾向于構(gòu)造性的解決辦法。構(gòu)造性的方法雖然作起來(lái)有時(shí)比較辛苦，但它不僅肯定了“存在”的事實(shí)，而且還告訴人們?cè)鯓影堰@個(gè)存在找出來(lái)。構(gòu)造性方法雖然計(jì)算比較繁復(fù)，但隨著計(jì)算機(jī)的發(fā)展和普及，“繁復(fù)”的弱點(diǎn)大半已經(jīng)不成問(wèn)題，構(gòu)造性方法正好可以借助計(jì)算機(jī)揚(yáng)長(zhǎng)避短，向人們提供滿(mǎn)意的答案。我們下一章要介紹的庫(kù)恩（Kuhn）算法，就是代數(shù)基本定理的構(gòu)造性證明方法。 既然我們強(qiáng)調(diào)構(gòu)造性工作的實(shí)際應(yīng)用價(jià)值，那么，面對(duì)一種算法，第一要問(wèn)它是否成功，第二要問(wèn)它的效率如何。不成功的算法不能把解求出來(lái)，當(dāng)然沒(méi)用。成功但效率很低的算法，也沒(méi)有多少價(jià)值。如果有人告訴你一種算法，并且在數(shù)學(xué)上證明了按這種算法一定可以找到問(wèn)題的解，但是求解要在最新的計(jì)算機(jī)上花費(fèi)多少萬(wàn)年的時(shí)間，你對(duì)這樣一種實(shí)際上無(wú)法實(shí)現(xiàn)的構(gòu)造性方法會(huì)有什么感想？恐怕是啼笑皆非吧？,54 - 37,收斂性與復(fù)雜性,算法是否成功，是收斂性問(wèn)題，收斂的就成功，不收斂即發(fā)散的就 不成功。效率如何，是算法的復(fù)雜性問(wèn)題。復(fù)雜性是我們介紹的主題。 效率的高低，指的是收斂的快慢，這是毫無(wú)疑問(wèn)的。同一種算法， 解小規(guī)模的問(wèn)題花時(shí)間少，解大規(guī)模的問(wèn)題花時(shí)間多，這是很自然的事 情。問(wèn)題是，隨著問(wèn)題規(guī)模的增加，所需要的計(jì)算時(shí)間怎樣增加？以代 數(shù)方程求解來(lái)說(shuō)，如果方程的次數(shù)為n，求解所需要的時(shí)間，我們把它 暫記為T(mén)(n)。T(n)究竟是n的什么函數(shù)呢？即使沒(méi)有明確的函數(shù)關(guān)系， 也要盡可能把它們的關(guān)系反映出來(lái)。 因?yàn)楣ぷ髁康拇笮?，工作效率的高低，總是可以用工作時(shí)間來(lái)表 示，所以我們稱(chēng)T(n)為解法或算法的時(shí)間復(fù)雜性函數(shù)。 不同的算法具有很不相同的時(shí)間復(fù)雜性函數(shù)，說(shuō)它們當(dāng)中哪些“效 率足夠高”，哪些“效率太低”，總要看當(dāng)時(shí)的情況。但是，計(jì)算機(jī)科學(xué) 和計(jì)算數(shù)學(xué)科學(xué)家們公認(rèn)一種簡(jiǎn)單的區(qū)別，這種區(qū)別對(duì)這些問(wèn)題提供了 重要的透徹的分析，這就是多項(xiàng)式時(shí)間算法和指數(shù)時(shí)間算法的區(qū)別。,54 - 38,O(f(n)的定義,定義1-1 稱(chēng)一個(gè)函數(shù)g(n)是O(f(n)（小于等于f(n)的 階），當(dāng)且僅當(dāng)存在一個(gè)常數(shù)c0和n00，對(duì)一切nn0有 |g(n)|c|f(n)|成立。也稱(chēng)函數(shù)g(n)以f(n)為界或者稱(chēng) g(n)囿于f(n)。記作g(n)O(f(n)。,按此定義，如果g(n)O(n2)，則一定有g(shù)(n)O(n3)，為了更精確地說(shuō)明一個(gè)算法的復(fù)雜性，有時(shí)引人記號(hào)(f(n)，表示階恰好為f(n)的函數(shù)。,54 - 39,(f(n)的定義,定義1-2 稱(chēng)一個(gè)函數(shù)g(n)是(f(n)，當(dāng)且僅當(dāng)存在 常數(shù)c10和c20及一個(gè)n00，對(duì)一切nn0有 |g(n)|c1|f(n)|和|f(n)|c2|g(n)| 成立。記作g(n)(f(n)。 這樣，當(dāng)f(n)5n時(shí)，可以記作f(n)O(n2)，但不能 記作f(n)(n2)，只能記作f(n)(n)。但在一般情 況，人們?cè)谶M(jìn)行算法分析時(shí)，盡量在(f(n)的意義下使 用O(f(n)，例如當(dāng)f(n)=5n+2時(shí)，一般記作f(n)=0(n)，而 不記作f(n)=0(n2)。,54 - 40,多項(xiàng)式時(shí)間算法與指數(shù)時(shí)間算法,定義1-3 時(shí)間復(fù)雜性函數(shù)T(n)=O(p(n)（p(n)是多項(xiàng)式）的算法，稱(chēng)為多項(xiàng)式時(shí)間算法。不能這樣限制時(shí)間復(fù)雜性函數(shù)的算法稱(chēng)為指數(shù)時(shí)間算法。 應(yīng)該注意到，上述定義1-3中包含某些通常不看作指數(shù)函數(shù)的非多項(xiàng)式時(shí)間復(fù)雜性函數(shù)的算法作為指數(shù)時(shí)間算法，例如T(n)=nlogn。 指數(shù)關(guān)系為什么這么重要？下面我們講一個(gè)傳說(shuō)，它明確地把一種算法與計(jì)算時(shí)間的指數(shù)增長(zhǎng)展現(xiàn)在我們面前。,54 - 41,梵塔問(wèn)題,古代印度人把佛教圣地貝拿勒斯看作是世界的中心。傳說(shuō)在貝拿勒斯的圣廟里，有塊黃銅板，上面豎著3根寶石柱，這些寶石柱，徑不及小指，長(zhǎng)僅半臂。大梵天王（印度教的一位主神）在創(chuàng)造世界的時(shí)候，在其中一根柱上放置了64片中心有插空的金片。這些金片的大小都不一樣，大的在下面，小的在上面，從下而上疊成塔形，著就是所謂的梵天寶塔。 大梵天王為寶塔立下了至尊不渝的法則，這些金片可以從一根柱移到另一根柱，沒(méi)次只能移動(dòng)一片，并且要求不管如何時(shí)刻，也不管在哪一根柱上，小金片永遠(yuǎn)在大金片上面，絕不允許顛倒。 大梵天王預(yù)言，當(dāng)疊塔形的64片金片都從他創(chuàng)造世界是所放置的那根柱上移到另一根柱上，并且也是大的在下小的在上疊成塔形的時(shí)候，世界的末日就要來(lái)臨，一聲霹靂將梵塔、廟宇和眾生都消滅干凈。,54 - 42,梵塔問(wèn)題,大家可能會(huì)想：這個(gè)傳說(shuō)未免太不高明了，不就是64片金片嗎？頂多幾個(gè)鐘頭就可以實(shí)現(xiàn)寶塔挪位，到那時(shí)候，預(yù)言者豈不是要自己掌嘴？ 我和大家一樣，不相信什么世界末日。不過(guò)，按照大梵天王的規(guī)則把寶塔從一根柱上搬到另一根柱上，可不是容易的事。誠(chéng)然，傳說(shuō)畢竟是傳說(shuō)，但我們不妨把梵天寶塔作為一種數(shù)學(xué)游戲，自己動(dòng)手試一試。 按照大梵天王的規(guī)則，把一個(gè)n層寶塔從A柱移到B柱，至少要移動(dòng)多少次呢？我們把這個(gè)移動(dòng)次數(shù)記作S(n)。n=64是比較多的，我們先從n=1,2,3做起。,54 - 43,梵塔問(wèn)題,圖 1.2-1,54 - 44,梵塔問(wèn)題,n=1時(shí)，把金片直接從A柱移動(dòng)到B柱就行了，所以S(1)=1。 n=2時(shí)，可以借助C柱，先把小片移到C柱暫住，再把大片直送B柱，最后把小片移到B柱上壓在大片上面。三步完成，所以S(2)=3=2S(1)+1。 n=3時(shí)，我們這樣來(lái)分解任務(wù)：先把上面2片移到C柱，再把最底片移到B柱，最后把C柱上的2片移到B柱。這樣，3層塔的挪位完成。利用前面討論的結(jié)果，有：S(3)=S(2)+1+S(2) =3+1+3=7。 如此這樣繼續(xù)下去。 n=k時(shí)，我們分三步完成：先把上面k-1片移到C柱，再把最底片移到B柱，最后把C柱上的k-1片移到B柱。所以 S(k)=S(k-1)+1+S(k-1)=2S(k-1)+1。,54 - 45,梵塔問(wèn)題,因此，我們可以得到如下的遞歸序列,故有,S(n)2S(n-1)+12(2S(n-2)+1)+122S(n-2)+2+1 22(2S(n-3)+1)+21+20=23S(n-3)+ 22+21+20 23(2S(n-4)+1)+22+21+20=24S(n-4)+23+22+21+20 2n-1S(1) +2n-2+2n-3+23+22+21+20 2n-1+2n-2+2n-3+22+21+20 ,54 - 46,梵塔問(wèn)題,至此我們知道，把一個(gè)n層梵塔按照大梵天王的規(guī)則從一根柱上搬到另一根柱上，至少要移動(dòng)金片S(n)=2n-1次。 假如你手腳非常麻利，一秒鐘可以移動(dòng)一次金片，那么： n=1時(shí)，1秒鐘就可以完成任務(wù)； n=2時(shí)，3秒鐘就可以完成任務(wù)； n=3時(shí)，7秒鐘就可以完成任務(wù)； n=4時(shí)，需要15秒鐘； n=5時(shí)，31秒鐘； n=6時(shí)，(26-1)/60=1.05分鐘； n=7時(shí)，(27-1)/60=2.12分鐘； n=8時(shí)，(28-1)/60=4.25分鐘； ,54 - 47,梵塔問(wèn)題,看起來(lái)沒(méi)什么了不起，可是當(dāng)n=64變成真正的梵天寶塔時(shí)，就需要 S(64)=264-1=18,446,744,073,709,551,615 秒鐘才能完成移塔的任務(wù)。我們知道，平均一年約365.24天，每天24小時(shí)，每小時(shí)3600秒，所以一年大約31,557,000秒。由此可以看出，需要大約 (264-1)/31557000584,600,000,000 年的時(shí)間才能完成移動(dòng)任務(wù)。 我們所面臨的寶塔移位問(wèn)題，問(wèn)題的規(guī)模就是寶塔的層數(shù)n。問(wèn)題的規(guī)模只從n=1增加到n=64，為了解決這個(gè)問(wèn)題所需要的時(shí)間卻從1秒鐘增加到約5846億年。這就是指數(shù)增長(zhǎng)的厲害。,54 - 48,梵塔問(wèn)題,按照近代天體物理學(xué)的一種理論，太陽(yáng)系是在大約30億年前由處于混沌狀態(tài)的物質(zhì)逐漸演變而成的，太陽(yáng)的核子燃料還能使用100150億年。如果這種理論正確，那么很容易算出太陽(yáng)系的壽命不會(huì)超過(guò)200億年。這些數(shù)據(jù)不應(yīng)當(dāng)成為“世界末日”的證明，遠(yuǎn)在太陽(yáng)系的壽命結(jié)束之前，人類(lèi)文明該早已找到新的寄托、新的載體、新的可以更加大顯身手的廣闊天地。值得我們驚嘆的是，古印度先賢們對(duì)指數(shù)增長(zhǎng)竟有如此深刻的了解。64是一個(gè)小小的很平凡的數(shù)字，可是通過(guò)指數(shù)關(guān)系，64層梵天寶塔所賦予的期限，卻原來(lái)如此之長(zhǎng)。這個(gè)期限比太陽(yáng)系的壽命還長(zhǎng)得多，誰(shuí)還能企求更多呢？,54 - 49,幾種算法的速度比較,表1-1 幾個(gè)多項(xiàng)式的和指數(shù)的時(shí)間復(fù)雜性函數(shù)的對(duì)比 (假定都用1微秒（10-6秒）能夠完成一次運(yùn)算的高速計(jì)算機(jī)),54 - 50,算法速度增長(zhǎng)分析,從表中可以看出，對(duì)于多項(xiàng)式時(shí)間復(fù)雜性函數(shù)，工作量隨問(wèn)題規(guī)模n增長(zhǎng)而增長(zhǎng)的速度都比較溫和，但對(duì)于指數(shù)時(shí)間復(fù)雜性函數(shù)，這種增長(zhǎng)到后來(lái)就非常激烈。 列表的n=60，還不如前面的梵塔問(wèn)題n=64。隨著社會(huì)經(jīng)濟(jì)的發(fā)展和科學(xué)技術(shù)的進(jìn)步，應(yīng)用問(wèn)題的規(guī)模數(shù)達(dá)到幾百幾千是