**
前言
**
算法是使高效的程序成为可能的方法。它们解释了如何排列记录、搜索项、计算数值(比如质因子分解)、查找一个街道网络中的最短路径、确定可能通过通信网络的最大流。算法好坏的差别可能意味着是在一秒、一个小时内解决问题,还是永远也不能解决问题。
学习算法使你能建立有用的方法工具来解决具体的问题。它能帮助你理解在不同的情况下,哪个算法是最有效的,所以对于一个特定的问题,你就能选择最适合的算法。对某些数据而言性能优异的算法可能对其他的数据而言表现糟糕。所以知道如何选择一个最适合当前情况的算法是很重要的。
更重要的是,通过学习算法,你可以学习常规的问题解决技巧。即使你已知的任何算法都不能很好地适合当前的状况,你也可以把这些技巧应用到其他问题上。这些技巧让你从不同的角度看问题,使你能创造和分析自己的算法,从而解决你的问题,并且满足没有预料到的需求。
除了帮助你解决工作上的问题,这些技巧甚至会帮助你获得需要使用这些技巧的工作。许多大的科技公司,比如微软、谷歌、雅虎、IBM等公司都想要让他们的程序员理解算法和相关问题的解决技巧。其中,有些公司因为让面试者在面试中解决算法编程和逻辑难题而“臭名昭著”。
好的面试官不一定期待你解决每一个难题。事实上,当你没有解决某个难题时,他们可能会了解更多。最好的面试官想看到你如何处理一个不熟悉的问题,而不是想要看到答案。他们想看到你是举起双手说这个问题在面试中是不合理的,还是你分析了这个问题,并提出了一条有希望的推理来用算法解决这个问题。“天哪,我不知道。或许我要上网搜一下”将会是一个坏的答案。“看起来一个递归的分治法可能有用”将会是一个好得多的答案。
这是一本易读的计算机算法导论书。它描述了一些重要的传统算法,并且说明了每一个算法在什么时候是适合的。它解释了如何分析算法从而理解它们的行为。最重要的,它教会了你创造自己新算法的技巧。
这里是本书中描述的一些有用的算法:
数值算法,比如随机化、分解因式、处理质数、数值积分
熟练操作常见数据结构的方法,比如堆、树、平衡树、B树
排序和搜索
网络算法,比如最短路径、生成树、拓扑排序和流计算
这里是本书中解释的一些常规的问题解决技巧:
暴力或者穷举搜索
分治法
回溯法
递归
分支界限
贪心算法和爬山法
最小花费算法
缩小范围
启发式算法
为了帮助读者掌握这些算法,本书提供了一些练习,读者可以利用它们来探索自己的方法,以便修改书中的算法并把它们应用到新的情况中。这些练习也会帮助你巩固算法中的主要技巧。
目录
[第1章 算法基础知识
1.1 方法]()
1.2 算法和数据结构
1.3 伪代码
1.4 算法的特点
1.4.1 大O符号
1.4.2 常见的运行时间函数
1.4.3 可视化函数
1.5实际因素
1.6 总结
1.7 练习
[第2章 数值算法
2.1 随机化数据]()
2.1.1 随机数生成
2.1.2 随机化数组
2.1.3 生成不均匀分布
2.2 寻找最大公约数
2.3 求幂运算
2.4 有关素数的运算
2.4.1 寻找素数因子
2.4.2 寻找素数
2.4.3素性测试
2.5 进行数值积分
2.5.1 矩形规则
2.5.2梯形规则
2.5.3 自适应求积
2.5.4 蒙特卡罗积分
2.6 查找零
2.7 总结
2.8 练习
[第3章 链表
3.1 基本概念]()
3.2 单链表
3.2.1 遍历链表
3.2.2 查找单元格
3.2.3 使用哨兵
3.2.4 在开头添加单元格
3.2.5 在结尾添加单元格
3.2.6 在某个单元格后插入单元格
3.2.7 删除单元格
3.3 双向链表
3.4 有序链表
3.5 链表算法
3.5.1 复制链表
3.5.2 链表的插入排序
3.6 链表的选择排序
3.7 多线程链表
3.8 循环链表
3.8.1 标记单元格
3.8.2 使用散列表
3.8.3 链表回溯
3.8.4 反转链表
3.8.5 乌龟和兔子
3.8.6 双向链表中的循环问题
3.9 总结
3.10 练习