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