基礎(chǔ)部分

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

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

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

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

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

?

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

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