前言

本書為普通高等教育“十一五”國家級規(guī)劃教材。

算法設(shè)計與分析不僅是計算機科學(xué)與技術(shù)專業(yè)學(xué)生的必備知識，也是計算機應(yīng)用工作者必不可少的基礎(chǔ)知識。掌握扎實的算法設(shè)計與分析理論和方法有助于理工科學(xué)生進(jìn)一步學(xué)習(xí)計算機技術(shù)，適應(yīng)更廣泛的職業(yè)挑戰(zhàn)。

計算機學(xué)科教學(xué)計劃2001（Computing Curricula 2001，簡稱CC2001）將計算機學(xué)科分成14個領(lǐng)域，每個領(lǐng)域分成若干個知識單元，每個知識單元又包括若干個主題。CC2001強調(diào)算法，重視算法設(shè)計與分析能力和程序設(shè)計能力。計算機算法的基本內(nèi)容主要包含在算法與復(fù)雜性（Algorithm And Complexity，簡稱AL）和程序設(shè)計基礎(chǔ)（Programming Fundamental，簡稱PL）等知識領(lǐng)域中。在CC2001建議的計算機科學(xué)與技術(shù)專業(yè)的280個核心學(xué)時中，程序設(shè)計與算法方面分配90個核心學(xué)時，約占總核心學(xué)時的32.1%。

算法領(lǐng)域涉及的內(nèi)容廣泛，通常包括迄今為止，算法學(xué)家們所設(shè)計的許多基本和經(jīng)典算法，如排序、搜索、圖算法、組合問題算法、字符串算法和大量的數(shù)值算法，算法問題求解、算法分析技術(shù)和常用的算法設(shè)計策略，可計算性理論和問題復(fù)雜性的研究，如計算模型、NP完全問題和問題復(fù)雜度下界理論。近年來，算法研究在隨機算法、近似算法、密碼算法、分布式算法和并行算法，以及其他算法方面也都有很多新成果。

作為“算法設(shè)計與分析”課程教材，根據(jù)我國在算法與數(shù)據(jù)結(jié)構(gòu)方面課程開設(shè)的實際情況，本書不再重復(fù)屬于我國傳統(tǒng)“數(shù)據(jù)結(jié)構(gòu)”課程中的基本數(shù)據(jù)結(jié)構(gòu)和算法的內(nèi)容，但選用快速排序等在“數(shù)據(jù)結(jié)構(gòu)”課程中已學(xué)過的若干排序、搜索和圖算法，它們被作為算法設(shè)計策略和算法分析的實例使用。這種做法不是內(nèi)容的簡單重復(fù)，而是必要的和有益的深化。以學(xué)生熟知的知識為基礎(chǔ)，介紹新知識，可使學(xué)生更容易理解和接受新的算法知識。

算法知識理論性較強，涉及的范圍又很廣，給學(xué)習(xí)和理解造成困難。為了將本書寫成條理清晰、內(nèi)容翔實、邏輯嚴(yán)謹(jǐn)、深入淺出的“算法設(shè)計與分析”教材，作者做了以下努力。

首先，本書分3部分組織內(nèi)容，力求做到結(jié)構(gòu)清晰、內(nèi)容取舍恰當(dāng)。

其次，書中算法都有完整的C++程序，程序結(jié)構(gòu)清楚，構(gòu)思精巧，對程序代碼都做了詳細(xì)注釋，所有程序都已在VC++環(huán)境下編譯通過并能正確運行，它們既是學(xué)習(xí)算法設(shè)計的示例，也是很好的C++程序設(shè)計示例。

此外，本書通過大量實例和圖示介紹算法，并有豐富的習(xí)題，便于自學(xué)。

這樣做的目的是在保持算法科學(xué)性的同時，加強其技術(shù)性和實用性，也降低算法學(xué)習(xí)的難度，使復(fù)雜抽象的算法設(shè)計更容易為學(xué)習(xí)者理解和掌握。這也體現(xiàn)了計算機學(xué)科的科學(xué)性和工程性、理論性和實踐性并重的學(xué)科特點。

全書包括3部分：算法和算法分析、算法設(shè)計策略及求解困難問題。

第1部分介紹算法概念、算法問題分類和問題求解方法，算法復(fù)雜度、遞歸技術(shù)，還介紹了兩種新的數(shù)據(jù)結(jié)構(gòu)：跳表和伸展樹，以及它們特定的算法分析方法。

第2部分討論常用的算法設(shè)計策略：基本搜索和遍歷方法、分治法、貪心法、動態(tài)規(guī)劃法、回溯法和分枝限界法。對于每種算法設(shè)計策略，通常先介紹一般方法，然后使用該策略解決若干經(jīng)典的算法問題。

第3部分介紹NP完全問題、隨機算法、近似算法，并對現(xiàn)代密碼學(xué)和數(shù)論算法也做了簡要論述。

本書作者在南京郵電大學(xué)講授“算法設(shè)計與分析”和“數(shù)據(jù)結(jié)構(gòu)”課程多年。本書是在作者編寫出版的多本關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)領(lǐng)域教材的基礎(chǔ)上，參考了近年來國內(nèi)外多種算法設(shè)計與分析的優(yōu)秀教材編寫而成的。本書的編寫得到了電子工業(yè)出版社的大力支持，并得到了南京郵電大學(xué)和計算機學(xué)院領(lǐng)導(dǎo)的推薦和關(guān)心，在此表示衷心感謝。

書中若有不妥之處，敬請讀者批評指正。

作者