算法图解第11章—未介绍的10种算法

  1. 数

    二叉查找数（binary search tree）
    二叉查找数的插入和删除操作操作的速度比有序数组要快的多。
    如果你对数据库和高级数据结构感兴趣，可以研究B数、红黑树、堆、伸展树。

  2.  反向索引

    常用于创建搜索引擎

  3. 傅立叶变换

    能告诉你其中包含哪些成分
    能够将歌曲分解为不同的频率，常用来压缩音乐。
    JPG 也是一种压缩格式。
    还被用来地震预测和DNA分析。

  4. 并行算法

    在多个内核种并行地执行，但是速度的提升并非线性的。
    因为并行性管理开销和负载均衡。

  5. MapReduce

    比较流行的是分布式算法，可让算法在多台计算机上运行。
    适合于在短时间内完成海量工作，其中的 MapReduce 基于两个原理：映射（map）函数和归并（reduce）函数。

    映射函数

    const arr1 = [1,2,3,4,5];

let arr2 = arr1.map((item) => {
  return item*2
})

console.log('arr2:',arr2);
//arr2: [ 2, 4, 6, 8, 10 ]

    但如果执行的操作需要更长的时间，就需要有100台计算机，而 map 能够自动将工作分配给这些计算机去完成。这就是 MapReduce 中“映射”部分基本的理念。

    归并函数

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

    let arr3 = 0;

arr1.map((item) => {
  arr3+=item
})

console.log(arr3);
//15

  6. 布隆过滤器和HyperLogLog

    布隆过滤器是一种概率型数据结构。
    使用散列表时，答案绝对可靠，而使用布隆过滤器时，答案却是很可能正确的。
    缺点：
    – 可能出现错报的情况，如google可能指出“这个网站已搜集”，但实际上并没有搜集。
    – 不可能出现漏报的情况，如果过滤器说“这个网站未搜集”，就肯定未搜集。
    优点：在于占用的存储空间很少，非常适用于不要求答案绝对准确的情况。
    HyperLogLog 是一种类似于布隆过滤器的算法。
    近似的计算集合中不同的元素数，也不能给出准确的答案，而占用内存空间却少很多。

  7.  SHA算法

    有一种散列函数是安全散列算法（SHA）函数。给定一个字符串，SHA 返回其散列值。
    可用于比较文件、检查密码。

  8. 局部敏感的散列算法

    SHA是局部不敏感的
    局部敏感的散列算法，修改字符串中的一个字符，再计算其散列值，结果将截然不同。

  9. Diffie_Hellman 密钥交换

    公钥和私钥
    只要只有你知道私钥，就只有你才能解密消息。

  10. 线性规划

    使用 Simplex 算法
    用于在给定约束条件下最大限度地改善指定的指标。