代數(shù)方程和數(shù)值計算的復(fù)雜性理論簡介.ppt

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