像小说集一样趣味的算法新手入门书。
算法是解决困难的一步步步骤,都是电子信息科学行业的关键主题。现如今程序员*常见的算法早已历经了古人的探索、检测及证实。假如你要搞明白这种算法,又不愿困在在繁杂的证实中,这书更是你的不二选择。这部图例丰富多彩、扣人心弦的好用手册将给你轻轻松松懂得怎样在自身的程序流程中高效率应用关键的算法。
这书范例丰富多彩,图片配文字,以令人非常容易了解的方法诠释了算法,致力于协助程序员在平时新项目中充分发挥算法的动能。书中的前三章将协助你奠定基础,陪你学习培训二分查找、大O表示法、二种基础的数据结构及其递归等。剩下的篇数将关键详细介绍运用普遍的算法,主要内容包含:应对实际难题时的处理方法,例如,什么时候选用贪欲算法或动态规划;散列表的运用;图算法;Kzui近邻算法。
目录
- 前言
- 致谢
- 关于本书
- 第1 章 算法简介 1
- 1.1 引言 1
- 1.1.1 性能方面 1
- 1.1.2 问题解决技巧 2
- 1.2 二分查找 2
- 1.2.1 更佳的查找方式 4
- 1.2.2 运行时间 8
- 1.3 大O 表示法 8
- 1.3.1 算法的运行时间以不同的速度增加 9
- 1.3.2 理解不同的大O运行时间 10
- 1.3.3 大O 表示法指出了最糟情况下的运行时间 12
- 1.3.4 一些常见的大O运行时间 12
- 1.3.5 旅行商 13
- 1.4 小结 15
- 第2 章 选择排序 16
- 2.1 内存的工作原理 16
- 2.2 数组和链表 18
- 2.2.1 链表 19
- 2.2.2 数组 20
- 2.2.3 术语 21
- 2.2.4 在中间插入 22
- 2.2.5 删除 23
- 2.3 选择排序 25
- 2.4 小结 28
- 第3 章 递归 29
- 3.1 递归 29
- 3.2 基线条件和递归条件 32
- 3.3 栈 33
- 3.3.1 调用栈 34
- 3.3.2 递归调用栈 36
- 3.4 小结 40
- 第4 章 快速排序 41
- 4.1 分而治之 41
- 4.2 快速排序 47
- 4.3 再谈大O表示法 52
- 4.3.1 比较合并排序和快速排序 53
- 4.3.2 平均情况和最糟情况 54
- 4.4 小结 57
- 第5 章 散列表 58
- 5.1 散列函数 60
- 5.2 应用案例 63
- 5.2.1 将散列表用于查找 63
- 5.2.2 防止重复 64
- 5.2.3 将散列表用作缓存 66
- 5.2.4 小结 68
- 5.3 冲突 69
- 5.4 性能 71
- 5.4.1 填装因子 72
- 5.4.2 良好的散列函数 74
- 5.5 小结 75
- 第6 章 广度优先搜索 76
- 6.1 图简介 77
- 6.2 图是什么 79
- 6.3 广度优先搜索 79
- 6.3.1 查找最短路径 82
- 6.3.2 队列 83
- 6.4 实现图 84
- 6.5 实现算法 86
- 6.6 小结 93
- 第7 章 狄克斯特拉算法 94
- 7.1 使用狄克斯特拉算法 95
- 7.2 术语 98
- 7.3 换钢琴 100
- 7.4 负权边 105
- 7.5 实现 108
- 7.6 小结 116
- 第8 章 贪婪算法 117
- 8.1 教室调度问题 117
- 8.2 背包问题 119
- 8.3 集合覆盖问题 121
- 8.4 NP 完全问题 127
- 8.4.1 旅行商问题详解 127
- 8.4.2 如何识别NP 完全问题 131
- 8.5 小结 133
- 第9 章 动态规划 134
- 9.1 背包问题 134
- 9.1.1 简单算法 135
- 9.1.2 动态规划 136
- 9.2 背包问题FAQ 143
- 9.2.1 再增加一件商品将如何呢 143
- 9.2.2 行的排列顺序发生变化时结果将如何 145
- 9.2.3 可以逐列而不是逐行填充网格吗 146
- 9.2.4 增加一件更小的商品将如何呢 146
- 9.2.5 可以偷商品的一部分吗 146
- 9.2.6 旅游行程最优化 147
- 9.2.7 处理相互依赖的情况 148
- 9.2.8 计算最终的解时会涉及两个以上的子背包吗 148
- 9.2.9 最优解可能导致背包没装满吗 149
- 9.3 最长公共子串 149
- 9.3.1 绘制网格 150
- 9.3.2 填充网格 151
- 9.3.3 揭晓答案 152
- 9.3.4 最长公共子序列 153
- 9.3.5 最长公共子序列之解决方案 154
- 9.4 小结 155
- 第10 章 K 最近邻算法 156
- 10.1 橙子还是柚子 156
- 10.2 创建推荐系统 158
- 10.2.1 特征抽取 159
- 10.2.2 回归 162
- 10.2.3 挑选合适的特征 164
- 10.3 机器学习简介 165
- 10.3.1 OCR 165
- 10.3.2 创建垃圾邮件过滤器 166
- 10.3.3 预测股票市场 167
- 10.4 小结 167
- 第11 章 接下来如何做 168
- 11.1 树 168
- 11.2 反向索引 171
- 11.3 傅里叶变换 171
- 11.4 并行算法 172
- 11.5 MapReduce 173
- 11.5.1 分布式算法为何很有用 173
- 11.5.2 映射函数 173
- 11.5.3 归并函数 174
- 11.6 布隆过滤器和HyperLogLog 174
- 11.6.1 布隆过滤器 175
- 11.6.2 HyperLogLog 176
- 11.7 SHA 算法 176
- 11.7.1 比较文件 177
- 11.7.2 检查密码 178
- 11.8 局部敏感的散列算法 178
- 11.9 Diffie-Hellman 密钥交换 179
- 11.10 线性规划 180
- 11.11 结语 180
- 练习答案 181