读书笔记:《算法图解》 - [美]Aditya Bhargava 著 / 袁国忠 译

浅入深出[皱眉] ★★★★★

读完时间:2020 年 8 月 17 日

出版时间:2017 年 3 月

1.2 二分查找

需要猜测的次数与列表长度相同,这被称为线性时间(linear time)。

二分查找的运行时间为对数时间(或log时间)。

2.2 数组和链表

使用数组意味着所有待办事项在内存中都是相连的(紧靠在一起的)。

链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。

需要同时读取所有元素时,链表的效率很高:你读取第一个元素,根据其中的地址再读取第二个元素,以此类推。但如果你需要跳跃,链表的效率真的很低。

3.1 递归

如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。

3.2 基线条件和递归条件

每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环。

3.3 栈

调用另一个函数时,当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。

4.1 分而治之

编写涉及数组的递归函数时,基线条件通常是数组为空或只包含一个元素。陷入困境时,请检查基线条件是不是这样的。

5.1 散列函数

数组和链表都被直接映射到内存,但散列表更复杂,它使用散列函数来确定元素的存储位置。

5.4 性能

在平均情况下,散列表执行各种操作的时间都为O(1)。O(1)被称为常量时间。你以前没有见过常量时间,它并不意味着马上,而是说不管散列表多大,所需的时间都相同。例如,你知道的,简单查找的运行时间为线性时间。

填装因子越低,发生冲突的可能性越小,散列表的性能越高。一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表的长度。

6.1 图简介

解决最短路径问题的算法被称为广度优先搜索。要确定如何从双子峰前往金门大桥,需要两个步骤。

  1. 使用图来建立问题模型。
  2. 使用广度优先搜索解决问题。

6.4 实现图

散列表是无序的,因此添加键—值对的顺序无关紧要。

6.5 实现算法

如果任务A依赖于任务B,在列表中任务A就必须在任务B后面。这被称为拓扑排序,使用它可根据图创建一个有序列表。

7.2 术语

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

8.2 背包问题

在有些情况下,完美是优秀的敌人。有时候,你只需找到一个能够大致解决问题的算法,此时贪婪算法正好可派上用场,因为它们实现起来很容易,得到的结果又与正确结果相当接近。

9.2 背包问题FAQ

每次迭代时,你都存储当前的最大价值。最大价值不可能比以前低!

9.3 最长公共子串

在问题可分解为彼此独立且离散的子问题时,就可使用动态规划来解决。

11.1 树

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

如果你对数据库或高级数据结构感兴趣,请研究如下数据结构:B树,红黑树,堆,伸展树。

11.5 MapReduce

分布式算法非常适合用于在短时间内完成海量工作,其中的MapReduce基于两个简单的理念:映射(map)函数和归并(reduce)函数。

11.6 布隆过滤器和HyperLogLog

布隆过滤器提供了解决之道。布隆过滤器是一种概率型数据结构,它提供的答案有可能不对,但很可能是正确的。为判断网页以前是否已搜集,可不使用散列表,而使用布隆过滤器。使用散列表时,答案绝对可靠,而使用布隆过滤器时,答案却是很可能是正确的。

11.8 局部敏感的散列算法

希望散列函数是局部敏感的。在这种情况下,可使用Simhash。如果你对字符串做细微的修改,Simhash生成的散列值也只存在细微的差别。

发表评论

您的电子邮箱地址不会被公开。