算法设计与分析(Python).pdf

21世纪高等学校计算机专业实用规划教材算法设计与分析(Python)Design and Analysis of Algorithm Using Python程振波李曲王春平编著清华大学出版社北京内容简介本书介绍了算法设计与分析的基本技巧，主要包括递归、分治、动态规划、贪心和随机等算法，以及利用这些算法求解计算问题的时间复杂度分析等内容。通过诸多有趣的实例，向读者介绍了算法设计的思想，以便读者能形成算法思维的固定模式去解决问题。在介绍每一类算法范式以及分析算法复杂度时，都力求建立直观的思维过程，而摒弃过深的数学证明。书中所有算法均采用Pytho语言描述，读者能从中学习到许多算法实现的技巧，从而提高编写程序的能力。本书可作为高等学校计算机专业大一、大二或者学习过程序设计的非计算机专业学生的算法设计与分析教材。本书封面贴有清华大学出版社防伪标签，无标签者不得销售。版权所有，侵权必究。侵权举报电话：010-6278298913701121933图书在版编目(CIP)数据算法设计与分析：Pythor/程振波，李曲，王春平编著.一北京：清华大学出版社，2018(21世纪高等学校计算机专业实用规划教材)ISBN978-7-302-47748-8I.算.程李王.电子计算机一算法设计一高等学校一教材电子计算机一算法分析一高等学校一教材V.TP301.6中国版本图书馆CP数据核字(2017)第166911号责任编辑：梁颖柴文强封面设计：何凤霞责任校对：焦丽丽责任印制：李红英出版发行：清华大学出版社网t址：http:/,htp:/地址：北京清华大学学研大厦A座邮编：100084社总机：010-62770175邮购：010-62786544投稿与读者服务：010-62776969，c-质量反馈：010-62772015，课件下载：http:/,010-62795954印刷者：北京富博印制有限公司装订者：北京市密云县京文制本装订厂经销：全国新华书店本：185mm260mm印张：15字数：368千字版次：2018年1月第1版印次：2018年1月第1次印刷印数：12000定价：39.00元产品编号：069618-01前言“算法设计与分析”是计算机专业非常重要的一门基础课程，它不仅是诸多计算机专业课程的基础，也是许多信息科技类公司招聘程序员时，笔试与面试重点考核的内容。算法设计与分析己经有了诸多经典的著作，比如美国麻省理工学院(MT)几位教授合著的算法导论等。然而，这些经典著作当作教材使用时，都会存在对内容进行适当裁剪，以便更适合48或者32个学时教学的问题。我们写本书的目的就是对初等算法内容进行合理的编排，让初学者能很快地掌握解决计算问题的常用算法，以及分析算法效率的方法。本书算法均采用Python语言进行描述，Python是一类解释性语言，其语法简单直观，有一定程序设计基础的学生可以很快入门。Python语法简单并不意味着功能弱，它在科学计算、Wb应用等诸多领域都有着广泛的应用。国外知名的高校，如麻省理工学院，也在算法设计课中采用Python语言描述。与采用伪代码描述算法的书比较而言，采用Python描述算法能给读者直接的运算结果，从而可以使读者更易于揣摩算法实现的技巧。计算机算法不仅涉及诸多理论，还有各种技术细节。比如介绍随机算法时，有些执行时间的分析就需要较多的概率论知识：而算法实现技术细节则不仅关注如何存储数据，甚至对执行算法的硬件环境也会考虑在内。本书的内容安排则介于两者之间，在数学分析与实现之间期望取得合理的平衡。首先，在分析算法效率时尽量避免过深的数学证明，但关键步骤依然会给出直观的解释。其次，在实现算法时本书尽量利用Python已有的数据结构和库函数，从而简化算法实现的技术难度。如果将要处理的数据、问题看作是食材，那么算法就是将食材“转化”成各种令人垂涎的美食的过程。中国菜肴到处都是充满想象力的转化，将原本普通的食材（如大豆和糯米等)转化为营养和美味的食物（豆腐、酒酿和酱料等）。本书的主线就是转化，它不仅有问题的转化，也有方法的转化（如图1所示）。通过问题的转化将问题“化繁为简”，通过方法的转化以便融会贯通各种算法设计的技巧。本书主要内容由于计算机已经成为现代科技、生活不可缺少的工具。因此，解决计算问题的算法涉及的内容可以说包罗万象，从简单的排序和查找到复杂的语音识别、文字翻译，甚至见参考文献1