书名：Python算法设计与分析pdf/doc/txt格式电子书下载

推荐语：Python数据结构与算法入门基础教程涵盖主流算法经典算法问题的解决、图像问题的解决等内容是一本即学即用的图解算法书

作者：王硕、

出版社：人民邮电出版社

出版时间：2020-05-01

书籍编号：30616430

ISBN：9787115529008

正文语种：中文

字数：288848

版次：1

所属分类：计算机-程序设计

图书在版编目（CIP）数据

Python算法设计与分析/王硕等编著.--北京：人民邮电出版社，2020.5

ISBN　978-7-115-52900-8

Ⅰ.①P…　Ⅱ.①王…　Ⅲ.①软件工具—程序设计　Ⅳ.①TP311.561

中国版本图书馆CIP数据核字（2019）第269407号

♦编著　王硕　董文馨　张舒行　张洁　李秉伦

责任编辑　刘博

责任印制　王郁　陈犇

♦人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164　　电子邮件　315@ptpress.com.cn

网址　https://www.ptpress.com.cn

北京鑫正大印刷有限公司印刷

♦开本：787×1092　1/16

印张：15.25　　2020年5月第1版

字数：438千字　　2020年5月北京第1次印刷

定价：49.80元

读者服务热线：(010)81055256　印装质量热线：(010)81055316

反盗版热线：(010)81055315

广告经营许可证：京东工商广登字20170147号

内容提要

本书内容包括算法初步、排序算法、查找、双指针问题、哈希算法、深度优先搜索算法、广度优先搜索算法、回溯算法、动态规划、贪心算法、分治算法、并查集、最短路径算法和数论算法等常见算法。每个算法都做了深入的讲解，同时通过实例介绍了如何应用这些算法。书中算法都以Python语言进行描述。

本书的特色在于讲解知识点的同时，辅以大量生动的例子，以更好地帮助读者深刻理解算法的原理。读者可以通过本书快速了解并掌握这些算法。

本书适合有Python语言基础，了解基本数据结构知识，渴望深入学习算法的读者阅读。

前言

为什么要写这本书

本书是讲解算法的教材。为帮助大家理解，书中使用了大量的代码和图表。

学习算法不是一件容易的事情，再加上复杂的场景和数学理论，会让算法的学习曲线更陡。因此，本书尽量使用通俗易懂的语言描述。同时，我们选择了 Python 这门简单易懂的语言作为本书的编程语言。对于初学编程的人来说，Python 可以缩短学习编程语言的时间和降低学习编程的难度，使得初学者可以更加关注算法本身的魅力，而不是拘泥于复杂的语法结构。

随着编程学习的深入，大家自然会发现算法才是编程的核心，这也是为什么像 Google、Facebook、阿里巴巴等这类大公司在面试中主要会考查算法的原因。并且，很多算法的智慧都可以应用到人们的生活中去，因此，算法的知识不仅对计算机专业的人有用，大家都应有所了解。

算法离不开数据结构，为此，本书选取了几大经典算法和数据结构进行讲解。而算法和数据结构的学习也能充分锻炼读者的编程和解决问题能力。

本书有何特色

1.涵盖核心算法知识点

本书涵盖排序算法、查找、双指针问题、哈希算法、深度优先搜索算法、广度优先搜索算法、回溯算法、动态规划、贪心算法、分治算法、并查集、最短路径算法和数论算法共13个常见算法，帮助读者全面掌握核心算法的知识点。

2.以Python语言为载体，降低学习难度

抛弃其他复杂的编程语言，本书采用简单的编程语言 Python 作为算法的载体，降低学习算法的难度。

3.选择经典算法的经典问题，有较高的通用性

本书在简单介绍算法基础以后，选择了13个经典算法，重点讲解算法原理，并选择丰富、经典问题进行有针对性的练习和讲解。

4.提供完善的技术支持和售后服务

由于笔者水平有限，时间仓促，书中难免存在疏漏和不足之处，敬请读者批评指正。欢迎发送邮件至邮箱：317977682@qq.com。读者在阅读本书的过程中有任何疑问，都可以通过该邮箱获得帮助。

本书内容及知识体系

第1章 算法初步

本章详细介绍了算法的本质、意义和应用。在了解算法本质的同时，要掌握时间复杂度和空间复杂度，以判断一个算法的效率和实用性。时间复杂度和空间复杂度是衡量一个算法优劣的标尺。

第2章 排序算法

本章讲解了8种常用排序算法，重点在于理解各个排序算法的核心思想，并把它们应用到其他算法中。

第3章 查找

本章讲解了顺序查找、二分查找及树中的查找这三大类查找方法，其中详细讲解了二叉搜索树的操作以及AVL树的平衡方法，并给出了部分示例程序。合理地使用二分查找、二叉搜索树和平衡树，可以使查找效率大大提高。

第4章 双指针问题

“指针”是编程语言中的一个对象，它存储着一个内存空间的地址，计算机可以通过这个地址找到变量的值。也就是说，这个特定的地址指向这个特定的值。指针最大的优点在于它可以有效利用零碎的内存空间。双指针问题通过两个指针辅助求解。

第5章 哈希算法

哈希算法也是一种查找算法，应该说哈希算法是最快的查找算法。使用哈希算法解决查找问题，不仅效率高、代码少，而且容易理解。读者在遇到查询问题能用哈希算法的时候，一定要记得使用哈希算法。

第6章 深度优先搜索算法

深度优先搜索算法是经典的图论算法，深度优先搜索算法的搜索逻辑和它的名字一样，只要有可能，就尽量深入搜索，直到找到答案，或者尝试了所有可能后确定没有解。

第7章 广度优先搜索算法

广度优先搜索算法与深度优先搜索算法类似，也是查询的方法之一，它也是从某个状态出发查询可以到达的所有状态。但不同于深度优先搜索算法，广度优先搜索算法总是先去查询距离初始状态最近的状态，而不是一直向最深处查询结果。

第8章 回溯算法

回溯算法和“暴力”线性搜索法的相似点在于两者在最坏的情况下都会尝试所有的可能，导致时间复杂度为指数级别。与“暴力”线性搜索法相比，回溯算法是一种有条理的、最优化的搜索技术。回溯算法会通过提前放弃一些已知不可能的选择，加快速度。

第9章 动态规划

动态规划是一种算法设计技术，通常用于求解最优化问题。它和分治算法很类似，都是通过划分并求解子问题来获得原问题的解。但与分治算法将子问题递归求解不同，动态规划旨在剔除递归中的重叠子问题，对每个子问题只求解一次，从而可以极大地节省算力资源。

第10章 贪心算法

算法求解虽比一般的递归求解资源消耗小，但是我们通常还是要将每个子问题都求解出来。对于很多最优化问题而言，我们还能不能简化呢？答案当然是肯定的，这就需要使用贪心算法。

第11章 分治算法

分治算法的主要思想是将原问题分成若干个子问题，解决这些子问题再最终合并出原问题的答案。在计算过程中，子问题会被递归地分解成更小的子问题，直到子问题满足边界条件。最后，算法会层层递归回原问题的答案。

第12章 并查集

并查集是解决图的遍历问题的一种优化数据结构，在元素的划分和查找问题中，可以有效降低解决问题时的时间复杂度。

第13章 最短路径算法

从手机导航到人工智能，最短路径问题在人们生活中无处不在。在之前介绍了关于图的基本知识，包括权重、路径、有向图及无向图。这一章则介绍四个解决最短路径问题的算法。

第14章 数论算法

本章详细介绍了欧几里得算法、扩展欧几里得算法、中国余数定理以及两个素性检验算法：费马素性检验与米勒-拉宾素性检验。数论中的算法在计算机领域可能不像排列或查找那么常见，但是它们在密码学中十分重要。另外，除米勒-拉宾素性检验，这些算法都历史悠久，希望读者在学习的同时也感受一下古人的智慧。

适合阅读本书的读者

● 需要全面学习算法的人员。

● 对编程算法感兴趣的人员。

● 希望提高算法水平的程序员。

● 开设相关课程的大专院校师生。

第1章 算法初步

1.1 什么是算法

1.1.1 算法的定义

对算法的解释，从古至今定义是不唯一的。本书给出的算法的定义是：一系列用来解决单个或多个问题，或有执行计算功能的命令的集合。而联系上输入与输出，算法就是将输入转换为输出的一系列计算步骤的集合。生动地讲，可以把一个程序比作一道菜。如图1-1所示，做菜的原材料就是输入，做出来的成品即为输出；而算法，就是做菜过程中的复杂步骤。

图1-1 算法和做菜步骤的对比

算法的本质其实是数学的理论与推导。在还没有发明求和公式之前，如何求出1+2+3+…+n？逐个数求和虽能算出答案，但终究过于繁杂，如果n=10000呢？但反观求和公式，无论n取多大的值，计算的步骤和繁琐程度基本不会增加。这就是算法存在的意义。人类在解决复杂问题时所采用的一系列特定的方法，即为算法。

1.1.2 算法与程序的区别

算法和程序的定义有很大交集。通常来说，（计算机）程序指一组计算机能识别和执行，并有一定功能的指令。后者的定义似乎和算法很相似，但两者最大的区别在于程序是以计算机能够理解的各式各样的编程语言编写而成的，而算法是可以通过编程语言、图绘、口述等人能够理解的方式来描述的，不一定局限于编程语言的诠释，如图 1-2 所示。不过，算法和程序之间并没有明确的分界线，理解二者的意思就足够了。

图1-2 算法和程序的关系

刚才曾提过，算法是一种以数学为本质的计算方法。然而作为方法，则必有正确（可行）、不正确（不可行），高效、低效之分。若一个算法对每一个恰当的输入（严格地符合问题的前提条件，且可以为空）都以正确的输出终止程序，则可以称该算法是正确的，并正确地解决了给定的问题。若算法以不正确的输出而终止程序，或根本无法终止程序（如程序陷入死循环），则这个算法是不正确的。

但显而易见，不是所有的算法都可以通过输入和输出的正确和不正确而简单地分为两大类。譬如人们要预测未来特定事件发生概率，而这种问题无法用结果来检验解决方法正确与否。因此，算法的正确性的检验也可以回溯到其本质，就是数学的检验，也就是说用数学来证明算法的正确性或可行性。

对算法至关重要的不只有其正确性，还有它的效率。人类至今的发展，提高最迅速的可以说就是计算的效率了。从原始人的结绳计数，到现在的超级计算机，计算能力的提升不是区区几个数量级能说明的。但很不幸，当今计算机的运算速度不是无限快，存储器也不是免费的，所以如何高效地利用好有限的时间和空间就是算法存在的意义。有趣的是，求解相同问题而设计的不同算法在效率方面通常有显著的差异，而这些算法效率上的差异要比在硬件或者软件效率上的差异大得多。

回到 1+2+3+…+n这个求和问题中。一定程度上说，逐个数相加也可以被看作一种解决求和问题的算法，一种简单、低效的算法。相反，求和公式则是一种较复杂、高效的算法。但如何来评判一个算法是否高效？时间复杂度和空间复杂度就是很好的丈量工具。

1.2 时间复杂度

1.2.1 运行时间和程序复杂程度的关系

一个高级语言编写的程序的运行时间主要取决于三个因素：算法的方法、策略（复杂度），问题的输入规模，计算机执行指令的速度。问题的输入规模是客观的、限定的，要加快算法的效率绝不能影响问题的输入规模；计算机执行指令的速度虽然可以有显著提升，但其发展时间较长，也不是确定的，总不能终日盼着计算机性能的提升。所以提高算法的效率，减少程序运行时间，改进算法的策略是至关重要的。

在讲解时间复杂度之前，需先引入一个概念——时间频度。时间频度代表一个算法中的语句执行次数，其又称为语句频度。显然，时间频度越高的算法运行的时间越长。

时间频度也可被记为T(n)，其中n为问题的规模，即输入值的规模。当n不断变化时，时间频度T(n)也会不断变化。为了探究自变量n和因变量T(n)变化的关系，我们引入时间复杂度这个概念。不同于时间频度，时间复杂度考察的是当输入规模趋于无穷时，时间频度的渐近情况。时间复杂度的具体定义为：若有某个辅助函数f(n)，使得的极限值（当n趋近于无穷大时）为不等于 0的常数，则称f(n)是T(n)的同数量级函数。记作

T (n)=O(f(n))

O(f(n))称为算法的渐进时间复杂度，简称时间复杂度。在数学上，O符号（Landau符号）用来描述一个函数数量级的渐近上界。因为O符号表示法并不是真实代表算法的执行时间，而是表示代码执行时间的增长变化趋势。

1.2.2 时间复杂度是渐进的

如果我们将算法中的一次计算记为1，那么如果有n个输入值，算法对每一个输入值做一次运算，那么整个算法的运算量即为n。这个时候，我们就可以说，这是一个时间复杂度为O( )n 的算法。同理，如果仍有n个输入值，但算法对每一个输入值做一次运算，这个操作需要再重复n次，那么整个算法的运算量即为n· n=n2，时间复杂度为O( n2 )。这时如果对每一个输入值做一次运算，这个操作需要重复n+1次，算法运算量变为：

n i(n+1)=n 2+n

这

....