第1章　算法基礎(chǔ)

學(xué)習(xí)目標(biāo)

充分理解并掌握算法的相關(guān)概念，能夠分析一段代碼是否具備算法的特征

理解算法設(shè)計(jì)的一般過(guò)程

能夠運(yùn)用算法復(fù)雜性分析方法正確估算算法的時(shí)間復(fù)雜度和空間復(fù)雜度

能夠運(yùn)用面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言C++描述算法

掌握遞歸的概念，能夠辨別遞歸的停止條件和遞歸方程

熟悉基本數(shù)據(jù)結(jié)構(gòu)和數(shù)學(xué)公式的概念及使用方法

有兩種思想，像珠寶商放在天鵝絨上的寶石一樣熠熠生輝，一個(gè)是微積分，另一個(gè)就是算法。微積分以及在微積分基礎(chǔ)上建立起來(lái)的數(shù)學(xué)分析體系造就了現(xiàn)代科學(xué)，而算法則造就了現(xiàn)代世界。

——David Berlinski之THE ADVENT OF THE ALGORITHM

計(jì)算機(jī)行業(yè)是一個(gè)肥沃且充滿勃勃生機(jī)的生態(tài)圈，不斷孕育著一代又一代的新技術(shù)、新概念，毫無(wú)疑問(wèn)，那些站在科技浪尖的技術(shù)概念自然成為開發(fā)者的寵兒。縱觀計(jì)算機(jī)行業(yè)的發(fā)展歷程，不難發(fā)現(xiàn)無(wú)論該行業(yè)的浪潮多么朝夕莫測(cè)，計(jì)算機(jī)和軟件發(fā)展背后的根基卻巋然屹立、經(jīng)年不變，算法便是其根基之一，它對(duì)計(jì)算機(jī)行業(yè)的發(fā)展起著不可估量的作用。因此，算法在計(jì)算機(jī)專業(yè)教育中占有很重要的地位。對(duì)算法的學(xué)習(xí)和研究主要包括算法設(shè)計(jì)、算法描述、算法的正確性證明、算法分析和驗(yàn)證等幾方面。

另外，算法的設(shè)計(jì)與分析是計(jì)算機(jī)專業(yè)教育的核心問(wèn)題，掌握算法的設(shè)計(jì)策略和算法分析的基本方法是對(duì)一個(gè)軟件工作者的基本要求，為此，本書主要對(duì)這兩大方面進(jìn)行研究。設(shè)計(jì)策略是指面對(duì)一個(gè)問(wèn)題，如何設(shè)計(jì)一個(gè)正確有效的算法；算法分析是指對(duì)于一個(gè)已設(shè)計(jì)的算法，如何評(píng)價(jià)其優(yōu)劣。二者相互依存，設(shè)計(jì)出的算法需要進(jìn)行分析和評(píng)價(jià)，對(duì)算法的分析和評(píng)價(jià)反過(guò)來(lái)又將推動(dòng)算法設(shè)計(jì)的改進(jìn)。