算法图解 / 像小说一样有趣的算法入门书

本文目录结构

编辑推荐

像小说一样有趣的算法入门书。

算法是解决问题的一步步流程，也是计算机科学领域的核心主题。如今程序员经常使用的算法已经经过了前人的探索、检验及证明。如果你想搞明白这些算法，又不想被困在繁琐的证明中，本书正是你的选择。这本图示丰富、引人入胜的实用指南将让你轻松学会如何在自己的程序中高效使用重要的算法。

你一定能看懂的算法基础书

代码示例基于 Python

400 多个示意图，生动介绍算法执行过程

展示不同算法在性能方面的优缺点

教会你用常见算法解决每天面临的实际编程问题

内容简介

本书示例丰富，图文并茂，以让人容易理解的方式阐释了算法，旨在帮助程序员在日常项目中更好地发挥算法的能量。书中的前三章将帮助你打下基础，带你学习二分查找、大 O 表示法、两种基本的数据结构以及递归等。余下的篇幅将主要介绍应用广泛的算法，具体内容包括：面对具体问题时的解决技巧，比如，何时采用贪婪算法或动态规划；散列表的应用；图算法；Kzui 近邻算法。

作者简介

Aditya Bhargava，软件工程师，兼具计算机科学和美术方面的教育背景，在 adit.io 撰写编程方面的博客。

目录

• 前言
• 致谢
• 关于本书

第 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