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

《代數(shù)方程和數(shù)值計(jì)算的復(fù)雜性理論簡(jiǎn)介.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《代數(shù)方程和數(shù)值計(jì)算的復(fù)雜性理論簡(jiǎn)介.ppt（54頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

Email guxf 2020年1月22日星期三 計(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)迭代算法 我們知道 形如ax2 bx c 0 a 0的一元二次方程 它的兩個(gè)根可以按照 這個(gè)求根公式算出來(lái) 54 4 ay3 by2 cy d 0 a 0可作代換x y b 3a化為無(wú)平方項(xiàng)的簡(jiǎn)化形式x3 px q 0 對(duì)簡(jiǎn)化形式作代換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型要選擇適當(dāng)?shù)膖 使判別式為0 即 即t3 bt2 ac 4d t a2d 4bd c2 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 a0 xn a1xn 1 a2xn 2 an 1x an 0 a0 0這里f x 是一個(gè)n次多項(xiàng)式 如果能夠把方程f x 0改寫成x x 的形式 并能夠找到一個(gè)x 使得x x 那么 x 就是原代數(shù)方程的一個(gè)解 54 8 不動(dòng)點(diǎn)迭代法 把方程f x 0改寫成x x 的形式 非常容易 也有許多方式 例如 可以寫成x a0 xn a1xn 1 a2xn 2 an 1 1 x an 也可以寫成 等等 因?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ù)方程改寫成不動(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次方程x5 17x 2 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)一步把上述迭代的情況研究清楚 可以畫一張迭代圖幫助我們分析 圖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)a b 使得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 817 10 3 0 f b 3 469 10 3 0 正好符合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 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得一個(gè)近似解 這時(shí)f c 1 2 10 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 是 的地盤 A C 是B的地盤 C 是 的地盤 而A的地盤只有它自己一個(gè)點(diǎn) A C的地盤也只有它自己一個(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 具體寫下來(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可以改寫為多種不 動(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 上滿足如下條件 1 當(dāng)x a b 時(shí) x a b 即a x b 2 對(duì)任意的x1 x2 a b 恒成立 x1 x2 L x1 x2 即 x 在 a b 上滿足Lipschitz條件 L稱為L(zhǎng)ipschitz常數(shù) 且L 1 則方程x x 在 a b 上的解 存在且唯一 并且對(duì)任意x0 a 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 2 a 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 因L 1 所以 54 28 推論1 1 若條件 2 改為 x 在 a b 上有界 且 x L 1 當(dāng)x a b 時(shí)則定理結(jié)論成立 上面證明迭代過(guò)程的收斂性 理論上要得到精確解 一般需要進(jìn)行無(wú)窮次迭代循環(huán) 這當(dāng)然是不現(xiàn)實(shí)的 實(shí)際應(yīng)用中也只需求得滿足精度要求得近似值 為此 我們要估計(jì)經(jīng)過(guò)n次迭代后的誤差 n xn 54 29 定理1 2 設(shè)函數(shù) x 在有限區(qū)間 a b 上滿足如下條件 1 當(dāng)x a b 時(shí) x a b 即a x b 2 x 在 a b 上滿足Lipschitz條件 且L 1 則成立誤差估計(jì)式 54 30 定理1 2的證明 對(duì)任意正整數(shù)m n 有 由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è)解 解在什么地方等等 也都屬于這類問(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)椴蝗坏脑?就和雞只有雌雄兩個(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)造性方法外 我們還要注意 人類的認(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)避短 向人們提供滿意的答案 我們下一章要介紹的庫(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 n T n 究竟是n的什么函數(shù)呢 即使沒(méi)有明確的函數(shù)關(guān)系 也要盡可能把它們的關(guān)系反映出來(lái) 因?yàn)楣ぷ髁康拇笮?工作效率的高低 總是可以用工作時(shí)間來(lái)表示 所以我們稱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稱一個(gè)函數(shù)g n 是O f n 小于等于f n 的階 當(dāng)且僅當(dāng)存在一個(gè)常數(shù)c 0和n0 0 對(duì)一切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(shù) n O n3 為了更精確地說(shuō)明一個(gè)算法的復(fù)雜性 有時(shí)引人記號(hào) f n 表示階恰好為f n 的函數(shù) 54 39 f n 的定義 定義1 2稱一個(gè)函數(shù)g n 是 f n 當(dāng)且僅當(dāng)存在常數(shù)c1 0和c2 0及一個(gè)n0 0 對(duì)一切n n0有 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)式 的算法 稱為多項(xiàng)式時(shí)間算法 不能這樣限制時(shí)間復(fù)雜性函數(shù)的算法稱為指數(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 2 S 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 2 S k 1 1 54 45 梵塔問(wèn)題 因此 我們可以得到如下的遞歸序列 故有 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 梵塔問(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 31557000 584 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)的核子燃料還能使用100 150億年 如果這種理論正確 那么很容易算出太陽(yáng)系的壽命不會(huì)超過(guò)200億年 這些數(shù)據(jù)不應(yīng)當(dāng)成為 世界末日 的證明 遠(yuǎn)在太陽(yáng)系的壽命結(jié)束之前 人類文明該早已找到新的寄托 新的載體 新的可以更加大顯身手的廣闊天地 值得我們驚嘆的是 古印度先賢們對(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á)到幾百幾千是常有的事 例如 投入產(chǎn)出的經(jīng)濟(jì)分析 就經(jīng)常要對(duì)付幾百各經(jīng)濟(jì)變量 這個(gè) 幾百 就是投入產(chǎn)出分析問(wèn)題的規(guī)模 大型線性規(guī)劃問(wèn)題要對(duì)付上千個(gè)方程和上千個(gè)約束條件 等式或不等式 這里的 幾千 就是線性規(guī)劃的規(guī)模 大家也許會(huì)想 雖然問(wèn)題的規(guī)模越來(lái)越大 但計(jì)算機(jī)的運(yùn)算速度也會(huì)越來(lái)越快 所以沒(méi)什么可擔(dān)心的 其實(shí)不然 我們還是以上述6種算法為例 試作分析 假定這6種算法用現(xiàn)有的計(jì)算機(jī)在1小時(shí)內(nèi)可以解決的問(wèn)題的最大規(guī)模是n 1000 這樣做 是為了把6種算法都放在同一條起跑線上 便于做公平的比較 表1 2告訴我們 如果發(fā)明了速度等于現(xiàn)有計(jì)算機(jī)100倍或1000倍的計(jì)算機(jī) 那么在1小時(shí)內(nèi)可以解決的問(wèn)題的規(guī)模如何變化 54 51 改進(jìn)技術(shù)對(duì)多項(xiàng)式和指數(shù)的時(shí)間算法的影響 表1 2改進(jìn)技術(shù)對(duì)幾種多項(xiàng)式的和指數(shù)的時(shí)間算法的影響 1小時(shí)內(nèi)可解的最大的問(wèn)題實(shí)例的規(guī)模 54 52 好的 算法 我們看到 對(duì)于2n算法 如果計(jì)算機(jī)速度提高1000倍 在一小時(shí)內(nèi)可解的最大的問(wèn)題的規(guī)模從1000增加到1010 只增加百分之一 而對(duì)于n5算法 這個(gè)規(guī)模從1000增加到3980 差不多增加了3倍 基于上述討論分析 我們就可以明白 為什么在計(jì)算機(jī)科學(xué)和計(jì)算數(shù)學(xué)中都把多項(xiàng)式時(shí)間算法看作是 好的 算法 科學(xué)研究的一個(gè)重要內(nèi)容 就是判別和論證現(xiàn)有的各種算法是不是多項(xiàng)式時(shí)間算法 或者尋找和設(shè)計(jì)新的多項(xiàng)式時(shí)間算法 既然多項(xiàng)式時(shí)間算法是好的算法 那么是否凡是指數(shù)時(shí)間算法都是不好的算法呢 54 53 小結(jié) 這個(gè)問(wèn)題不那么簡(jiǎn)單 回憶上一節(jié)講的不動(dòng)點(diǎn)迭代xn 1 xn5 2 17 這是解方程x5 17x 2 0的一種算法 大家已經(jīng)體會(huì)到這個(gè)算法相當(dāng)好 但是 這個(gè)算法是多項(xiàng)式時(shí)間算法嗎 不是 按多項(xiàng)式時(shí)間算法的定義 解規(guī)模為n的問(wèn)題所需要的時(shí)間不超過(guò)cnk 這里c是一個(gè)正常數(shù)而k是一個(gè)固定的非負(fù)整數(shù) 我們記得 上述迭代如果從n 3開(kāi)始 就根本不收斂 不解決問(wèn)題 這就是說(shuō) 不論迭代多少時(shí)間 問(wèn)題總不能解決 所以 按cnk確定時(shí)限的c和k不存在 這就說(shuō)明它不時(shí)多項(xiàng)式時(shí)間算法 54 54 小結(jié) 但是如果從比較好的地方開(kāi)始迭代 它又算得很好 令人十分滿意 所以 面對(duì)一個(gè)非多項(xiàng)式時(shí)間算法 我們并不立即判斷它是不好得算法而完全拋棄 而是要研究它什么時(shí)候不好 為什么不好 更要研究它什么時(shí)候會(huì)表現(xiàn)出好的行為 可以解決我們面對(duì)的問(wèn)題 本來(lái) 只有當(dāng)一種算法是收斂的時(shí)候 才可以說(shuō)它是多項(xiàng)式時(shí)間算法或指數(shù)時(shí)間算法 上述不動(dòng)點(diǎn)迭代從很多地方開(kāi)始都不收斂 我們尚且不能籠統(tǒng)說(shuō)它不好 那么如果是收斂的算法但收斂得比較慢 指數(shù)時(shí)間 更不能馬上說(shuō)它不好 這是一個(gè)更深一步的問(wèn)題