基礎(chǔ)部分

　　這一部分將引導(dǎo)讀者開始思考算法的設(shè)計和分析問題，簡單介紹算法的表達(dá)方法、將在本書中用到的一些設(shè)計策略，以及算法分析中用到的許多基本思想。本書后面的內(nèi)容都是建立在這些基礎(chǔ)知識之上的。

　　第1章是對算法及其在現(xiàn)代計算系統(tǒng)中地位的一個綜述。本章給出了算法的定義和一些算法的例子。它還說明了算法是一項技術(shù)，就像快速的硬件、圖形用戶界面、面向?qū)ο笙到y(tǒng)和網(wǎng)絡(luò)一樣。

　　在第2章中，我們給出了書中的第一批算法，它們解決的是對n個數(shù)進(jìn)行排序的問題。這些算法是用一種偽代碼形式給出的，這種偽代碼盡管不能直接翻譯為任何常規(guī)的程序設(shè)計語言，但足夠清晰地表達(dá)了算法的結(jié)構(gòu)，以便任何一位能力比較強(qiáng)的程序員都能用自己選擇的某種語言將算法實現(xiàn)出來。我們分析的排序算法是插人排序，它采用了一種增量式的做法，另外還分析了合并排序算法，它采用了一種遞歸技術(shù)，稱為“分治法”。盡管這兩種算法所需的運行時間都隨n的值而增長，但增長的速度是不同的。我們在第2章中分析了這兩種算法的運行時間，并給出了一種有用的表示方法來表達(dá)這些運行時間。

　　第3章給出了這種表示式的準(zhǔn)確定義，稱為漸近表示。在第3章的一開始，首先定義了幾種漸近記號，它們主要用于表示算法運行時間的上界和/或下界。第3章余下的部分主要給出了一些數(shù)學(xué)表示方法。這一部分的作用更多的是為了確保讀者所用的記號能與本書中的記號體系相匹配，而不主要是教授新的數(shù)學(xué)概念。

　　第4章更深人地討論了第2章引人的分治方法。特別地，第4章包含了解決遞歸式的方法。遞歸式主要用于描述遞歸算法的運行時間?！爸鞣椒ā埃╩aster method）是一種功能很強(qiáng)的技術(shù)，它可以用于解決分冶算法中出現(xiàn)的遞歸式。第4章中的相當(dāng)-部分內(nèi)容都是在證明主方法的正確性。如果跳過這一部分證明內(nèi)容的話，也沒有什么太大的影響。

?

　　第5章介紹了概率分析和隨機(jī)化算法。概率分析一般用于確定一些算法的運行時間，在這些算法中，由于同一規(guī)模的不同輸人可能有著內(nèi)在的概率分布，因而在這些不同輸人之下，算法的運行時間可能有所不同。在有些情況下，我們假定算法的輸人符合某種已知的概率分布，于是，算法的運行時間就是在所有可能的輸人之下，運行時間的平均值。在其他情況下，概率分布不是來自于輸人，而是來自于算法執(zhí)行過程中所做出的隨機(jī)選擇。如果一個算法的行為不僅由其輸人決定，還要由一個隨機(jī)數(shù)生成器所生成的值來決定的話，它就是一個隨機(jī)化算法（randomizedalgorithm）。我們可以利用隨機(jī)化算法，強(qiáng)行使算法的輸入符合某種機(jī)率分布，從而確保不會有某輸入會始終導(dǎo)致算法的性能變壞;或者，對于那些允許產(chǎn)生不正確結(jié)果的算法，甚至能夠?qū)⑵溴e誤率限制在某個范圍之內(nèi)。

　　附錄A~附錄C包含了另一些數(shù)學(xué)知識，它們對讀者閱讀本書可能會有所幫助。在閱讀本書之前，讀者很可能已經(jīng)知道了附錄中給出的大部分知識（我們采用的某些符號約定與讀者過去見過的可能會有所不同），因而，可以將附錄視為參考材料。另一方面，你很可能從未見過第一部分中給出的內(nèi)容。第一部分中的所有各章和附錄都是以一種人門指南的風(fēng)格來編寫的。