前言

虽然自己讲授“算法设计与分析”课程很多年了，但是一直没有想过写一本书。去年，应清华大学出版社邀约，萌生了写一本书的想法。为什么讲了这么多年课，直到现在才有写书的想法呢？一个主要原因就是我越来越强烈地感觉到：学生虽然能够理解课堂讲授的理论知识，但是在解决实际问题时，他们似乎难以下手。

为什么会有这种现象呢？我仔细思考之后，找到了一个关键的问题。“算法设计与分析”这门课程的理论是比较抽象的，虽然不难理解，但它就像天上的云一样，不容易落地。那么,如何能让理论知识落地，指引读者去解决实际问题呢？这就好像踢足球，如果只是听别人讲如何踢足球，一般人都能听懂，但是听懂了并不代表自己会了，如果要会踢足球，还需要大量的练习。

对于“算法设计与分析”这门课程而言，掌握理论知识之后也需要大量练习，那么怎样练习呢？就是在实际案例中去应用。但是在应用时需要注意，目标不能仅仅是解决某个问题，而要关注解决这个问题背后的思想方法。举一个简单的例子，假设我们要设计一个效率是O(logn)的算法求xn的值，其中x和n都是已知的。如果仅从解决问题的角度，可以利用n的二进制表达逐位处理，也可以达到O(logn)的效率。但是如果读者想要练习算法设计思想，就要分析这个问题的结构，也就是xn=xn/2×xn/2，从这个结构可以看出，原问题xn和子问题xn/2是一样的，仅仅是问题的规模有所区别，这样就出现了分治法求解的算法设计思路了，即原问题被分解为两个子问题。如果定义函数F（n）=xn，然后简单地利用F（n）=F(n/2)×F(n/2)的思路写代码，就会导致效率达到O(n)，而不是O(logn)，这个分析过程可以利用递归算法效率分析的方法推导出。这时，我们就能发现这里的核心问题是子问题求解了两次，如果能求解一次子问题，就可以达到O(logn)的算法效率。这样，算法优化的思想就清晰了，我们可以把子问题的解F(n/2)存起来，并通过这个临时变量来计算F（n），而不是调用两次子问题求解，就可以提高算法效率。

上面这个简单的例子说明，算法设计与分析在实践的过程中，我们更需要关注的是如何分析问题的结构，原问题与子问题有什么关系？什么样的算法设计策略适合解决这个问题？又如何通过效率分析进一步优化算法？而不是仅仅关注如何得到这个问题的解。所以，我想在这本书里表达的一个思想就是，希望各位读者在每个案例中关注算法设计的思想如何体现的、算法设计的思路是怎样的。如果能从这些角度去理解书中提供的案例，可能会对各位读者更有帮助。

本书基于Thomas H.Cormen等编写的著名教材《算法导论》中的部分内容，介绍了算法设计的基本策略，例如分治法、贪心法、动态规划等，同时简单介绍了算法效率分析中的渐进效率和摊还分析方法。由于这些内容在原著中都有表述，本书尽量从通俗易懂的角度对算法思想进行了解释，同时增加了回溯法的算法设计方法。本书收集了各种算法设计的案例，并且致力于把这些案例实现的思想解释清楚，让读者在多个案例里不断练习，逐渐建立计算思维的思维方式，从而在遇到一个实际问题时，能有一个下手的思路，通过分析问题的结构去寻找求解问题的方法。

算法设计与分析实践案例解析前言写书实在是一个漫长而痛苦的过程，对于每个案例，我在梳理思路时同样感到吃力。然而，这也是一个快速提升的过程。由于本人能力有限，书中一些算法思想的表达只是个人的一些理解，难免有不准确的地方，请各位读者指正。

本书中的多个案例与求解算法来自GeeksforGeeks官网、斯坦福大学的CS166: Advanced Data Structures课程、杜克大学的CPS 230: Design and Analysis of Algorithms课程、麻省理工学院公开课资源的Advanced Algorithms课程的部分课件，在此表示衷心感谢。

本书由“深圳大学教材建设项目”资助。在本书的撰写过程中，两位参编老师李炎然、吴定明做了很多工作。其中，李炎然老师提供了大量的动态规划案例，这些案例都是李老师自己设计的。吴定明老师在图论方面提供了很多好的资料，拓宽了本书的案例深度和广度。深圳大学计算机与软件学院2021级学生曹婉楠,2022级学生陈恺斌、陈碧晗、黄德海、黄雨欣参与了本书的资料整理，在此表示深深的感谢。同时，感谢深圳大学计算机与软件学院算法设计与分析课程组全体老师的支持！

杨烜

2025年7月