淺談算法分析的策略和技術

做算法分析的目的通常是為了確定算法的時間效率。這是通過對算法的基礎步驟執行次數進行計數來完成的。對于幾乎一切算法問題來說，計數的結果都是隨著問題的規模增長的。而考察到底增長得有多快，才是算法分析的主要目的。而談到計數，毫不奇怪地，就涉及數學了。所以，我們就從一些重要的數學公式入手，它們在算法分析中發揮的作用真是不可小覷。

1 幾個求和公式，兼論算法效率

關于史上最偉大的數學家之一Carl Friedrich Gauss（1777—1855），有一個眾所周知但真實性可疑的故事，那就是當他10歲左右的時候，他的老師要求全班同學計算前100個正整數之和，即的值，他可能覺得這會花費這些學生相當一段時間。當然，老師沒有想到這些學生中隱藏著一位數學高手。理所當然地，Carl只花了幾分鐘就得到了答案，方法是把全部數字分成50對，其中每一對都有著相同的和101：

把這種思路推廣到前個正整數，就得到了下面的公式：

（1）作為練習，建議讀者嘗試求解謎題心算求和，其中就利用了本公式及其變形。

公式(1)在算法中有著無可取代的地位。還可以從它推導出若干其他的有用公式。比如，欲求前個正偶數的和，我們就可以得出：

而前個正奇數的和，則這樣推導：

另一個非常重要的公式是2的各次方冪之和，我們在概論的前半部分已經用過：

（2）現在我們來看第一道采用算法分析求解的謎題。

據說，國際象棋游戲是很多個世紀以前由印度西北部的一位叫Shashi的賢人發明的。當Shashi將他的發明呈獻給國王以后，國王愛不釋手，并承諾給予這位發明人任何他想要的賞賜。Shashi說自己想要一些麥子，不過他是這么說的：在國際象棋棋盤的第1個格子里放1粒麥子，第2個格子里放2粒，第3個格子里放4粒，第4個格子里放8粒，依此類推，直至64個格子被放滿為止。請問，這樣的賞賜要求合理嗎？

根據公式，Shashi要求的麥子總粒數等于：

如果每一秒可以數一粒麥子的話，這個總數的數量需要花費5850億年才能數完。這比已知地球年齡的100倍還要長。這個例子很好地說明了指數增長（exponential growth）有多么恐怖。顯然，如果一個算法要求指數增長，那么除了極小的謎面以外，對于大多數情況它都沒有實用性了。

如果Shashi要求的不是每格比前一格麥子粒數加倍，而是每格比前一格麥子粒數多兩粒呢？這樣，麥子的總粒數就等于：

假如還是每一秒可以數一粒麥子的話，只需要1小時14分鐘，他要求的合理賞賜就能夠數完了。二次（quadratic）增長，顯然作為算法運行時間的增長速率來說，是較能夠接受的。

線性（linear）算法運行得相對較快，這種算法和輸入規模成比例地增長。還有更快的對數（logari thmic）算法。這種類型的算法通常基于每次降低一個常數因子的減而治之策略（參見概覽的算法設計策略部分），比如，反復地將問題規模減半。這樣，指數增長就被反其道而用之，問題的規模會急劇下降。前半部分的猜數字謎題就屬于對數算法類型。

2 非遞歸算法分析

讀者可能不會為以下的事實感覺意外：非遞歸算法（nonrecursive algorithm）就是指沒有形成遞歸的算法。換言之，求解這種算法，不能通過將其自身應用于同一問題越來越小的謎面，最終達到一步解出的目的。非遞歸算法的典型分析方法，就是對它的主要步驟數目求和。然后，將該和簡化為一個精確的計數公式，或一個表達其增長速率的估算公式。我們來看看下面這個例子[Gar99, p. 88 J，一個像謎題的問題。

算法起始時，只有一個單位方塊。每步迭代都在上一步的外圍填滿方塊。試問，在第步迭代時，總共有多少個單位方塊？最初幾步迭代如圖1所示。

圖1方塊搭建算法的最初幾步迭代示意

算法的基本步驟，就是添加一個單位方塊。因此，對算法的基本步驟的數目進行計數，實際上就等價于對單位方塊的總數進行計數。經過步迭代以后，最長的水平行將有個這樣的方塊，位于其上下的其他行將各包括從1到的所有奇數，由于前個奇數之和等于，單位方塊的總數就等于：

另一種解法是，注意到在第步（）迭代時，增加的單位方塊個數等于。這樣，經過步迭代，單位方塊總數可以這樣計算：

雖然采用中規中矩的標準技術當然不會有錯，但是利用題設的特殊性卻總是有用的。就拿這道題來說，就可以對n步迭代以后產生圖形的對角線所包含的方塊數目進行計數。這樣就可以發現，圖形是由n條每條都包含了n個單位方塊的對角線和交替出現的(n-1)條每條都包含了(n-1)個單位方塊的對角線共同構成的，所以，總計有圖像說明文字個單位方塊。

3 遞歸算法分析

我們將通過解答經典的漢諾塔謎題，來展示遞歸算法分析的標準技術。

本謎題的一般謎面是有個大小不同的圓盤，以及三根樁。一開始所有的圓盤都按大的在下、小的在上的順序擺放在第一根樁上。目標是通過一系列的移動，將所有圓盤都移到另一根樁上去。每次只能移動一個圓盤，并且不能違反大的在下、小的在上的規定。

這個問題有個優雅的遞歸解法，如圖2所示。欲將個圓盤從1號樁轉移至3號樁上（2號樁作為輔助樁），則先將個圓盤從1號樁轉移至2號樁上（3號樁作為輔助樁），再將最大的一個圓盤從1號樁直接移動到3號樁上，最后把個圓盤從2號樁轉移至3號樁上（1號樁作為輔助樁）。當然，如果，把唯一的這個圓盤從1號樁直接移動到3號樁上即可。

圖2 漢諾塔謎題的遞歸解法

顯然，算法的基本操作是將一個圓盤從一根樁移動到另一根樁上去。令M(n)表示算法在處理個圓盤時所要求的移動步驟總數。那么，根據上面的算法描述（同時也請參考圖1.13），我們就可以得出下面關于M(n)的方程：

，當n>1時

上式可化簡為

，當n>1時

這樣的方程稱為遞歸關系式（recurrence relalion），因為它們表明了數列的第項與它的前項之間的關系。具體到這道題目，數列的第項，即M(n)，比它的前一項M(n?1)的兩倍還要多1。請注意，這樣的數列并不唯一，因為此時還沒有指定數列的首項。由于算法指定在僅有一個圓盤時，僅須移動一步，題目就可得解，所以我們就能夠為遞歸關系附加一個條件，即M(1)=1。毫不奇怪，這個條件就稱為初始條件（initial condition）。把以上分析綜合一下，我們就得出了個圓盤條件下的漢諾塔謎題所對應的遞歸關系式及其初始條件：

M(n)=2M(n-1)+1，當n>1時，

M(1)=1。

在這里，我們不采用概覽的前半部分介紹過的標準方法來求解這個方程，而是嘗試用歸納法：先利用上述方程算得M(n)最開始若干項的值，并列成表格，嘗試找出通用模式，然后證明這個模式適用于所有的正數n。

考察M(n)最開始若干項的值以后，我們發現似乎有公式圖像說明文字成立。顯然，有圖像說明文字。證明該公式對一切n>1皆成立的最簡單方法就是把公式本身代入方程，看看是否對一切符合大小的方程都成立即可。結果證明的確如此，因為：

因此，我們就得到了一個指數算法，這就是說即使對于不太大的，算法的運行也會花費長得難以想象的時間。究其原因，并不在于該特定算法本身設計拙劣，并不難證明，對于這個問題來說，該算法已經是所有可能的算法中最高效的。是問題內在的困難性，使得解決它的嘗試有了指數級別的難度。但這未必不是好事：在漢諾塔謎題的發明者édouard Lucas在19世紀80年代發表的最初版本中，梵天之塔的僧侶們在移動完64個圓盤以后，世界即將毀滅。假設僧侶們不吃、不睡、不死，并且每分鐘移動一個圓盤的話，世界將在約圖像說明文字年毀滅，這個時間比估算的宇宙年齡要長約1000倍。

作為練習，讀者也許愿意動手求解謎題受限的漢諾塔中的最小移動步數，這是諸多經典版本的變形之一：

4 不變量

我們以不變量的思想作為概覽部分的壓軸話題。在我們的討論中，所謂不變量（invariant），就是在任何一個算法在解題時保持不變的某種性質。對于謎題一般的問題而言，不變量經常用來說明某個問題無解，因為稱為不變量的性質在謎題的初始狀態成立，而在所要求的終止狀態卻并不成立。我們來看一些例子。

缺角棋盤的多米諾鋪陳 是否可能用多米諾骨牌1鋪滿一塊缺了一個角的棋盤（如圖3（a））？是否可能用多米諾骨牌鋪滿一塊缺了對角線上的兩個對角的棋盤（如圖3（b））？

圖3（a）缺了一個角的棋盤 （b）缺了對角線上的兩個對角的棋盤

第一個問題的答案肯定是“不行”：任何多米諾鋪陳都只能覆蓋偶數個方塊（覆蓋方塊的偶數配對特性就是這里的不變量），而第一個問題中的棋盤上的方塊數是一個奇數。

第二個問題的答案也是“不行”，盡管題設棋盤上的方塊數顯然是偶數。涉及的不變量并非同一個：由于一塊多米諾骨牌會覆蓋一明一暗兩個方塊，所以在任何多米諾鋪陳中覆蓋的明暗方塊數都是一樣多的。這么一來，能夠覆蓋題設中棋盤的多米諾鋪陳就不可能存在了，因為明暗方塊數由于缺了對角線上兩個對角，而相差了兩個。

一般地，奇偶配對（even-odd parity）以及著色（coloring），是運用不變量思想時用得最廣的兩種方法。謎題“最后一個球”和“騎士的征途”是兩個典型應用例子，讀者可以參考。

不變量的另一種重要性可以在另一道關于在古老的普魯士城市哥尼斯堡中如何散步的著名謎題中得到體現。

是否可能在單次散步中，過哥尼斯堡的所有橋僅一次，并返回起點？河流、兩座小島以及七座橋的草圖如圖4所示。

圖4連接陸地和兩座小島，并供人過河的哥尼斯堡七橋

著名的瑞士數學家Leonhard Euler（1707—1783）解出了本題。首先，Euler注意到，經過的陸地——無論是河岸還是小島——都和問題求解無關。唯一有關的，是橋建立起來的連接。用現代術語來說，就是這種洞見成功地使他把原問題變換成了一個圖論問題，如圖5所示。（事實上，該圖是一個多重圖，因為連接圖的某些頂點的，可能不止一條邊。）

圖5 表達哥尼斯堡七橋問題的多重圖

問題就在于圖5中的這個多重圖中是否存在一條Euler回路：一個鄰接頂點的序列，它在回到起始頂點前遍歷了所有的邊僅一次。Euler注意到，符合這種要求的回路中，進入一個頂點的次數必須恰好等于離開該頂點的次數。所以，若要多重圖中存在這種回路，就必須滿足接觸頂點的邊數——稱為該頂點的度數——對于所有的頂點而言皆為偶數。這個不變量性質就決定了哥尼斯堡七橋問題無解，因為條件不滿足：圖5中所有的頂點度數都為奇數。更有甚者，基于同樣的分析，可以發現即使不要求回到起點，散步時想要過每座橋僅一次也是不可能的。若要實現這種散步路線（稱為Euler路徑），除起點和終點這兩個頂點外，其他所有頂點的度數都必須是偶數。

順便指出，連通多重圖中若要存在Euler回路和Euler路徑，則上述條件不僅是必要的，也是充分的。（如果說一個多重圖是連通的，就意味著每對頂點之間都存在一條路徑。當然，如果這一點不成立，Euler回路和Euler路徑的存在性也就無從談起了。）這個事實首先是由Euler發現的，但后來由另一位數學家證明。讀者可以利用以上分析來求解正文部分的謎題一筆畫。

如今，哥尼斯堡七橋問題已經成為學習圖論這門計算和運籌學學科的重要分支必讀的內容。人們也經常以它為例，來說明解謎活動在嚴肅科學、教育和實際應用中的潛在用途。

下面這道謎題里，不變量將扮演一個不同的角色，不再用來證明解不存在。

求將n×m格的巧克力條掰成nm塊的最少次數，每次只允許沿著縱橫方向掰，且每次只能掰一個碎塊。

讀者不妨親手嘗試一下這道數學家和計算機科學家們都會做的謎題，再看下面兩句話揭開的謎底。由于一次只能掰一個碎塊，而每掰斷一次只會讓碎塊數增加1，所以要把n×m格的巧克力條掰成nm塊，就需要掰(nm-1)次。而且，只要沿著縱橫方向，無論怎么掰次都能把n×m格的巧克力條掰成nm塊。

我們舉的最后一個例子中，不變量將扮演一個更具建設性的角色，它將指明算法運行的必由之路。下面的謎題由史上最著名的兩位制謎人Henry E. Dudeney [Dud02, p. 95]和Sam Loyd [Loy59, p. 8]分別發表在兩處2。這道題目的所有變形都不過是把方格數目和表述文字簡單變化一下而已。

用一塊的棋盤表示一片田地，用同一種顏色的兩枚棋子表示一個農夫和他的妻子，用同一種其他顏色的兩枚棋子表示一只公雞和一只母雞。每次移動棋子都可以把它移到上下左右任一方向的相鄰位置，但不能移到對角線的相鄰位置。如果起始位置如圖6（a）所示，然后按照農夫、農婦、公雞、母雞的順序依次移動各個棋子，直到雞被人捉住為止，即人再移一步即占據雞的位置。試用最少移動步數完成題設任務。

我們很快就會發現，農夫捉不到公雞，農婦捉不到母雞。將棋盤按國際象棋棋盤進行著色以后，我們就能看出來，只有人和雞在相鄰的兩個顏色不同的格子里的時候（見圖6（b）），人才能捉到雞。但是，農夫和公雞、農婦和母雞分別是從相同顏色的格子里出發的，這個性質在移動任意有限步以后仍然保持。所以，農夫應該去捉母雞，而農婦應該去捉公雞。即使雞不配合，它們也不能避免這樣的宿命：一只在八步以后被捉，另一只在九步以后被捉。

圖6（a）謎題田地里的雞題設的棋盤（b）將棋盤著色后的結果

至于某個具體謎題應該應用哪個策略來求解，這個問題沒有答案?。ㄈ绻械脑?，謎題也就失去益智娛樂的魅力了。）策略只是通用工具，對于特定的謎題來說，策略可能管用也可能不管用。經過大量的實踐以后，才能對策略的有效性產生一些直覺，但這樣的直覺當然不可能萬無一失。

還有，以上講述的策略和技術為具備算法背景的謎題提供了一套極有用的工具集。

當然，即使已經知道要應用哪種策略，求解過程也可能仍然遠非易事。比如，運用不變量來證明某個謎題無解是一種慣用手法。但是即使已經知道奇偶配對以及棋盤著色可能有利于導向答案，發掘出一個特定問題的不變量卻可能仍然很困難。還是那句話，多多練習，解題任務就會變得更順手，但難度不一定很小。

本文節選自《算法謎題》

本文轉載自異步社區。

Python

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。