算法设计与分析基础

出版时间：2004-6  出版社：第1版 (2004年1月1日)  作者：（美）莱维丁（Levitin/A.）/潘彦  页数：388  字数：614000  译者：潘彦  
Tag标签：无  

内容概要

作者基于丰富的教学经验，开发了一套对算法进行分类的新方法。这套方法站在通用问题求解策略的高度，对现有的大多数算法都有能进行很好的分类，从而使本书的读者能够沿着一条清晰的、一致的、连贯的道路来探索算法设计与分析这一迷人领域。   本书十分适合计算机专业的本科高年级学生或研究生学习。另外，由于本书的介绍深入浅出，只要具备数据库存和离散数据学的知识，任何有兴趣探究算法秘密的读者也可以自学本书。

作者简介

Anany Lcvitin 是Villanova大学计算科学系的教授。他的论文《算法设计技术新途径：弥补传统分类法的缺憾》（A new road map of algorithm design techniques;picking up where the traditional classiflcation leaves off ）受到极高的评价。在SIGCSE会议上，作者做过多

书籍目录

第1章 绪论  1.1 算法的概念  习题1.1  1.2 算法问题求解基础  习题1.2  1.3 重要的问题类型  习题1.3  1.4 基本数据结构  习题1.4  小结第2章 算法效率分析基础  2.1 分析框架  习题2.1   2.2 渐进符号和基本效率类型  习题2.2  2.3 非递归算法的数学分析  习题2.3  2.4 递归算法的数学分析  习题2.4  2.5 例题：斐波那契数列  习题2.5  2.6 算法的经验分析  习题2.6  2.7 算法可视法  习题2.7  小结第3章 蛮力法  3.1 选择排序和冒泡排序  习题3.1  3.2 顺序查找和蛮力字符串匹配  习题3.2  3.3 最近对和凸包问题的蛮力算法  习题3.3   3.4 穷举查找  习题3.4  小结第4章 分治法  4.1 合并排序  习题4.1  4.2 快速排序  习题4.2  4.3 折半查找  习题4.3  4.4 二叉树遍历及其相关特性  习题4.4  4.5 大整数乘法和Strassen矩阵乘法 习题4.5   4.6 用分治法解最近对问题和凸包问题  习题4.6  小结第5章 减治法  5.1 插入排序  习题5.1  5.2 深度优先查找和广度优先查找  习题5.2  5.3 拓扑排序  习题5.3  5.4 生成组合对象的算法  习题5.4   5.5 减常因子算法  习题5.5  5.6 减可变规模算法  习题5.6  小结第6章 变治法  6.1 预排序  习题6.1   6.2 高斯消去法  习题6.2  6.3 平衡查找树  习题6.3  6.4 堆和堆排序  习题6.4  6.5 霍纳法则和二进制幂  习题6.5  6.6 问题化简  习题6.6  小结第7章 时空权衡  7.1 计数排序  习题7.1  7.2 串匹配中的输入增强技术  习题7.2  7.3 散列法  习题7.3  7.4 B树  习题7.4  小结第8章 动态规划  8.1 计算二项式系数  习题8.1  8.2 Warshall算法和Floyd算法  习题8.2  8.3 最优二叉查找树  习题8.3  8.4 背包问题和记忆功能  习题8.4  小结第9章 贪婪技术  9.1 Prim算法  习题9.1   9.2 Kruskal算法  习题9.2  9.3 Dijkstra算法  习题9.3  9.4 哈夫曼树  习题9.4  小结第10章 算法能力的极限  10.1 如何求下界  习题10.1  10.2 决策树  习题10.2  10.3 P、NP和NP完全问题  习题10.3  10.4 数值算法的挑战  习题10.4  小结第11章 超越算法能力的极限  11.1 回溯  习题11.1  11.2 分支界限  习题11.2   11.3 NP困难问题的近似算法  习题11.3  11.4 解非线性方程的算法  习题11.4  小结跋附录A：算法分析的实用公式  对数的性质  组合学  重要的求和公式  求和乘法法则  用定积分逼近求和式  向下取整和向上取整公式  其他附录B：递推关系简明指南  序列和递推关系  递推关系的求解方法   算法分析中的常见递推类型习题提示　第1章　第2章　第3章　第4章　第5章　第6章　第7章　第8章　第9章　第10章参考文献

媒体关注与评论

　　作者在本书中采用了一种算法设计技术的新分类法，使得我们能以一种一致的方式涵盖许多经典的算法，而这在传统分类法中是无法做到的。作为解决问题的通用工具、算法设计技术得到了广泛的应用。尤其是用来解决一些流行的谜题时，它的威力得到了极大的体现。　　本书相对同类教材来说，可读性更强，得益于多年来教授算法的经验，作者能够以一种清晰的方式、有条不紊地组织本书的脉络。　　本书中的习题超过600道，其中有些习题还利用了网络资源，本书还为所有的习题提供了提示，以帮助读者们很好地达到学习目标。　　

用户评论 (总计2条)

•   搞算法搞ACM的话，这本书和LRJ的“黑书”以及一本电子工业出版社出版的（具体忘了）算法书，可以说是必备的入门书籍，绝对值得一买！经典而且实用！
•   这本书是教材，感觉还可以，就我买的时候，松树的不小心，把书弄得有点皱纹。其余的还是比较好的，也不贵。如果有需要这本书的同志们，建议来当当网上选购。