《算法图解》读书笔记

算法图解 [美] Aditya Bhargava

1.2 二分查找
1.2.1 更佳的查找方式
一般而言,对于包含n 个元素的列表,用二分查找最多需要log2 n 步,而简单查找最多需要n 步。

1.3 大O表示法
1.3.1 算法的运行时间以不同的速度增加
仅知道算法需要多长时间才能运行完毕还不够,还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地。

3.1 递归

1
2
3
4
5
6
def look_for_key(box):
for item in box:
if item.is_a_box():
look_for_key(item) ←------递归!
elif item.is_a_key():
print "found the key!"

这两种方法的作用相同,但在我看来,第二种方法更清晰。递归只是让解决方案更清晰,并没有性能上的优势。实际上,在有些情况下,使用循环的性能更好。我很喜欢Leigh Caldwell在Stack Overflow上说的一句话:“如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。”

第 4 章 快速排序
分而治之 (divide and conquer,D&C)——一种著名的递归式问题解决方法

4.3 再谈大O表示法
快速排序的独特之处在于,其速度取决于选择的基准值。

4.3.1 比较合并排序和快速排序
在大O表示法O (n )中,n 实际上指的是这样的。
c 是算法所需的固定时间量,被称为常量 。例如,print_items 所需的时间可能是10毫秒 n ,而print_items2 所需的时间为1秒 n 。

5.1 散列函数
散列表是你学习的第一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存,但散列表更复杂,它使用散列函数来确定元素的存储位置。

5.3 冲突
散列函数很重要 。前面的散列函数将所有的键都映射到一个位置,而最理想的情况是,散列函数将键均匀地映射到散列表的不同位置。

7.1 使用狄克斯特拉算法
狄克斯特拉算法找出的是总权重最小的路径

7.2 术语
要计算非加权图中的最短路径,可使用广度优先搜索 。要计算加权图中的最短路径,可使用狄克斯特拉算法

在无向图中,每条边都是一个环。狄克斯特拉算法只适用于有向无环图 (directed acyclic graph,DAG)。

7.3 换钢琴
狄克斯特拉算法背后的关键理念:找出图中最便宜的节点,并确保没有到该节点的更便宜的路径 !

8.4 NP完全问题
8.4.2 如何识别NP完全问题
NP完全问题的简单定义是,以难解著称的问题,如旅行商问题和集合覆盖问题。

10.2 创建推荐系统
10.2.3 挑选合适的特征
在挑选合适的特征方面,没有放之四海皆准的法则,你必须考虑到各种需要考虑的因素。

11.1 树
二叉查找树类似于下面这样。对于其中的每个节点,左子节点的值都比它小 ,而右子节点的值都比它大 。

在二叉查找树中查找节点时,平均运行时间为O (log n ),但在最糟的情况下所需时间为O (n );而在有序数组中查找时,即便是在最糟情况下所需的时间也只有O (log n ),因此你可能认为有序数组比二叉查找树更佳。然而,二叉查找树的插入和删除操作的速度要快得多。

B树是一种特殊的二叉树,数据库常用它来存储数据。

11.5 MapReduce
11.5.1 分布式算法为何很有用

MapReduce是一种流行的分布式算法,你可通过流行的开源工具Apache Hadoop来使用它。

11.5.3 归并函数

映射是将一个数组转换为另一个数组。

归并是将一个数组转换为一个元素。