其他算法简介

树

一个例子，每当用户登录Facebook时，Facebook都必须在一个庞大的数组中查找，核实其中是否包含指定的用户名。前面说过，在这种数组中查找时，最快的方式是二分查找，但问题是每当有新用户注册时，都必须将其用户名插入该数组并重新排序，因为二分查找仅在数组有序时才管用。

如果能将用户名插入到数组的正确位置就好了，这样就无需在插入后再排序。为此，有人设计了一种名为二叉查找树（binary search tree）的数据结构。

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

二叉查找树也存在一些缺点，例如，不能随机访问，就像不能这么说：“给我第五个元素。”在二叉查找树处于平衡状态时，平均访问时间也为O(log n)。

不平衡的树是向某个方向倾斜，因此性能不佳。也有一些处于平衡状态的特殊二叉查找树，如红黑树。

那在什么情况下使用二叉查找树呢？B树是一种特殊的二叉树，数据库常用它来存储数据。

反向索引

这里非常简单地说说搜索引擎的工作原理。假设你有三个网页，内容分别是：“Hi，There”，“Hi，Adit”，“There we go”。

我们根据这些内容创建一个散列表。这个散列表的键为单词，值为包含指定单词的页面。现在假设有用户搜索hi，在这种情况下，搜索引擎需要检查哪些页面包含hi。

搜索引擎发现页面A和B包含hi，因此将这些页面作为搜索结果呈现给用户。现在假设用户搜索there。你知道，页面A和C包含它。

这是一种很有用的数据结构：一个散列表，将单词映射到包含它的页面。这种数据结构被称为反向索引（inverted index），常用于创建搜索引擎。

傅里叶变换

对傅里叶变换有一个精妙的评价：“给它一杯冰沙，它能告诉你其中包含哪些成分”。换言之，给定一首歌曲，傅里叶变换能够将其中的各种频率分离出来。

傅里叶变换非常适合用于处理信号，可使用它来压缩音乐。

数字信号并非只有音乐一种类型。JPG也是一种压缩格式，也采用了刚才说的工作原理。傅里叶变换还被用来地震预测和DNA分析。

并行算法

在最佳情况下，排序算法的速度大致为O(n log n)。对数组进行排序时，快速排序的并行版本所需的时间为O(n)。

并行算法设计起来很难，要确保它们能够正确地工作并实现期望的速度提升也很难。

有一点是确定的，那就是速度的提升并非线性的，因此即便你的笔记本电脑装备了两个而不是一个内核，算法的速度也不可能提高一倍，其中的原因有两个。

并行性管理开销：假设你要对一个包含1000个元素的数组进行排序，如果让每个内核对其中500个元素进行排序，再将两个排好序的数组合并成一个有序数组，那么合并也是需要时间的。

负载均衡：假设你需要完成10个任务，因此你给每个内核都分配5个任务。但分配给内核A的任务都很容易，10秒钟就完成了，而分配给内核B的任务都很难，1分钟才完成。这意味着有那么50秒，内核B在忙死忙活，而内核A却闲得很！你如何均匀地分配工作，让两个内核都一样忙呢？

MapReduce分布式算法

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

映射函数：映射函数很简单，它接受一个数组，并对其中的每个元素执行同样的处理。

归并函数：归并函数可是将很多项归并为一项。映射是将一个数组转换为另一个数组，而归并是将一个数组转换为一个元素。

布隆过滤器和HyperLogLog

有一个庞大的集合，给定一个元素，你需要判断它是否包含在这个集合中。为快速做出这种判断，可使用散列表。

但是因此这个散列表非常大，需要占用大量的存储空间。

布隆过滤器是一种概率型数据结构，它提供的答案有可能不对，但很可能是正确的。使用散列表时，答案绝对可靠，而使用布隆过滤器时，答案却是很可能是正确的。

HyperLogLog是一种类似于布隆过滤器的算法。如果Google要计算用户执行的不同搜索的数量，或者Amazon要计算当天用户浏览的不同商品的数量，要回答这些问题，需要耗用大量的空间！

HyperLogLog近似地计算集合中不同的元素数，与布隆过滤器一样，它不能给出准确的答案，但也八九不离十，而占用的内存空间却少得多。

面临海量数据且只要求答案八九不离十时，可考虑使用概率型算法！

SHA算法

安全散列算法（secure hash algorithm，SHA）函数。给定一个字符串，SHA返回其散列值。

你可使用SHA来判断两个文件是否相同，这在比较超大型文件时很有用。假设你有一个4 GB的文件，并要检查朋友是否也有这个大型文件。为此，你不用通过电子邮件将这个大型文件发送给朋友，而可计算它们的SHA散列值，再对结果进行比较。

SHA还让你能在不知道原始字符串的情况下对其进行比较。

局部敏感的散列算法

SHA还有一个重要特征，那就是局部不敏感的。假设你有一个字符串，并计算了其散列值。如果你修改其中的一个字符，再计算其散列值，结果将截然不同！

有时候，你希望结果相反，即希望散列函数是局部敏感的。在这种情况下，可使用Simhash。如果你对字符串做细微的修改，Simhash生成的散列值也只存在细微的差别。这让你能够通过比较散列值来判断两个字符串的相似程度，这很有用！

Diffie-Hellman密钥交换

Diffie-Hellman算法解决了如下两个问题。

双方无需知道加密算法。他们不必会面协商要使用的加密算法。

要破解加密的消息比登天还难。

Diffie-Hellman使用两个密钥：公钥和私钥。有人要向你发送消息时，他使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。只要只有你知道私钥，就只有你才能解密消息！

Diffie-Hellman算法及其替代者RSA依然被广泛使用。

线性规划

线性规划用于在给定约束条件下最大限度地改善指定的指标。

所有的图算法都可使用线性规划来实现。线性规划是一个宽泛得多的框架，图问题只是其中的一个子集。

线性规划使用Simplex算法，这个算法比较复杂。