这本自买回来，就被我反反复复翻看，却总是看了一半忘了看到具体哪儿，而从头看起的算法类书籍。
现在，终于被我看完了。遂有此笔记。

  • 仅当列表是有序的时候，二分查找才管用

  • 大 O 表示法指出了算法运行时间的增速

  • 算法运行时间是从其增速的角度度量的

    Leigh Caldwell 在 Stack Overflow 上说的一句话，“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”

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

  • 优化递归的调用栈，有 2 种方法

    • 重新编写代码，转而使用循环
    • 使用尾递归。这是一个高级的主题，不在本书的讨论范围内，另外，并非所有的语言都支持尾递归。

  • 编写涉及数组的递归函数的时候，基线条件通常是数组为空或只包含一个元素。

    Haskell 等函数式编程语言就没有循环，因此你只能使用递归来编写这样的函数。如果你对递归有深入的认识，函数式编程语言学习起来将更加容易。如果你喜欢递归或者想学习一门新语言，可以研究一下 Haskell。

  • 散列表要避免冲突，需要有：

    • 较低的装填因子
    • 良好的散列函数

  • 有向图中的边为箭头，箭头的方向指定了关系的方向。无向图中的边不带箭头，其中的关系是双向的。

  • 广度优先搜索求最短路径，对于检查过的点，务必不要再去检查，否则会导致无限循环。

  • 在无向图中，每条边都是一个环。迪杰斯特拉算法只能用于有向无环图 (directed acyclic graph, DAG)，如果有负权边，就不能使用迪杰斯特拉算法。

  • 在有负权边的图中，要求最短路径，需要用到贝尔曼 - 福德算法 (Bellman-Ford algorithm)

  • 贪心算法的理念：每步都采取最优解。每步都选择局部最优解，最终得到的就是全局最优解。

  • 判断是否是 NP 完全问题

    • 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
    • 涉及 “所有组合” 的问题通常是 NP 完全问题。
    • 不能将问题分成小问题，必须考虑各种可能的情况。这可能是 NP 完全问题。
    • 如果问题涉及序列，（如旅行商问题中的城市序列）且难以解决，它可能就是 NP 完全问题。
    • 如果问题涉及集合 (如广播台集合)，且难以解决，它可能就是 NP 完全问题。
    • 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是 NP 完全问题。

  • 对于 NP 完全问题，还没有找到快速解决方案。

  • 面临 NP 完全问题，最佳的做法是使用近似算法。

  • 仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。

  • 每种动态规则解决方案都涉及网格。

  • 没有放之四海皆准的计算动态规划的公式，动态规划是一门艺术。

  • git diff 命令指出两个文件的差异，使用的就是动态规划实现的。

  • 布隆过滤器是一个概率型数据结构，它提供的答案有可能不对，但很可能是正确的。布隆过滤器非常适合用于不要求答案绝对准确的情况。

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

  • 当前最安全的密码散列函数是 bcrypt，但没有任何东西是万无一失的。

  • SHA 散列函数是局部不敏感的，有一个字符变化，都会导致其散列值截然不同。有时候希望散列函数是局部敏感的。在这种情况下，可使用 Simhash。如果你对字符串做细微的修改，Simhash 生成的散列值也只存在细微的差别。这让你能够通过比较散列值来判断两个字符串的相似程度。需要检查两项内容的相似程序时，Simhash 很有用。

    • Google 使用 Simhash 来判断网页是否已搜集。
    • 老师可以使用 Simhash 来判断学生的论文是否是从网上抄的。
    • Scribd 允许用户上传文档或图书，以便与人分享，但不希望用户上传有版权的内容。这个网站可使用 Simhash 来检查上传的内容是否与出版的小说类似，如果类似，就自动拒绝。