算法设计、分析与实现从入门到精通

出版时间：2010-6  出版社：人民邮电出版社  作者：徐子珊  页数：409  字数：693000  
Tag标签：无  

前言

　　算法作为数学的一个分支已经存在几百年了。然而，算法真正焕发青春得到长足的发展，还是发生在20世纪电子计算机发明的时代。随着计算机技术的广泛应用，人们越来越清楚地认识到，作为计算机科学与工程最主要的技术——程序设计，其灵魂就是解决问题的算法。　　能否提供一本既能让广大读者清晰、轻松地理解算法思想，又能为读者提供算法的程序实现各种关键技术建议的书是作者一个很长时间的思考。现在摆在读者面前的这本书，就是这一思考的结果。作者希望本书在读者研习算法与程序设计时不仅是书桌前或是床头边的参考书，更多的是计算机旁的参考书。　　本书先按算法设计技巧分类为渐增型算法、递归分治算法、动态规划算法、贪婪算法、回溯算法和图的搜索算法等前6章。每章对2～3个经典问题针对一种算法设计技巧，给出解决问题的算法，并分析算法的时间复杂度。笔者认为，对于初学者来说，按算法的设计方法划分章节，算法思想的阐述比较集中，有利于入门。一旦具备了算法设计的基本方法，按应用领域划分专题深入学习，读者可以应用已学的方法综合起来解决比较复杂的问题。第7章的线性规划和第8章的计算几何可以算作这部分内容。在此基础上，读者可以更进一步探讨更前沿的随机算法、近似算法和并行算法等现代算法设计方法。本书之所以按照这样的8章编排，还有一个重要原因是它们之间有一定的前后逻辑关系：第1章渐增型算法和第2章分治算法是最基本的算法，并且在这两章内容展开的同时我们还介绍了后面各章所需要的数据结构，例如第2章介绍的优先队列就是第4章讨论贪婪算法时所需要的。建议读者以本书的章节顺序研读，特别是实现的程序中也有很多是前后呼应的代码段。　　算法理论对于程序设计实践的指导意义已经被大家所接受，但不管是在校学生还是已踏上职业征程的程序员，很多人对算法学习都有一种“枯燥繁难”的先人之见。如何有效地学习算法的设计与分析，是本书试图与读者一起探讨的最重要的目标之一。其实，算法都是针对具体问题的。对于要解决的问题进行深入理解与分析，是设计出正确有效的算法的前提。然而，“深入理解与分析”似乎是个模糊概念，怎样的“度”才能认为是对问题深入理解了呢？计算学科提出了一个非常重要的“标准”：简单地说，能够把一个问题输入与输出准确地提炼并表述出来，就可以认为是理解了这个问题。这样对问题的描述称为“问题的形式化描述”。一旦形式化地描述出了问题的输入与输出，也就能准确地把握住算法解决问题所需要的条件和所要达到的目标。换句话说，设计算法是要在问题的输入与输出之间架起一座通达的桥梁。本书以此为目标，无论是对正文中讨论的问题还是“动手做”题目中的问题或者是作为应用的ICPC问题，我们都给出其形式化描述。有了问题的输入与输出的数据表示，运用人们的常识、数学知识和科学知识建立起从输入到输出之间的对应关系，这就是算法。　　算法可以用自然语言或是图形等工具加以描述，但要将算法作为计算机程序的设计蓝图，则需要将其无歧义地表述出来。用伪代码表述算法是迄今为止人们所使用的最有效的方法。计算机程序设计语言当然也能做到无歧义地描述算法。事实上，市场上也有以某种具体的程序设计语言为描述工具的算法书籍，但这样的图书往往要面对一个两难问题：一方面，若要使具体语言描述的算法能直接运行，则必须做诸如变量声明、用该语言所提供的方式表示各种复杂的数学表达式以及其他操作等各种技术细节工作。这样就会大大降低算法描述的可读性，妨碍读者对算法思想本身的理解与接受。另一方面，如果为提高算法描述的可读性而省略上述的各种技术细节，则仍然回到伪代码描述的起点，让读者在实现程序时有隔靴抓痒的感觉。

内容概要

　　本书第1章～第6章按算法设计技巧分成渐增型算法、分治算法、动态规划算法、贪婪算法、回溯算法和图的搜索算法。每章针对一些经典问题给出解决问题的算法，并分析算法的时间复杂度。这样对于初学者来说，按照算法的设计方法划分，算法思想的阐述比较集中，有利于快速入门理解算法的精髓所在。一旦具备了算法设计的基本方法，按应用领域划分专题深入学习，读者可以结合已学的方法综合起来解决比较复杂的问题。本书第7章的线性规划和第8章的计算几何是综合算法部分，通过学习这些内容，读者将进一步地学习更前沿的随机算法、近似算法和并行算法等现代算法设计方法和实战技巧。　　本书特色是按照算法之间逻辑关系编排学习顺序，并对每一个经典算法，都给出了完整的C/C++/Java三种主流编程语言的实现程序，是一本既能让读者清晰、轻松地理解算法思想，又能让读者编程实现算法的实用书籍。建议读者对照本书在计算机上自己创建项目、文件，进行录入、调试程序等操作，从中体会算法思想的精髓，体验编程成功带来的乐趣。

书籍目录

第1章　集腋成裘——渐增型算法　　1.1　算法设计与分析　　1.2　插入排序算法　　　1.2.1　算法描述与分析　　　1.2.2　程序实现　　　1.2.3　应用——赢得舞伴　　1.3　两个有序序列的合并算法　　　1.3.1　算法描述与分析　　　1.3.2　程序实现　　1.4　序列的划分　　　1.4.1　算法描述与分析　　　1.4.2　程序实现　　1.5　小结　第2章　化整为零——分治算法　　2.1　Hanoi塔问题与递归算法　　　2.1.1　算法的描述与分析　　　2.1.2　程序实现　　　2.1.3　应用——新Hanoi塔游戏　　2.2　归并排序算法　　　2.2.1　算法描述与分析　　　2.2.2　程序实现　　　2.2.3　应用——让舞伴更开心　　2.3　快速排序算法　　　2.3.1　算法描述与分析　　　2.3.2　程序实现　　2.4　堆的实现　　　2.4.1　堆的概念及其创建　　　2.4.2　程序实现　　2.5　堆排序　　　2.5.1　算法描述与分析　　　2.5.2　程序实现　　2.6　基于二叉堆的优先队列　　　2.6.1　算法描述与分析　　　2.6.2　程序实现　　2.7　关于排序算法　　　2.7.1　比较型排序算法的时间复杂度　　　2.7.2　C/C++/Java提供的排序函数(方法)　　　2.7.3　应用——环法自行车赛　　2.8　小结　第3章　记表备查——动态规划算法　　3.1　矩阵链乘法　　　3.1.1　算法描述与分析　　　3.1.2　程序实现　　　3.1.3　应用——牛牛玩牌　　3.2　最长公共子序列　　　3.2.1　算法描述与分析　　　3.2.2　程序实现　　　3.2.3　算法的应用　　3.3　背包问题　　　3.3.1　算法描述与分析　　　3.3.2　程序实现　　　3.3.3　算法的应用　　3.4　带权有向图中任意两点间的最短路径　　　3.4.1　算法描述与分析　　　3.4.2　程序实现　　　3.4.3　应用——牛牛聚会　　3.5　小结　第4章　高效的选择——贪婪算法　　4.1　活动选择问题　　　4.1.1　算法描述与分析　　　4.1.2　程序实现　　　4.1.3　贪婪算法与动态规划　　　4.1.4　应用——海岸雷达　　4.2　Huffman编码　　　4.2.1　算法描述与分析　　　4.2.2　程序实现　　　4.2.3　应用——Huffman树　　4.3　最小生成树　　　4.3.1　算法描述与分析　　　4.3.2　程序实现　　　4.3.3　应用——北方通信网　　4.4　单源最短路径问题　　　4.4.1　算法描述与分析　　　4.4.2　程序实现　　　4.4.3　应用——西气东送　　4.5　小结　第5章　艰苦卓绝——回溯算法　第6章　图的搜索算法　第7章　集组合优化问题之大成——线性规划　第8章　图形学基础——计算几何　附录　参考文献　

章节摘录

　　1.1 算法设计与分析　　1.什么是算法　　众所周知，算法是程序的灵魂。只有对需要解决的计算问题有一个正确的算法，才可能编写出解决此问题的程序。所谓算法就是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解。算法研究有着悠久的历史，内容极其丰富。人们对各种典型的问题研究出了很多经典的算法设计方法。例如，本书详细讨论的渐增型算法、分治算法、动态规划、贪婪策略和回溯算法等都是具有代表性的经典算法设计方法。对这些方法的学习，可以为我们在解决各种具体问题时设计出正确、高效的算法提供有益的启示。　　2.算法分析基本概念　　解决一个问题，算法不必是唯一的。对表示问题的数据的不同组织方式（数据结构），解决问题的不同策略（算法思想）将导致不同的算法。解决同一问题的不同算法，消耗的时间和空间资源量有所不同。算法运行所需要的计算机资源的量称为算法的复杂性。一般来说，解决同一问题的算法，需要的资源量越少，我们认为越优秀。计算算法运行所需资源量的过程称为算法复杂性分析，简称为算法分析。理论上，算法分析既要计算算法的时间复杂性，也要计算它的空间复杂性。然而，算法的运行时间都是消耗在数据处理上的，从这个意义上说，算法的空间复杂性不会超过时间复杂性。出于这个原因，人们多关注于算法的时间复杂性分析。本书中除非特别说明，所说的算法分析，仅局限于对算法的时间复杂性分析。　　为客观、科学地评估算法的时间复杂性，我们设置一台抽象的计算机，它只用一个处理机，却有无限量的随机存储器。它的有限个基本操作——算术运算、逻辑运算和数据的移动（比如对变量的赋值）均在有限固定时间内完成，我们进一步假定所有这些基本操作都消耗一个时间单位。

编辑推荐

　　国内算法界著名学者、计算理论学组组长朱洪教授推荐。　　本算法教材文笔顺畅，处理算法描述的两难问题有自己的特点，且具有丰富的C、C++和Java实现程序，这对读者学以致用很有帮助。《算法设计、分析与实现从入门到精通：C、C++和Java》还有一个特点，文采甚好，如集腋成裘、化整为零、赢得舞伴等，生动形象，易于学习和理解。《算法设计、分析与实现从入门到精通：C、C++和Java》插图也精美，如Hanoi塔图等，都给《算法设计、分析与实现从入门到精通：C、C++和Java》增色很多，让读者在兴趣中学习。此书在应用性例题上，兼有中、英文描述题目，如环法自行车赛、牛牛玩牌、射雕英雄等例题。这些例题来自ACM／ICPC，它们富有挑战性，可引起读者的学习兴趣。　　38个经典范例，包括渐增型算法、分治算法、动态规划算法、贪婪算法、回溯算法、线性规划算法和计算几何等算法设计和实现技巧。　　26个国际大学生程序设计竞赛真题的详细解析及算法的应用。　　3种主流语言(C、C++和Java)实现算法范例程序。

用户评论 (总计4条)

•   书里面先把理论详解，然后把算法思想用程序表达出来，很实用.....
•   就是从ACM上面抽一些典型的例题下来讲，用三种语言描述，一般般。
•   讲解到位，比较详细
•   当当加油！