算法基础_[美]罗德·斯蒂芬斯（Rod Stephens）_9787111560920

本书的撰写有机结合了理论与实现，在讲授算法理论的同时也通过C#实例讲授了算法的实现。通过描述并分析一些重要的传统算法，从而理解它们并且了解每一个算法在什么时候使用较为适合，通俗易懂地教授读者创造自己的算法的技巧。这些技巧让读者能从不同的角度看问题，建立有用的方法工具，从而解决实际问题，抑或从容面对面试难题。本书适合当作“算法设计与分析”和“数据结构与算法”两门课程的教材或参考书使用。特别是本书还融入和面试相关的内容，因此适合作为算法相关工作面试的参考资料。

　　EssentialAlgorithms:APracticalApproachtoComputerAlgorithms算法是使高效的程序成为可能的方法。它们解释了如何排列记录、搜索项、计算数值（比如质因子分解）、查找一个街道网络中的最短路径、确定可能通过通信网络的最大流。算法好坏的差别可能意味着是在一秒、一个小时内解决问题，还是永远也不能解决问题。

　　学习算法使你能建立有用的方法工具来解决具体的问题。它能帮助你理解在不同的情况下，哪个算法是最有效的，所以对于一个特定的问题，你就能选择最适合的算法。对某些数据而言性能优异的算法可能对其他的数据而言表现糟糕。所以知道如何选择一个最适合当前情况的算法是很重要的。

　　更重要的是，通过学习算法，你可以学习常规的问题解决技巧。即使你已知的任何算法都不能很好地适合当前的状况，你也可以把这些技巧应用到其他问题上。这些技巧让你从不同的角度看问题，使你能创造和分析自己的算法，从而解决你的问题，并且满足没有预料到的需求。

　　除了帮助你解决工作上的问题，这些技巧甚至会帮助你获得需要使用这些技巧的工作。许多大的科技公司，比如微软、谷歌、雅虎、IBM等公司都想要让他们的程序员理解算法和相关问题的解决技巧。其中，有些公司因为让面试者在面试中解决算法编程和逻辑难题而“臭名昭著”。

　　好的面试官不一定期待你解决每一个难题。事实上，当你没有解决某个难题时，他们可能会了解更多。最好的面试官想看到你如何处理一个不熟悉的问题，而不是想要看到答案。他们想看到你是举起双手说这个问题在面试中是不合理的，还是你分析了这个问题，并提出了一条有希望的推理来用算法解决这个问题。“天哪，我不知道。或许我要上网搜一下”将会是一个坏的答案。“看起来一个递归的分治法可能有用”将会是一个好得多的答案。

　　这是一本易读的计算机算法导论书。它描述了一些重要的传统算法，并且说明了每一个算法在什么时候是适合的。它解释了如何分析算法从而理解它们的行为。最重要的，它教会了你创造自己新算法的技巧。

　　这里是本书中描述的一些有用的算法：

　　数值算法，比如随机化、分解因式、处理质数、数值积分熟练操作常见数据结构的方法，比如堆、树、平衡树、B树排序和搜索网络算法，比如最短路径、生成树、拓扑排序和流计算这里是本书中解释的一些常规的问题解决技巧：

　　暴力或者穷举搜索分治法回溯法递归分支界限贪心算法和爬山法最小花费算法缩小范围启发式算法为了帮助读者掌握这些算法，本书提供了一些练习，读者可以利用它们来探索自己的方法，以便修改书中的算法并把它们应用到新的情况中。这些练习也会帮助你巩固算法中的主要技巧。

　　最后，本书包含了解决面试中可能遇到的算法问题的技巧。算法技巧会让你解决许多面试中的难题。即使你不能用算法技巧解决每一个难题，至少表明你熟悉这些方法并且能用它们解决其他的问题。

　　算法选择本书中的每一个算法都是因为一个或多个下列原因而被选择的：

　　这个算法是有用的，并且有经验的程序员应该能理解它如何工作以及如何在程序中使用它。

　　这个算法展示了你可以应用到其他问题中的重要算法编程技巧。

　　计算机科学专业的学生普遍学习这个算法，所以这个算法或者它使用的技巧可能出现在一个技术性面试中。

　　当读者读完本书并做完练习后，将会有一个好的算法基础并掌握解决自己编程问题的技巧。

　　本书的目标人群本书主要针对三种读者：专业程序员、准备面试的程序员和学习编程的学生。

　　专业程序员将会发现本书中所描述的算法和技巧对于解决他们工作中遇到的难题是很有用的。即使遇到无法直接用书中的算法解决的问题，阅读本书中的算法也会让你从新的角度观察问题，从而发现新的解决办法。

　　准备工作面试的程序员可以使用本书来磨炼他们的算法技巧。你的面试可能不会包括书中描述的任何问题，但是可能包含一些足够相似的问题。你可以用从本书中学到的技巧解决它们。

　　学习编程的学生应该学习这些算法。本书中描述的许多方法是简单、富有魅力而且有效的。但是它们并不都是十分显而易见的，所以你不一定会在偶然间自己发现它们。递归、分治、分支界限等技巧，还有使用众所周知的数据结构，这些对任何有兴趣编程的人都是十分需要掌握的。

　　注就我个人而言，算法只是一种乐趣，它们就像填字游戏或者数独一样。我喜欢组成一个复杂的算法，倒一些数据进去，然后看到一个美丽的三维图形、一条匹配一系列点的曲线，或者一些其他的优雅的答案出现。我喜欢这种感觉。

　　充分运用本书仅仅是阅读本书，就能学到一些新的算法和技巧。但是要真正掌握这些算法体现出的方法，就需要用它们工作，需要用某种编程语言实现它们。你还需要实验、修改这些算法，尝试旧问题的新变型。本书中的练习和面试问题能让你想到使用这些算法中技巧的新方法。

　　为了从本书中得到最大的收获，我强烈推荐用一种你最喜欢的语言实现尽可能多的算法。甚至用

目　录 Essential Algorithms: A Practical Approach to Computer Algorithms 出版者的话译者序前言第1章　算法基础知识1 1.1　方法1 1.2　算法和数据结构2 1.3　伪代码2 1.4　算法的特点4 1.4.1　大O符号5 1.4.2　常见的运行时间函数7 1.4.3　可视化函数12 1.5实际因素12 1.6　总结13 练习13 第2章　数值算法16 2.1　随机化数据16 2.1.1　随机数生成16 2.1.2　随机化数组20 2.1.3　生成不均匀分布21 2.2　寻找最大公约数21 2.3　求幂运算23 2.4　有关素数的运算24 2.4.1　寻找素数因子24 2.4.2　寻找素数26 2.4.3素性测试27 2.5　进行数值积分28 2.5.1　矩形规则28 2.5.2梯形规则29 2.5.3　自适应求积30 2.5.4　蒙特卡罗积分32 2.6　查找零32 2.7　总结34 练习34 第3章　链表36 3.1　基本概念36 3.2　单链表37 3.2.1　遍历链表37 3.2.2　查找单元格37 3.2.3　使用哨兵38 3.2.4　在开头添加单元格39 3.2.5　在结尾添加单元格40 3.2.6　在某个单元格后插入单元格40 3.2.7　删除单元格41 3.3　双向链表42 3.4　有序链表43 3.5　链表算法44 3.5.1　复制链表44 3.5.2　链表的插入排序45 3.6　链表的选择排序46 3.7　多线程链表47 3.8　循环链表48 3.8.1　标记单元格49 3.8.2　使用散列表50 3.8.3　链表回溯51 3.8.4　反转链表51 3.8.5　乌龟和兔子53 3.8.6　双向链表中的循环问题55 3.9　总结55 练习55 第4章　数组57 4.1　基本概念57 4.2　一维数组58 4.2.1　查找元素58 4.2.2　查找最大值、最小值、平均值59 4.2.3　插入元素60 4.2.4　移除元素61 4.3　非零下界61 4.3.1　二维数组61 4.3.2　多维数组62 4.4　三角形数组64 4.5　稀疏数组66 4.5.1　找到行或列67 4.5.2　获取值68 4.5.3　设置值69 4.5.4　删除值71 4.6　矩阵72 4.7　总结74 练习74 第5章　栈和队列76 5.1　栈76 5.1.1　栈的链表实现76 5.1.2　栈的数组实现77 5.1.3　双向栈78 5.1.4　栈的算法79 5.2　队列84 5.2.1　队列的链表实现84 5.2.2　队列的数组实现85 5.2.3　专用队列86 5.3　总结87 练习87 第6章　排序89 6.1　时间复杂度为O(N2)的算法89 6.1.1　数组中的插入排序89 6.1.2　数组中的选择排序90 6.1.3　冒泡排序91 6.2　时间复杂度为O(N log N)的算法93 6.2.1　堆排序93 6.2.2　快速排序98 6.2.3　归并排序103 6.3　时间复杂度为亚O(N log N)的算法105 6.3.1　计数排序106 6.3.2　桶排序107 6.4　总结108 练习108 第7章　搜索110 7.1　线性搜索110 7.2　二分搜索111 7.3　插值搜索112 7.4　总结113 练习113 第8章　散列表114 8.1　散列表的基础知识114 8.2　链115 8.3　开放寻址116 8.3.1　删除记录117 8.3.2　线性探测118 8.3.3　二次探测119 8.3.4　伪随机探测120 8.3.5　双散列120 8.3.6　有序散列121 8.4　总结122 练习123 第9章　递归125 9.1　基础算法125 9.1.1　阶乘125 9.1.2　斐波那契数127 9.1.3　汉诺塔128 9.2　图算法130 9.2.1　科赫曲线130 9.2.2　希尔伯特曲线131 9.2.3　谢尔宾斯基曲线132 9.2.4　垫片134 9.3　回溯算法134 9.3.1　八皇后问题136 9.3.2　骑士巡游138 9.4　选择与排列140 9.4.1　循环选择140 9.4.2　重复选择141 9.4.3　不重复选择142 9.4.4　元素可重复的排列143 9.4.5　元素不重复的排列144 9.5　消去递归145 9.5.1　尾递归的消除145 9.5.2　存储中间值146 9.5.3　一般递归的消除148 9.6　总结150 练习151 第10章　树153 10.1　树的术语153 10.2　二叉树属性155 10.3　树的表示157 10.3.1　建立树的通用方法157 10.3.2　构造完全树159 10.4　树的遍历160 10.4.1　前序遍历160 10.4.2　中序遍历162 10.4.3　后序遍历163 10.4.4　深度优先遍历164 10.4.5　遍历的运行时间164 10.5　排序树 165 10.5.1　添加结点165 10.5.2　查找结点166 10.5.3　删除结点167 10.6　线索树168 10.6.1　建立线索树169 10.6.2　使用线索树171 10.7　特化树算法172 10.7.1　动物游戏172 10.7.2　表达式求值173 10.7.3　四叉树175 10.7.4　Trie树179 10.8　总结182 练习182 第11章　平衡树185 11.1　AVL树185 11.1.1　添加值185 11.1.2　删除值187 11.2　2-3树187 11.2.1　添加值188 11.2.2　删除值189 11.3　B树191 11.3.1　添加值191 11.3.2　删除值192 11.4　平衡树变体193 11.4.1　自上而下的B树193 11.4.2　B+树193 11.5　总结194 练习195 第12章　决策树196 12.1　游戏搜索树196 12.1.1　极小化极大值算法197 12.1.2　初始步骤和反应199 12.1.3　启发式游戏树200 12.2　搜索通用决策树201 12.2.1　优化问题202 12.2.2　穷举搜索202 12.2.3　分支界限203 12.2.4　决策树的启发式搜索205 12.2.5　其他决策树问题209 12.3　总结212 练习195 第13章　基本网络算法214 13.1　网络术语214 13.2

你还可能感兴趣

我要评论