![计算机算法基础[按需印刷]](http://images.china-pub.com/ebook3765001-3770000/3768787/zcover.jpg)
（已有2条评价）基本信息
【插图】
内容简介
书籍
计算机书籍
《计算机算法基础》是作者20多年在国内外教学与科研实践的结晶，深入浅出地介绍计算机算法中涉及的基本理论和方法。主要内容包括算法复杂度的概念和表达、分治法、贪心法、动态规划、图的遍历技术、平扫线技术、回溯法、分支限界法、(((剪枝等。在讲述这些理论和方法的同时，介绍一系列重要问题的算法，包括排序问题、选择问题、最小支撑树问题、最短路径问题、网络流问题、二分图的匹配问题、字符串的匹配问题以及若干几何算法问题，并将这些问题的解法及所用技术紧密相连，有机地编排在一起。此外，本书还介绍了问题本身固有的计算复杂性的概念和NP完全问题的理论以及近似算法。
《计算机算法基础》讲解细腻、分析透彻，以探索解决问题的方式深入分析了大量案例，使读者能清晰触摸到作者的思维方法，并建立起自己独立思考的学习习惯。本书可以作为计算机科学等相关专业本科生、研究生的教材，也可供从事计算机算法设计与分析工作的教师与研究人员参考。
计算机书籍
《计算机算法基础》是作者20多年在国内外教学与科研实践的结晶，深入浅出地介绍计算机算法中涉及的基本理论和方法。主要内容包括算法复杂度的概念和表达、分治法、贪心法、动态规划、图的遍历技术、平扫线技术、回溯法、分支限界法、(((剪枝等。在讲述这些理论和方法的同时，介绍一系列重要问题的算法，包括排序问题、选择问题、最小支撑树问题、最短路径问题、网络流问题、二分图的匹配问题、字符串的匹配问题以及若干几何算法问题，并将这些问题的解法及所用技术紧密相连，有机地编排在一起。此外，本书还介绍了问题本身固有的计算复杂性的概念和NP完全问题的理论以及近似算法。
《计算机算法基础》讲解细腻、分析透彻，以探索解决问题的方式深入分析了大量案例，使读者能清晰触摸到作者的思维方法，并建立起自己独立思考的学习习惯。本书可以作为计算机科学等相关专业本科生、研究生的教材，也可供从事计算机算法设计与分析工作的教师与研究人员参考。
作译者
沈孝钧，美国密苏里大学堪萨斯分校计算机科学系教授，在美国20多年教授计算机算法、分布式算法、计算机体系结构、并行计算机体系结构、离散数学和计算机网络等课程，目前兼任中科院研究生院、东南大学客座教授，主讲计算机算法课程。曾在离散数学、几何算法、并行处理和计算机网络领域做过多年的研究，并发表过大约30篇杂志论文和30篇会议论文。目前主要研究方向是计算机网络，包括传感器网络中各种调度算法问题。
目录
《计算机算法基础》
前言
教学建议
第1章 概述 1
1.1 算法与数据结构及程序的关系 1
1.1.1 什么是算法 1
1.1.2 算法与数据结构的关系 1
1.1.3 算法与程序的关系 1
1.1.4 选择排序的例子 2
1.1.5 算法的伪码表示 2
1.2 算法复杂度分析 3
1.2.1 算法复杂度的度量 3
1.2.2 算法复杂度与输入数据规模的关系 3
1.2.3 输入数据规模的度量模型 4
1.2.4 算法复杂度分析中的两个简化假设 4
1.2.5 最好情况、最坏情况和平均情况的复杂度分析 5
1.3 函数增长渐近性态的比较 6
1.3.1 三种比较关系及O、Ω、Θ记号 6
1.3.2 表示算法复杂度的常用函数 6
1.4 算法复杂度与问题复杂度的关系 8
前言
教学建议
第1章 概述 1
1.1 算法与数据结构及程序的关系 1
1.1.1 什么是算法 1
1.1.2 算法与数据结构的关系 1
1.1.3 算法与程序的关系 1
1.1.4 选择排序的例子 2
1.1.5 算法的伪码表示 2
1.2 算法复杂度分析 3
1.2.1 算法复杂度的度量 3
1.2.2 算法复杂度与输入数据规模的关系 3
1.2.3 输入数据规模的度量模型 4
1.2.4 算法复杂度分析中的两个简化假设 4
1.2.5 最好情况、最坏情况和平均情况的复杂度分析 5
1.3 函数增长渐近性态的比较 6
1.3.1 三种比较关系及O、Ω、Θ记号 6
1.3.2 表示算法复杂度的常用函数 6
1.4 算法复杂度与问题复杂度的关系 8
前言
计算机算法是计算机科学的一个重要分支，是计算机专业的一门必修课。作者从事这门课的教学及相关研究工作二十余年，在走了不少弯路后逐渐领悟到算法的思维方法和设计技巧，积累了一些经验，希望通过书的形式让更多的读者一开始便得到正规的训练，为今后进一步深造奠定坚实的基础。即使是不再深造的学生，能正确地运用第一门算法课中的方法解决实际工作中的问题也是至关重要的。我们经常看到，有些学过算法的学生仍喜欢用自己习惯的复杂度高的方法来解决问题，这是还没真正入门的表现。这本书的主要目的就是使学生能养成自觉地运用所学方法去追求最好结果的良好习惯。
书是为学生而用，为读者而写。作者本着这一宗旨，以共同探索解决问题的方式来写作，使读者能触摸到作者的思维方法，并能建立起自己独立思考的学习习惯。培养独立思考和创新的欲望对从事算法工作的人来讲十分重要，没有哪一种具体的算法可以解决所有问题，也没有哪一本书是万能的，只有勤于思考的人才能最好地解决实际问题。
本书包含了任何算法书都会包含的基本内容，并进行了扩充，主要包括网络流、字符串匹配、计算几何算法、近似算法以及穷举搜索法等，并在附录中介绍了红黑树。每章后配有精心挑选的习题，其中相当一部分是作者在教学实践中设计的。打星号的章节和题目较难或较偏，供选择。全书的内容足够用于两个学期教学，经过适当地取舍，本书可用于高等院校计算机及相关专业高年级本科生、硕士生及博士生教材。
最后，作者要感谢启蒙导师朱宗正教授（已去世）、博士生导师C. L. Liu教授的指导和熏陶，感谢清华大学、南京理工大学、伊利诺大学香滨分校的培养和提供的优良学术环境，感谢密苏里大学提供的教学和研究机会，并感谢朋友和家人的鞭策和支持。
因作者水平有限，疏漏之处在所难免，欢迎读者批评指正。
沈孝钧
2013年3月20日
书是为学生而用，为读者而写。作者本着这一宗旨，以共同探索解决问题的方式来写作，使读者能触摸到作者的思维方法，并能建立起自己独立思考的学习习惯。培养独立思考和创新的欲望对从事算法工作的人来讲十分重要，没有哪一种具体的算法可以解决所有问题，也没有哪一本书是万能的，只有勤于思考的人才能最好地解决实际问题。
本书包含了任何算法书都会包含的基本内容，并进行了扩充，主要包括网络流、字符串匹配、计算几何算法、近似算法以及穷举搜索法等，并在附录中介绍了红黑树。每章后配有精心挑选的习题，其中相当一部分是作者在教学实践中设计的。打星号的章节和题目较难或较偏，供选择。全书的内容足够用于两个学期教学，经过适当地取舍，本书可用于高等院校计算机及相关专业高年级本科生、硕士生及博士生教材。
最后，作者要感谢启蒙导师朱宗正教授（已去世）、博士生导师C. L. Liu教授的指导和熏陶，感谢清华大学、南京理工大学、伊利诺大学香滨分校的培养和提供的优良学术环境，感谢密苏里大学提供的教学和研究机会，并感谢朋友和家人的鞭策和支持。
因作者水平有限，疏漏之处在所难免，欢迎读者批评指正。
沈孝钧
2013年3月20日
书摘
第1章 概 述
计算机算法的设计与分析，简称为计算机算法，是计算机科学领域中一个重要分支，它主要研究两方面问题：
1）如何分析一个给定算法的时间复杂度。
2）如何为给定的计算问题设计一个算法，使得它的复杂度最低。
通俗讲，这里的时间复杂度就是用多少时间，显然以上两个问题是紧密相连的。因实用价值不大，计算机算法课一般已不太讨论空间复杂度，即用多少存储单元的问题，本书也是这样。这一章，我们介绍算法的时间复杂度的基本概念以及分析时遵循的基本原则。
1.1 算法与数据结构及程序的关系
计算机算法课是数据结构课和程序设计课的后续课程。一个简单的问题是，学了数据结构课和程序设计课之后，为什么还要学算法？程序本身是算法吗？这一节逐步给出简单回答。在深入学习之后，读者自己会有更准确的理解和领悟。
1.1.1 什么是算法
简单地说，算法（algorithm）是为解决某一计算问题而设计的一个过程，其每一步必须能在计算机上实现并在有限时间内完成。广义地讲，一个用某一语言（比如C++ 或机器语言）编写的程序也可称为算法。但是，为了理论分析的严格性和方便，我们对算法的定义加了某些限制。经过下面的讨论，我们会了解是哪些限制及为什么要加这些限制。
1.1.2 算法与数据结构的关系
算法与数据结构是密不可分的，除极少数算法外，几乎所有算法都需要数据结构的支持，而且数据结构的优劣往往决定算法的好坏。数据结构把输入的数据及运算过程中产生的中间数据以某种方式组织起来以便于动态地寻找、更改、插入、删除等。没有一种数据结构是万能的，我们应根据问题和算法的需要选用和设计数据结构，而在讨论数据结构时也必定会讨论其适用的算法。所以，数据结构课程与算法课程的内容往往有很大重叠。但是，数据结构课程需要解释其在计算机上的具体实现，而算法课程着重讨论在更为抽象的层次上解决问题的技巧及分析方法。打个比方，数据结构就好像汽车零件，例如发动机、车轮、车窗、车闸、座椅、灯光、方向盘等，而算法就好像是汽车总体设计。我们假定读者熟悉常用的一些数据结构，包括数组、队列、堆栈、二叉树等，而略去对它们的介绍。读者还应当具有基本的编写程序的知识。
1.1.3 算法与程序的关系
一段用某种计算机语言写成的源码，如果可以在计算机上运行并正确地解决一个问题，则称为一个程序。程序必须严格遵守该语言规定的语法（包括标点符号），并且编程时往往还必须考虑到计算机的物理限制，例如，最大允许的整数在32位机上和16位机上是不同的。而算法则不依赖于某种语言，更不依赖具体计算机的限制。只要步骤和逻辑正确，一个算法可以用任何一种语言表达。当然这种语言必须清楚无误地定义每一步骤且能够让稍懂程序的人看懂。这样，设计算法者可以着重考虑解题方法而免去不必要的琐碎的语法细节。所以，算法通常不是程序，但一定可以用任一种语言的程序来实现。（我们假定机器有足够大的内存。）
1.1.4 选择排序的例子
在这一节，我们举一个例子——选择排序（selection sort）——来说明算法与程序的关系。排序问题就是要求把 n 个输入的数字从小到大（或从大到小）排好。我们假定这n 个输入的数字是存放在数组A[1..n] 中。下面的算法称为选择排序。
【例1-1】选择排序。
输入：A[1], A[2], …, A[n]
输出：把输入的n个数重排使得A[1] " A[2] " … " A[n]
Selection-Sort (A[1..n])
1 for (i ( 1, i " n, i++)
计算机算法的设计与分析，简称为计算机算法，是计算机科学领域中一个重要分支，它主要研究两方面问题：
1）如何分析一个给定算法的时间复杂度。
2）如何为给定的计算问题设计一个算法，使得它的复杂度最低。
通俗讲，这里的时间复杂度就是用多少时间，显然以上两个问题是紧密相连的。因实用价值不大，计算机算法课一般已不太讨论空间复杂度，即用多少存储单元的问题，本书也是这样。这一章，我们介绍算法的时间复杂度的基本概念以及分析时遵循的基本原则。
1.1 算法与数据结构及程序的关系
计算机算法课是数据结构课和程序设计课的后续课程。一个简单的问题是，学了数据结构课和程序设计课之后，为什么还要学算法？程序本身是算法吗？这一节逐步给出简单回答。在深入学习之后，读者自己会有更准确的理解和领悟。
1.1.1 什么是算法
简单地说，算法（algorithm）是为解决某一计算问题而设计的一个过程，其每一步必须能在计算机上实现并在有限时间内完成。广义地讲，一个用某一语言（比如C++ 或机器语言）编写的程序也可称为算法。但是，为了理论分析的严格性和方便，我们对算法的定义加了某些限制。经过下面的讨论，我们会了解是哪些限制及为什么要加这些限制。
1.1.2 算法与数据结构的关系
算法与数据结构是密不可分的，除极少数算法外，几乎所有算法都需要数据结构的支持，而且数据结构的优劣往往决定算法的好坏。数据结构把输入的数据及运算过程中产生的中间数据以某种方式组织起来以便于动态地寻找、更改、插入、删除等。没有一种数据结构是万能的，我们应根据问题和算法的需要选用和设计数据结构，而在讨论数据结构时也必定会讨论其适用的算法。所以，数据结构课程与算法课程的内容往往有很大重叠。但是，数据结构课程需要解释其在计算机上的具体实现，而算法课程着重讨论在更为抽象的层次上解决问题的技巧及分析方法。打个比方，数据结构就好像汽车零件，例如发动机、车轮、车窗、车闸、座椅、灯光、方向盘等，而算法就好像是汽车总体设计。我们假定读者熟悉常用的一些数据结构，包括数组、队列、堆栈、二叉树等，而略去对它们的介绍。读者还应当具有基本的编写程序的知识。
1.1.3 算法与程序的关系
一段用某种计算机语言写成的源码，如果可以在计算机上运行并正确地解决一个问题，则称为一个程序。程序必须严格遵守该语言规定的语法（包括标点符号），并且编程时往往还必须考虑到计算机的物理限制，例如，最大允许的整数在32位机上和16位机上是不同的。而算法则不依赖于某种语言，更不依赖具体计算机的限制。只要步骤和逻辑正确，一个算法可以用任何一种语言表达。当然这种语言必须清楚无误地定义每一步骤且能够让稍懂程序的人看懂。这样，设计算法者可以着重考虑解题方法而免去不必要的琐碎的语法细节。所以，算法通常不是程序，但一定可以用任一种语言的程序来实现。（我们假定机器有足够大的内存。）
1.1.4 选择排序的例子
在这一节，我们举一个例子——选择排序（selection sort）——来说明算法与程序的关系。排序问题就是要求把 n 个输入的数字从小到大（或从大到小）排好。我们假定这n 个输入的数字是存放在数组A[1..n] 中。下面的算法称为选择排序。
【例1-1】选择排序。
输入：A[1], A[2], …, A[n]
输出：把输入的n个数重排使得A[1] " A[2] " … " A[n]
Selection-Sort (A[1..n])
1 for (i ( 1, i " n, i++)
