第3版的變化

第3版有若干變化。其中最重要的變化是介紹減治法和分治法的先后順序。第3版會先介紹減治法，后介紹分治法，這樣做有以下幾個(gè)優(yōu)點(diǎn)。

●　較之分治法，減治法更簡單。

●　在求解問題方面，減治法應(yīng)用更廣。

●　這樣的編排順序便于先介紹插入排序，后介紹合并排序和快速排序。

●　數(shù)組劃分的概念通過選擇性問題引入，這次利用Lomuto算法的單向掃描來實(shí)現(xiàn)，而將Hoare劃分方法的雙向掃描留至后文與快速排序一并介紹。

●　折半查找歸入介紹減常量算法的章節(jié)。

另一個(gè)重要變化是重新編排第8章關(guān)于動(dòng)態(tài)規(guī)劃的內(nèi)容，具體如下所述。

●　導(dǎo)述部分的內(nèi)容是全新的。在前兩版中用計(jì)算二項(xiàng)式系數(shù)的例子來引入動(dòng)態(tài)規(guī)劃這一重要技術(shù)，但在第3版中會介紹3個(gè)基礎(chǔ)性示例，這樣介紹的效果更好。

●　8.1節(jié)的習(xí)題是全新的，包括一些在前兩版中沒有涉及的流行的應(yīng)用。

●　第8章其他小節(jié)的順序也做了調(diào)整，以便達(dá)到由淺入深、循序漸進(jìn)的效果。

此外，還有其他一些變化。增加了不少與本書所述算法相關(guān)的應(yīng)用。遍歷圖算法不再隨減治法介紹，而是納入蠻力算法和窮舉查找的范疇，我認(rèn)為這樣更合理。在介紹生成組合對象的算法時(shí)，新增了格雷碼算法。對求解最近對問題的分治法有更深入的探討。改進(jìn)的內(nèi)容包括算法可視化和求解旅行商問題的近似算法，當(dāng)然參考文獻(xiàn)也有相應(yīng)的更新。

第3版一共新增約70道習(xí)題，其中涉及算法謎題和面試問題。