本書的目標是研究一大類重要且有用的算法，即適合計算機實現(xiàn)的求解問題的方法。為實現(xiàn)該目標，本書做了以下工作：

• 介紹許多不同領域的應用，重點關注有趣且重要的基礎算法；
• 花費足夠的時間來理解每個算法的本質和展示相關細節(jié)；
• 使用C語言來描述算法，同時提供有用的實現(xiàn)；
• 關注算法的性能特征；

算法的性能分析很重要。
理解算法的性能特征可能同時需要實驗和數(shù)學分析。

理解本書里展示的程序的方法是：

• 實現(xiàn)這些程序；
• 測試這些程序；
• 檢查這些程序的變種；
• 討論這些程序對小規(guī)模實例的操作；
• 在跟實際中遇到的類似的較大規(guī)模的實例上運行這些程序；

本書開發(fā)問題解的一般方法的步驟是：

• 先得到問題的一個簡單的解；
• 后尋求理解該算法的性能特征；
• 重復若干次上述步驟后，得到求解該問題的一個有效率且有用的算法；

為什么要關注算法的性能特征？

• 幫助開發(fā)優(yōu)化版本的算法；
• 比較執(zhí)行同一任務的不同算法；
• 預測或者確保算法在大規(guī)模問題的性能；

第1.1節(jié) 算法

當我們編寫一個計算機程序時，我們通常是正在實現(xiàn)一個先前設計好的用于解決某個問題的方法。這種方法通常跟使用的計算機無關，可能同等適用于許多計算機和計算機語言。為了學習問題是如何被解決的，我們必須要研究的正是這種方法，而不是計算機程序。

在計算機科學里，使用算法來描述一種適合用計算機程序來實現(xiàn)的問題解決方法。算法是計算機科學的基礎：算法是許多計算機領域的核心研究對象。大部分算法都涉及跟計算相關的數(shù)據(jù)的組織方法。通過這種方式創(chuàng)建的對象被叫做數(shù)據(jù)結構。數(shù)據(jù)結構也是計算機科學的核心研究對象。因此，算法和數(shù)據(jù)結構密不可分。

本書的觀點是數(shù)據(jù)結構是算法的副產(chǎn)品或者產(chǎn)品。因此，為了理解算法，必須要去研究數(shù)據(jù)結構。

簡單的算法可以產(chǎn)生復雜的數(shù)據(jù)結構，同理，復雜的算法也可以使用簡單的數(shù)據(jù)結構。在本書中，我們將研究許多數(shù)據(jù)結構的性質。

當我們使用計算來幫助我們解決一個問題時，我們通常會面臨許多可能的不同的方法。對于小規(guī)模問題來說，只要我們有一種可以正確解決問題的方法就行，幾乎跟使用哪一種方法無關。對于大規(guī)模問題來說，我們被激發(fā)去設計盡可能有效率地使用時間或者空間的方法。

我們學習算法設計的主要原因是這門學科給了我們一種獲得巨大節(jié)省的潛力，甚至有可能去做一些原本不可能實現(xiàn)的任務。在一個需要處理上千萬對象(數(shù)量級為)的應用里，使用一個設計良好的算法來使程序運行快上千萬倍(數(shù)量級為)的事情很常見。比如，我們將在第1.2節(jié)里看到的一個這樣的例子，在全書中看到許多其他的場景。作為對比，投資額外的錢和時間去夠買和安裝一臺新的計算機給一個程序帶來的速度提升可能只有或者。不管應用領域是什么，仔細的算法設計是求解大規(guī)模問題的過程中的非常重要的部分。

當要開發(fā)一個大型或者復雜程序時，必須花費大量努力去理解和定義要解決的問題、管理問題的復雜度、將該問題分解成更小的容易實現(xiàn)的子任務。
一般來說，許多算法分解之后的實現(xiàn)是平凡的。但是，在大部分情況里，總有一些算法的選擇很關鍵，因為系統(tǒng)的大部分資源將花費在運行這些算法。我們將在本書中重點講述這類算法，將研究各種各樣的、對求解在許多應用領域里的大型問題有用的基礎算法。

雖然在計算機中共享程序是越來越普遍，我們也期望在本書中盡可能多地共享使用算法，但是我們可能還是不得不實現(xiàn)一小部分算法。實現(xiàn)簡單版本的基礎算法可以幫助我們更好地理解它，從而更有效地使用它的高級版本。更重要的是，會多次出現(xiàn)重新實現(xiàn)基礎算法的機會。
主要原因有兩個：

• 我們經(jīng)常會面臨完全新的計算環(huán)境(軟件或者硬件)，該計算環(huán)境有著之前舊的實現(xiàn)可能不會完全利用的新特征。換句話說就是，我們經(jīng)常根據(jù)問題來裁剪實現(xiàn)基礎算法，使得我們的解具有更好的可移植性和存在更長的時間，而不是依賴系統(tǒng)函數(shù)。
• 在許多計算上的共享軟件機制通常并沒有強大到允許我們裁剪標準程序使其對特定任務更有效率地執(zhí)行，所以做一個新的實現(xiàn)更容易。

計算機程序經(jīng)常被過度優(yōu)化?？赡懿⒉恢档没ㄙM努力去保證一個特定算法的實現(xiàn)是可能最有效率的，除非該算法被使用許多次或者被用于一個大型任務。除此之外，一個仔細的、相對簡單的實現(xiàn)就夠了：我們自信該該實現(xiàn)能工作，且最差情形的運行時間可能比最好情形慢上5到10倍，這意味著最差情形可能要多運行額外的若干秒時間。作為比較，在最開始就選擇合適的算法會產(chǎn)生100倍或者1000甚至更多的差別，換算成運行時間就是分鐘、小時甚至更長。在這本書里，我們重點關注最好算法的最簡單合理的實現(xiàn)。

針對某個特定任務去選擇最好的算法是一個復雜的過程，可能包含高級的數(shù)學分析。在計算機科學中，算法分析就是研究這樣過程的分支。我們要研究的許多算法已通過分析表明性能良好的，其他算法可通過經(jīng)驗就可簡單地知道其運行良好。

雖然我們的主要目標是學習重要任務的合理算法，但是我們也會關注這些方法的相對性能。如果我們不了解一個算法使用了哪些資源，則我們就不應該使用該算法。我們要努力去了解我們的算法是如何按照預期運行的。

第1.2節(jié) 連通性問題

假設給定一個整數(shù)對序列，其中每個整數(shù)都表示某種類型的對象。
整數(shù)對p-q表示整數(shù)p跟整數(shù)q之間是連通的。
假設連通關系具有傳遞性：如果整數(shù)p和整數(shù)q是連通的，整數(shù)q和整數(shù)r是連通的，則整數(shù)p和整數(shù)r是連通的。
我們的目標是編寫一個程序來從集合中過濾額外的整數(shù)對：只有該程序截止目前所看到的整數(shù)對并不能推導出整數(shù)p和q是連通的，該程序才會輸出整數(shù)對p-q。如果之前的整數(shù)對確實可推導出整數(shù)p和整數(shù)q是連通的，則該程序就忽略整數(shù)對p-q，然后繼續(xù)處理下一個整數(shù)對。

分析：
我們的問題是要設計一個能判斷新的整數(shù)對是否連通的程序，其中該程序能記憶足夠多的有關其已看到的整數(shù)對的信息。

連通性問題的一個難點：如何安排節(jié)點和連接來快速判斷在一個大型網(wǎng)絡里任意給定的兩個節(jié)點之間是否是連通的？

連通性問題有許多重要的應用，這里簡要地考慮3個實例來表明連通性問題的本質。

例1 連接計算機
假設每個整數(shù)表示在一個大型網(wǎng)路中的一個計算機，每個整數(shù)對表示兩個計算機之間的連接。
則我們的問題可用來判斷：為了p和q之間能夠通信，是否要直接新增一條p和q之間的連接，或者是否可以利用現(xiàn)有的連接建立一條p和q之間的通信鏈路。
在這類應用中，我們可能需要處理的節(jié)點數(shù)有千萬個(數(shù)量級為)，連接數(shù)為百億個(數(shù)量級)，或者更多。如果沒有一個有效率的算法，則該應用是不可能有解的。

例2 連接電路
假設每個整數(shù)表示一個電路網(wǎng)路里的一個節(jié)點，每個整數(shù)對表示連接兩個節(jié)點的電線。
在這里，如果可能的話，可使用我們的程序來找到一種方式來連接所有的節(jié)點，同時不增加額外的連接。
并不能保證在列表中的邊足以連接所有的點。
后面將看到：判斷一個列表里的邊是否足以連接所有的點將成為我們的程序的一個主要應用。

例3 變量名等價
在某種編程環(huán)境中，經(jīng)過一系列的變量聲明后，如何來判斷給定的兩個變量名是不是等價的？
變量名等價應用是一個很早的應用，激發(fā)了我們將要考慮的若干個算法。
變量名等價應用將我們的問題直接和一個簡單的抽象關聯(lián)起來，該簡單的抽象為我們提供了一種可以使得我們的算法對一大類應用都適用的方式。

變量名等價應用要求我們給每個不同的變量名關聯(lián)一個整數(shù)，電路連接應用里要求為每個節(jié)點關聯(lián)一個整數(shù)，計算機連接應用里要求為每個計算機關聯(lián)一個整數(shù)。我們將在第10章到第16章里考慮一系列的、以有效率的方式提供這類關聯(lián)的算法。因此，在這一章，為了不失一般性，我們假設總共有N個整數(shù)，從0到N-1。

我們尋求的程序應該是一個做具體且定義良好的任務的程序。同時，我們還有許多其他相關的問題要解決。

在開發(fā)一個算法時要面對的首要任務之一就是確保我們已用合理的方式描述了問題。我們對一個算法要求的太多，可能期望需要完成任務所需的時間和空間就越多。由于這種關系是不可能先驗地知道的，所以一旦發(fā)現(xiàn)某個問題很難解決或者解決起來代價很高時，我們就修改問題的描述。一旦發(fā)現(xiàn)算法提供的信息要比原始問題描述要求的信息更有用時，我們就修改問題的描述。比如，我們的連通性問題描述僅要求我們的程序能判斷任意給定的整數(shù)對p-q是不是連通的，而沒要求我們的程序能打印任何一種或者所有使得整數(shù)p與整數(shù)q連通的方式。添加這樣一種描述會使得問題更難，會導致一個不同家族的算法，這些算法我們會在第5章簡要介紹和第7部分詳細論述。

上一段里添加的描述對我們比原始描述要求更多的信息，我們也可以添加描述使得問題比原始描述要求更少的信息。比如，我們可能想簡單地解決問題：M個連接是否足以將N個對象都連接起來？這個問題表明：為了開發(fā)出有效率的算法，我們通常需要對我們正在處理的抽象對象做高級的推理。在這里，來自圖論的一個基本的結果意味著所有N個對象都連通當且僅當通過連通算法輸出的整數(shù)對的個數(shù)為N-1。換句話說，一個連通算法永遠都不會輸出超過N-1個整數(shù)對，因為一旦連通算法已經(jīng)輸出了N-1個整數(shù)對，則之后連通算法遇到的任何一個整數(shù)對將是連通的。因此，我們可以得到一個回答yes-no的程序，該程序是通過修改解決連通性問題的程序為一個遞增計數(shù)器的程序得到的：

• 不輸出每個之前不連通的整數(shù)對；
• 如果計數(shù)器的值不為N-1，輸出no；當計數(shù)器值為N-1時，輸出yes。

這個問題只是我們可能想要解決的有關連通性的許多問題中的一個。
輸入的每個整數(shù)對的集合是一個圖，輸出的每個整數(shù)對的集合是該圖的生成樹，該生成樹連接了所有對象。我們將在第7部分考慮圖、生成樹及相關的算法。

為了使得我們?yōu)檫B通性問題開發(fā)的算法適用更多的類似問題，嘗試去確認我們將要執(zhí)行的基本操作是有價值的。每次得到一個新的整數(shù)對，首先要判斷給整數(shù)對是否表示一個新的連接，如果是，然后將該新連接信息整合到已有的對象連接信息里，以便程序能對未來看到的連接進行檢查。先用輸入的整數(shù)值表示在抽象集合里的元素，然后設計算法和數(shù)據(jù)結構，我們將這兩步封裝為抽象操作：

• find：查找集合中是否包含一個給定的數(shù)據(jù)項；
• union：用數(shù)據(jù)項的并集替換包含兩個給定數(shù)據(jù)項的集合；

用這兩個抽象操作來組織我們的算法似乎并不妨礙對連通性問題的求解。
這兩個抽象操作可能對求解其他問題有幫助。
通常，在計算機科學和算法設計中，開發(fā)功能更強大的抽象層是一個必需的過程。在本書中會無數(shù)次遇到這種情形。在本章里，我們非正式地使用抽象思維來指導我們設計求解連通性問題的程序，在第4章里，我們將看到如何使用C代碼來封裝抽象操作。

使用find和union兩個抽象操作可以輕松地求解連通性問題。
從輸入中讀取一個新的整數(shù)對p-q后，我們對該整數(shù)對的每個成員執(zhí)行find操作。如果該整數(shù)對的所有成員在同一個集合里，我們將跳過該整數(shù)對開始處理下一個整數(shù)對；否則，我們做一次union操作，并輸出該整數(shù)對。這里的集合表示的是連通組件：該集合的元素是對象；任何兩個對象都是連通的。這種方法將連通性問題算法解的開發(fā)簡化為定義一個數(shù)據(jù)結構來表示連通組件的集合以及開發(fā)有效率地使用該數(shù)據(jù)結構的find與union算法。

有許多可行的方式來表示和處理抽象集合，我們會在第4章中考慮詳細的細節(jié)。在本章里，我們的關注點是尋找一種能支持有效率的find和union操作的表示。

第1.3節(jié) Union-Find算法

開發(fā)一個求解給定問題的有效的算法的第一步是實現(xiàn)求解該問題的一個簡單的算法。如果我們要解決的是若干個容易的特定問題實例，則該簡單實現(xiàn)可能就能完成這個任務。如果需要更高級的算法，則該簡單實現(xiàn)可以為我們提供一個對小規(guī)模情形的正確性檢查和評估性能特征的基準。雖然我們經(jīng)常關心性能，但是我們對求解問題的第一個程序的主要關心是保證該程序是這個問題的正確的解。

容易想到的第一個辦法是以某種形式保存所有的輸入整數(shù)對，然后編寫一個遍歷這些整數(shù)對的函數(shù)來嘗試發(fā)現(xiàn)下一個輸入對是否連通。
我們使用的是另一種辦法。首先，在實際應用中，整數(shù)對的個數(shù)可能足夠大，以助于不能將它們?nèi)４嬖趦?nèi)存里。其次，即使我們把輸入對全保存下來了，也沒有簡單的方法能從所有連通的集合快速判斷出兩個對象是否連通。雖然我們考慮的是在第5章里采用的辦法，但是我們在本章里考慮的辦法更簡單，因為這些辦法求解的是難度更小的問題，且更有效率，因為這些辦法不要求保存所有的整數(shù)對。這些辦法都使用一個整數(shù)數(shù)組來持有實現(xiàn)union和find所必需的信息，其中一個整數(shù)對應一個對象。

數(shù)組是我們將在第3.2節(jié)討論的基礎的數(shù)據(jù)結構。在這里，我們使用數(shù)組的最簡單形式：比如，我們期望使用100個整數(shù)，我們就聲明a[100]；我們使用a[i]來引用第i個整數(shù)，其中0<=i<100。

程序1.1是求解連通問題的一個簡單實現(xiàn)，名叫quick-find算法。該算法的基礎是一個整數(shù)數(shù)組，該數(shù)據(jù)有這樣的性質：p和q連通當且僅當數(shù)組的第p個元素和第q個元素相等。我們將該數(shù)組第i個元素初始化為i，其中0<=i<N。為了實現(xiàn)對p和q的union操作，我們遍歷整個數(shù)組，修改所有值等于p的數(shù)組元素的值為q。

圖1.3展示了圖1.1中的實例的union操作的變化情況。一方面，為了實現(xiàn)find操作，我們僅需測試下標索引的數(shù)組元素的相等性即可。另一方面，對每個輸入對，union操作都需要遍歷整個數(shù)組。

性質1.1
對于有N個對象連通性問題，如果需要M次union操作，則quick-find算法至少要執(zhí)行MN條指令。

由于在現(xiàn)代計算機上每秒鐘可以執(zhí)行上億()條或者上十億()條指令，所以如果M和N比較小時，則開銷是可以忽略的。但是我們可能會在一個現(xiàn)代應用里遇到有上千萬個對象和上百億個輸入對。一個不可逃避的結論是使用quick-find算法來求解這樣的問題是不可行的。我們將在第2章里考慮精確量化這個結論。

圖1.4是圖1.3的一個圖形化表示。我們將某個對象看做是它們所屬的集合的代表，其他對象都指向的其在集合中的該代表。很快就會知道轉移到數(shù)組的這種圖形化表示的原因。觀察到：用這種表示展示的對象之間的連接不一定跟輸入對之間的連接一樣。這種表示是算法選擇用來記憶的信息，該信息能知道將來的輸入對之間是否連通。