本書以 Python 語(yǔ)言為平臺(tái),分四個(gè)部分介紹了算法的基本概念、五種經(jīng)典的算法思想、重要的數(shù)據(jù)結(jié)構(gòu)以及實(shí)踐中常用的幾種算法技術(shù)。除第 1 章和第 2 章外,書中每章內(nèi)容都包括了基本概念、實(shí)現(xiàn)方式、具體應(yīng)用以及達(dá)人修煉真題。每一種算法思想中的達(dá)人修煉真題都提供了相應(yīng)的源代碼,可供讀者運(yùn)行,從而達(dá)到理論與實(shí)踐并重的目的。
本書從算法基本分析到算法基本思想,再到具體應(yīng)用及大量真題,內(nèi)容全面,條理清楚,語(yǔ)言通俗。本書對(duì)計(jì)算機(jī)及相關(guān)專業(yè)本科生及研究生的面試、筆試將有所幫助;此外,計(jì)算機(jī)科學(xué)相關(guān)領(lǐng)域的工程師以及愛(ài)好者也可以將本書作為技術(shù)參考書籍,在需要時(shí)可查找所需算法的相關(guān)內(nèi)容并從中得到啟示;當(dāng)然,對(duì)計(jì)算機(jī)科學(xué)感興趣的高中生以及 IT 領(lǐng)域項(xiàng)目經(jīng)理也可以閱讀本書,從而開啟算法世界的大門。
◆各章自成體系,可以作為獨(dú)立的學(xué)習(xí)單元(算法基礎(chǔ)經(jīng)典算法思想重要數(shù)據(jù)結(jié)構(gòu)常用算法),滿足從 菜鳥向 達(dá)人進(jìn)階的的需求
零基礎(chǔ)也能輕松掌握,自學(xué)算法的好搭檔
◆73個(gè)示意圖,生動(dòng)介紹算法執(zhí)行過(guò)程
◆全書包含40余道經(jīng)典算法真題,每道題目均一題多解,深入剖析不同算法在性能方面的優(yōu)劣
◆免費(fèi)提供立體化學(xué)習(xí)資源,包括16個(gè)章節(jié)核心知識(shí)點(diǎn)講解視頻,各類算法實(shí)現(xiàn)源代碼、實(shí)例數(shù)據(jù)及運(yùn)行結(jié)果
隨著大數(shù)據(jù)處理、人工智能等領(lǐng)域的飛速發(fā)展和計(jì)算機(jī)性能的飛躍性提升,無(wú)論在學(xué)術(shù) 界還是產(chǎn)業(yè)界,計(jì)算機(jī)領(lǐng)域的前沿概念與技術(shù)都逐步深入到思維層面,數(shù)學(xué)在這其中發(fā)揮的 作用越來(lái)越重要,越來(lái)越多的高深數(shù)學(xué)理論被運(yùn)用到實(shí)際中來(lái),有效地解決了許多實(shí)際問(wèn)題, 例如分析幾何、小波分析、數(shù)值計(jì)算等。這一切讓人們逐步意識(shí)到計(jì)算機(jī)程序設(shè)計(jì)依賴的就 是數(shù)學(xué)知識(shí)和算法思想。在軟件工程師動(dòng)手編程完成某一任務(wù)之前,先要通過(guò)一系列的分析 過(guò)程來(lái)確定解決該任務(wù)的方法。首先,分析待求解任務(wù)/問(wèn)題,將其抽象為某種數(shù)學(xué)模型;然 后確定求解該問(wèn)題時(shí)的資源限制(包括時(shí)間資源、電力資源、存儲(chǔ)資源、計(jì)算資源、容錯(cuò)成 本等);后在已知信息的基礎(chǔ)上,選擇已有的算法或提出新的算法,在滿足資源限制的情況 下解決問(wèn)題。因此,可以說(shuō)一個(gè)不懂算法的菜鳥程序員是無(wú)法獨(dú)立、自主地解決具體工 程問(wèn)題的,也很難寫出邏輯嚴(yán)密、簡(jiǎn)化的高質(zhì)量代碼。
一名優(yōu)秀的計(jì)算機(jī)科學(xué)領(lǐng)域的工程師或科學(xué)家一定對(duì)經(jīng)典算法思想有深入的理解并能夠 將這些算法靈活應(yīng)用于解決實(shí)際問(wèn)題的過(guò)程中。目前,很多 IT 公司都會(huì)考查應(yīng)聘者的算 法功底和邏輯思維能力,因?yàn)樗惴üΦ咨詈竦膽?yīng)聘者,往往可以使項(xiàng)目的設(shè)計(jì)模式格外優(yōu)化, 程序邏輯也更為嚴(yán)密清晰。IT 公司的專家和達(dá)人都對(duì)算法有很深的造詣,同時(shí),項(xiàng) 目經(jīng)理也必須具備超強(qiáng)的邏輯思維能力。
對(duì)于所有即將邁入職場(chǎng)的計(jì)算機(jī)科學(xué)相關(guān)領(lǐng)域的學(xué)生而言,應(yīng)該都希望自己以后能夠在 職場(chǎng)中逐漸成長(zhǎng)為所在細(xì)分領(lǐng)域的優(yōu)秀人才,具備出色完成各類任務(wù)、解決各類問(wèn)題的能力, 算法可以說(shuō)是解決這些問(wèn)題的關(guān)鍵,而程序語(yǔ)言只是一個(gè)外殼。算法的功底與一個(gè)計(jì)算機(jī)科 學(xué)工程師的水平上限關(guān)系密切。所以,如果你想從事計(jì)算機(jī)科學(xué)相關(guān)工作,那么就應(yīng)當(dāng)認(rèn)真 地培養(yǎng)自己的邏輯思維,從而提高算法功底!
本書的所有作者以及團(tuán)隊(duì)均在計(jì)算機(jī)科學(xué)領(lǐng)域有著多年的算法學(xué)習(xí)經(jīng)歷和IT領(lǐng)域工作經(jīng) 驗(yàn),對(duì)算法有著較為深入的開發(fā)與實(shí)踐。本書是在所有作者(包括未出現(xiàn)在作者名單中的幕 后奉獻(xiàn)者)鉆研算法的基礎(chǔ)上,經(jīng)過(guò)長(zhǎng)期的應(yīng)用總結(jié)而完成的,并用言簡(jiǎn)意賅的語(yǔ)言將這些 算法問(wèn)題的答案展現(xiàn)出來(lái)。
本書特色
當(dāng)前,已出版的算法書籍不計(jì)其數(shù),從經(jīng)典的《算法導(dǎo)論》到針對(duì)具體的細(xì)分領(lǐng)域(例 Python 算法從菜鳥到達(dá)人 IV 如文本處理、神經(jīng)網(wǎng)絡(luò)等)相關(guān)算法的書籍,每一本都有自己的側(cè)重點(diǎn)與特色。本書的特色 主要體現(xiàn)在以下幾方面:
1)強(qiáng)調(diào)算法基礎(chǔ),理論與應(yīng)用并重。
2)包含大量實(shí)際應(yīng)用中的算法真題。
3)本書以 Python 語(yǔ)言實(shí)現(xiàn)。雖然 Python 中沒(méi)有指針的概念(只有引用),為了便于理解, 書中很多地方還是使用了指針,可以認(rèn)為其等價(jià)于引用。
4)本書配有核心知識(shí)點(diǎn)講解視頻(視頻制作由劉玖樽和田思怡完成),講解內(nèi)容和程序 代碼經(jīng)多次校審和驗(yàn)證(由李海洋、劉玖樽、熊良成和田思怡完成)。
讀者對(duì)象
1)計(jì)算機(jī)領(lǐng)域程序員及工程師。
2)計(jì)算機(jī)科學(xué)相關(guān)領(lǐng)域本科生及研究生。
3)其他算法愛(ài)好者(對(duì)算法感興趣的高中生、IT 領(lǐng)域產(chǎn)品經(jīng)理等)。
我們的目標(biāo)是將本書打造成廣大IT從業(yè)者和程序開發(fā)人員學(xué)習(xí)和提升算法能力的高效學(xué) 習(xí)材料,同時(shí)也可以作為科研院所及企業(yè)的工程師參考的一本技術(shù)性書籍,不論你是菜鳥 還是達(dá)人,閱讀本書都將受益匪淺,可以有效提升解決實(shí)際編程問(wèn)題的能力。
本書內(nèi)容
本書共 16 章,分為以下四大部分。
部分(算法基礎(chǔ),第 1、2 章) 這一部分將引導(dǎo)讀者理清算法在計(jì)算機(jī)系統(tǒng)中的作用以及偽代碼寫法的約定等,不僅給 出了算法的定義,簡(jiǎn)單地介紹了算法的表達(dá)方式,同時(shí)引導(dǎo)讀者思考算法的設(shè)計(jì)和分析問(wèn)題, 本書后面的內(nèi)容都是建立在這些基礎(chǔ)之上的。
第二部分(經(jīng)典算法思想,第 3~7 章) 算法設(shè)計(jì)有很多思想,但是歸納起來(lái),算法設(shè)計(jì)中有五種思想使用為廣泛,它們分別 是遞歸與分治法、動(dòng)態(tài)規(guī)劃算法、貪心算法、回溯法與分支界限法。這一部分逐一介紹了這 些經(jīng)典算法思想的具體思路以及利用這些算法思想可以解決的具體問(wèn)題。
第三部分(重要數(shù)據(jù)結(jié)構(gòu),第 8~13 章) 談到算法的時(shí)候,數(shù)據(jù)結(jié)構(gòu)這個(gè)詞大概率也不會(huì)缺席。數(shù)據(jù)結(jié)構(gòu)也是所有計(jì)算機(jī)專業(yè)學(xué) 生必修的一門課程。這一部分主要講解了一些重要數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)以及應(yīng)用范圍。對(duì)于 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)較好的讀者,可以跳過(guò)本部分,并不會(huì)影響閱讀本書其余章節(jié)。
第四部分(常用算法,第 14~16 章) 這一部分重點(diǎn)介紹了日常學(xué)習(xí)或工作中常用的一些算法,包括常用的排序算法、查找 算法以及字符串匹配算法。這些算法并不復(fù)雜,但是都有著非常高的使用頻率,掌握它們將 快速提升讀者對(duì)算法的應(yīng)用和實(shí)踐能力。
反饋溝通
歡迎讀者朋友在閱讀本書過(guò)程中給予反饋意見(jiàn),以利于本書的進(jìn)一步完善與提升。反饋 意見(jiàn)請(qǐng)發(fā)送至 yuancoder@foxmail.com,我們將盡力解決問(wèn)題。
本書全體作者
前言
部分 算法基礎(chǔ)/1
第 1 章 算法綜述/2
1.1 算法在計(jì)算機(jī)系統(tǒng)中的作用/2
1.1.1 算法的定義/2
1.1.2 算法的地位/2
1.1.3 一個(gè)簡(jiǎn)單的算法/3
1.2 偽代碼的約定/4
第 2 章 算法分析/6
2.1 精確效率分析/6
2.2 漸進(jìn)效率分析/8
2.2.1 漸進(jìn)記號(hào)/9
2.2.2 漸進(jìn)記號(hào)的應(yīng)用/10
2.3 遞歸式求解/15
第二部分 經(jīng)典算法思想/17
第 3 章 遞歸與分治法/18
3.1 遞歸的概念/18
3.2 分治法/22
3.3 分治法的應(yīng)用/25
3.4 達(dá)人修煉真題/26
第 4 章 動(dòng)態(tài)規(guī)劃算法/50
4.1 動(dòng)態(tài)規(guī)劃基礎(chǔ)/50
4.1.1 動(dòng)態(tài)規(guī)劃基本思想/50
4.1.2 動(dòng)態(tài)規(guī)劃算法舉例長(zhǎng)公共子序列/50
4.2 動(dòng)態(tài)規(guī)劃算法分析/53
4.2.1 子結(jié)構(gòu)/54
Python 算法從菜鳥到達(dá)人
VI
4.2.2 重疊子問(wèn)題/54
4.3 動(dòng)態(tài)規(guī)劃算法的應(yīng)用/55
4.3.1 0-1 背包問(wèn)題/55
4.3.2 石子歸并/56
4.3.3 常用動(dòng)態(tài)規(guī)劃類問(wèn)題/59
4.4 達(dá)人修煉真題/60
第 5 章 貪心算法/79
5.1 貪心算法基礎(chǔ)/79
5.1.1 貪心算法基本思想/79
5.1.2 貪心算法舉例裝載問(wèn)題/79
5.2 貪心算法的分析/80
5.3 貪心算法的應(yīng)用/81
5.3.1 普通背包問(wèn)題/81
5.3.2 活動(dòng)安排問(wèn)題/83
5.3.3 紀(jì)念品分組/85
5.4 達(dá)人修煉真題/87
第 6 章 回溯法/91
6.1 回溯法基本概念與算法框架/91
6.1.1 基本思路/91
6.1.2 回溯法的實(shí)現(xiàn)/93
6.2 回溯法的應(yīng)用/94
6.2.1 0-1 背包問(wèn)題/94
6.2.2 八皇后問(wèn)題/96
6.2.3 一摞烙餅的排序/97
6.3 達(dá)人修煉真題/100
第 7 章 分支界限法/103
7.1 分支界限法概念與算法框架/103
7.1.1 分支界限法基本思想/103
7.1.2 算法框架與分析/104
7.1.3 一個(gè)簡(jiǎn)單的例子(0-1 背包問(wèn)題)/106
7.2 分支界限法的應(yīng)用/108
7.2.1 TSP 問(wèn)題/108
7.2.2 多段圖的短路徑問(wèn)題/111
7.2.3 任務(wù)分配問(wèn)題/113
7.3 達(dá)人修煉真題/116
第三部分 重要數(shù)據(jù)結(jié)構(gòu)/121
第 8 章 棧與隊(duì)列/122
8.1 棧/122
目錄
VII
8.2 隊(duì)列/124
8.3 達(dá)人修煉真題/128
第 9 章 鏈表/142
9.1 鏈表概述/142
9.2 鏈表的操作/143
9.3 達(dá)人修煉真題/145
第 10 章 樹與二叉樹/152
10.1 樹的概念與定義/152
10.1.1 基本概念/152
10.1.2 樹的表示/153
10.2 二叉樹/154
10.2.1 基本概念/154
10.2.2 二叉樹的存儲(chǔ)結(jié)構(gòu)/155
10.2.3 遍歷二叉樹和線索二叉樹/156
10.3 樹、二叉樹和森林之間的關(guān)系/159
10.4 達(dá)人修煉真題/164
第 11 章 哈希表/170
11.1 哈希表概述/170
11.2 哈希表的應(yīng)用/173
11.3 達(dá)人修煉真題/175
第 12 章 并查集/185
12.1 并查集基本思想/185
12.1.1 并查集概念/186
12.1.2 并查集的實(shí)現(xiàn)/186
12.1.3 帶權(quán)并查集/189
12.2 并查集的應(yīng)用/191
12.2.1 食物鏈/191
12.2.2 Kruskal 小生成樹算法/194
12.3 達(dá)人修煉真題/195
第 13 章 位圖/199
13.1 位圖基本概念/199
13.2 位圖法的應(yīng)用/203
13.2.1 位運(yùn)算常見(jiàn)應(yīng)用/204
13.2.2 位圖法在大數(shù)據(jù)處理中的應(yīng)用/207
13.3 達(dá)人修煉真題/209
第四部分 常用算法/213
第 14 章 排序算法/214
14.1 插入排序/214
Python 算法從菜鳥到達(dá)人
VIII
14.2 選擇排序/218
14.3 交換排序/222
14.4 歸并排序/226
14.5 桶排序/基數(shù)排序/228
14.6 達(dá)人修煉真題/231
第 15 章 查找算法/235
15.1 基本概念/235
15.2 靜態(tài)查找/236
15.3 動(dòng)態(tài)查找/239
15.4 哈希查找/244
15.5 達(dá)人修煉真題/244
第 16 章 字符串匹配算法/250
16.1 簡(jiǎn)單字符串匹配/250
16.2 KMP 算法/251
16.3 BM 算法/254
16.4 SUNDAY 算法/255
16.5 達(dá)人修煉真題/255
附錄/263