《代數(shù)方程和數(shù)值計算的復雜性理論簡介.ppt》由會員分享，可在線閱讀，更多相關《代數(shù)方程和數(shù)值計算的復雜性理論簡介.ppt（54頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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