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