前言
雖然自己講授“算法設(shè)計(jì)與分析”課程很多年了，但是一直沒有想過寫一本書。去年，應(yīng)清華大學(xué)出版社邀約，萌生了寫一本書的想法。為什么講了這么多年課，直到現(xiàn)在才有寫書的想法呢？一個(gè)主要原因就是我越來越強(qiáng)烈地感覺到：學(xué)生雖然能夠理解課堂講授的理論知識(shí)，但是在解決實(shí)際問題時(shí)，他們似乎難以下手。
為什么會(huì)有這種現(xiàn)象呢？我仔細(xì)思考之后，找到了一個(gè)關(guān)鍵的問題。“算法設(shè)計(jì)與分析”這門課程的理論是比較抽象的，雖然不難理解，但它就像天上的云一樣，不容易落地。那么,如何能讓理論知識(shí)落地，指引讀者去解決實(shí)際問題呢？這就好像踢足球，如果只是聽別人講如何踢足球，一般人都能聽懂，但是聽懂了并不代表自己會(huì)了，如果要會(huì)踢足球，還需要大量的練習(xí)。
對于“算法設(shè)計(jì)與分析”這門課程而言，掌握理論知識(shí)之后也需要大量練習(xí)，那么怎樣練習(xí)呢？就是在實(shí)際案例中去應(yīng)用。但是在應(yīng)用時(shí)需要注意，目標(biāo)不能僅僅是解決某個(gè)問題，而要關(guān)注解決這個(gè)問題背后的思想方法。舉一個(gè)簡單的例子，假設(shè)我們要設(shè)計(jì)一個(gè)效率是O(logn)的算法求xn的值，其中x和n都是已知的。如果僅從解決問題的角度，可以利用n的二進(jìn)制表達(dá)逐位處理，也可以達(dá)到O(logn)的效率。但是如果讀者想要練習(xí)算法設(shè)計(jì)思想，就要分析這個(gè)問題的結(jié)構(gòu)，也就是xn=xn/2×xn/2，從這個(gè)結(jié)構(gòu)可以看出，原問題xn和子問題xn/2是一樣的，僅僅是問題的規(guī)模有所區(qū)別，這樣就出現(xiàn)了分治法求解的算法設(shè)計(jì)思路了，即原問題被分解為兩個(gè)子問題。如果定義函數(shù)F（n）=xn，然后簡單地利用F（n）=F(n/2)×F(n/2)的思路寫代碼，就會(huì)導(dǎo)致效率達(dá)到O(n)，而不是O(logn)，這個(gè)分析過程可以利用遞歸算法效率分析的方法推導(dǎo)出。這時(shí)，我們就能發(fā)現(xiàn)這里的核心問題是子問題求解了兩次，如果能求解一次子問題，就可以達(dá)到O(logn)的算法效率。這樣，算法優(yōu)化的思想就清晰了，我們可以把子問題的解F(n/2)存起來，并通過這個(gè)臨時(shí)變量來計(jì)算F（n），而不是調(diào)用兩次子問題求解，就可以提高算法效率。
上面這個(gè)簡單的例子說明，算法設(shè)計(jì)與分析在實(shí)踐的過程中，我們更需要關(guān)注的是如何分析問題的結(jié)構(gòu)，原問題與子問題有什么關(guān)系？什么樣的算法設(shè)計(jì)策略適合解決這個(gè)問題？又如何通過效率分析進(jìn)一步優(yōu)化算法？而不是僅僅關(guān)注如何得到這個(gè)問題的解。所以，我想在這本書里表達(dá)的一個(gè)思想就是，希望各位讀者在每個(gè)案例中關(guān)注算法設(shè)計(jì)的思想如何體現(xiàn)的、算法設(shè)計(jì)的思路是怎樣的。如果能從這些角度去理解書中提供的案例，可能會(huì)對各位讀者更有幫助。
本書基于Thomas H.Cormen等編寫的著名教材《算法導(dǎo)論》中的部分內(nèi)容，介紹了算法設(shè)計(jì)的基本策略，例如分治法、貪心法、動(dòng)態(tài)規(guī)劃等，同時(shí)簡單介紹了算法效率分析中的漸進(jìn)效率和攤還分析方法。由于這些內(nèi)容在原著中都有表述，本書盡量從通俗易懂的角度對算法思想進(jìn)行了解釋，同時(shí)增加了回溯法的算法設(shè)計(jì)方法。本書收集了各種算法設(shè)計(jì)的案例，并且致力于把這些案例實(shí)現(xiàn)的思想解釋清楚，讓讀者在多個(gè)案例里不斷練習(xí)，逐漸建立計(jì)算思維的思維方式，從而在遇到一個(gè)實(shí)際問題時(shí)，能有一個(gè)下手的思路，通過分析問題的結(jié)構(gòu)去尋找求解問題的方法。
算法設(shè)計(jì)與分析實(shí)踐案例解析前言寫書實(shí)在是一個(gè)漫長而痛苦的過程，對于每個(gè)案例，我在梳理思路時(shí)同樣感到吃力。然而，這也是一個(gè)快速提升的過程。由于本人能力有限，書中一些算法思想的表達(dá)只是個(gè)人的一些理解，難免有不準(zhǔn)確的地方，請各位讀者指正。
本書中的多個(gè)案例與求解算法來自GeeksforGeeks官網(wǎng)、斯坦福大學(xué)的CS166: Advanced Data Structures課程、杜克大學(xué)的CPS 230: Design and Analysis of Algorithms課程、麻省理工學(xué)院公開課資源的Advanced Algorithms課程的部分課件，在此表示衷心感謝。
本書由“深圳大學(xué)教材建設(shè)項(xiàng)目”資助。在本書的撰寫過程中，兩位參編老師李炎然、吳定明做了很多工作。其中，李炎然老師提供了大量的動(dòng)態(tài)規(guī)劃案例，這些案例都是李老師自己設(shè)計(jì)的。吳定明老師在圖論方面提供了很多好的資料，拓寬了本書的案例深度和廣度。深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院2021級(jí)學(xué)生曹婉楠,2022級(jí)學(xué)生陳愷斌、陳碧晗、黃德海、黃雨欣參與了本書的資料整理，在此表示深深的感謝。同時(shí)，感謝深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院算法設(shè)計(jì)與分析課程組全體老師的支持！
楊烜
2025年7月