算法图解

• 丽拉先生

  2019-04-19
  Facebook实际使用的是什么呢？很可能是十多个数据库，它们基于众多不同的数据结构：散列表、B树等。数组和链表是这些更复杂的数据结构的基石。
• 

  2018-04-18
  NP完全问题的简单定义是， 以难解著称的问题， 如旅行商问题和集合覆盖问题。 很多非常聪明的人都认为， 根本不可能编写出可快速解决这些问题的算法但如果要找出经由指定几个点的的最短路径， 就是旅行商问题——NP完全问题。 简言之， 没办法判断问题是不是NP完全问题， 但还是有一些蛛丝马迹可循的。元素较少时算法的运行速度非常快， 但随着元素数量的增加， 速度会变得非常慢。涉及“所有组合”的问题通常是NP完全问题。不能将问题分成小问题， 必须考虑各种可能的情况。 这可能是NP完全问题。如果问题涉及序列（ 如旅行商问题中的城市序列） 且难以解决， 它可能就是NP完全问题。如果问题涉及集合（ 如广播台集合） 且难以解决， 它可能就是NP完全问题。如果问题可转换为集合覆盖问题或旅行商问题， 那它肯定是NP完全问题。贪婪算法寻找局部最优解， 企图以这种方式获得全局最优解。对于NP完全问题， 还没有找到快速解决方案。面临NP完全问题时， 最佳的做法是使用近似算法。贪婪算法易于实现、 运行速度快， 是不错的近似算法。
• 

  2018-04-17
  广度优先搜索指出是否有从A到B的路径。如果有， 广度优先搜索将找出最短路径。面临类似于寻找最短路径的问题时， 可尝试使用图来创建模型， 再使用广度优先搜索来解决问题。有向图中的边为箭头， 箭头的方向指定了关系的方向， 例如，rama→adit表示rama欠adit钱。无向图中的边不带箭头， 其中的关系是双向的， 例如， ross - rachel表示“ross与rachel约会， 而rachel也与ross约会”。队列是先进先出（ FIFO） 的。栈是后进先出（ LIFO） 的。你需要按加入顺序检查搜索列表中的人， 否则找到的就不是最短路径， 因此搜索列表必须是队列。对于检查过的人， 务必不要再去检查， 否则可能导致无限循环。
• 

  2018-04-17
  散列表是一种功能强大的数据结构， 其操作速度快， 还能让你以不同的方式创建数据模型。 你可能很快会发现自己经常在使用它。你可以结合散列函数和数组来创建散列表。冲突很糟糕， 你应使用可以最大限度减少冲突的散列函数。散列表的查找、 插入和删除速度都非常快。散列表适合用于仿真映射关系。一旦填装因子超过0.7， 就该调整散列表的长度。散列表可用于缓存数据（ 例如， 在Web服务器上） 。散列表非常适合用于防止重复。
• 

  2018-04-17
  刚才你就打造了一个“Maggie”！ 你结合使用散列函数和数组创建了一种被称为散列表 （ hash table） 的数据结构。 散列表是你学习的第一种包含额外逻辑的数据结构。 数组和链表都被直接映射到内存， 但散列表更复杂， 它使用散列函数来确定元素的存储位置。在你将学习的复杂数据结构中， 散列表可能是最有用的， 也被称为散列映射、 映射、 字典和关联数组。 散列表的速度很快！ 还记得第2章关于数组和链表的讨论吗？ 你可以立即获取数组中的元素， 而散列表也使用数组来存储数据， 因此其获取元素的速度与数组一样快。
• 

  2018-04-16
  使用栈虽然很方便， 但是也要付出代价： 存储详尽的信息可能占用大量的内存。 每个函数调用都要占用一定的内存， 如果栈很高， 就意味着计算机存储了大量函数调用的信息。 在这种情况下， 你有两种选择。重新编写代码， 转而使用循环。使用尾递归 。 这是一个高级递归主题， 不在本书的讨论范围内。另外， 并非所有的语言都支持尾递归 递归指的是调用自己的函数。每个递归函数都有两个条件： 基线条件和递归条件。栈有两种操作： 压入和弹出。所有函数调用都进入调用栈。调用栈可能很长， 这将占用大量的内存。
• 

  2018-04-16
  编写递归函数时， 必须告诉它何时停止递归。 正因为如此， 每个递归函数都有两部分： 基线条件 （ base case） 和递归条件 （ recursivecase） 。 递归条件指的是函数调用自己， 而基线条件则指的是函数不再调用自己， 从而避免形成无限循环。
• 

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

  2017-09-01
  当前，我们获得的主要启示如下 算法的速度指的并非时间，而是操作数的增速。 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。 算法的运行时间用大O表示法表示。 O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。
• villim

  2017-09-01
  下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。 O(log n)，也叫对数时间，这样的算法包括二分查找。 O(n)，也叫线性时间，这样的算法包括简单查找。 O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。 O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。 O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
• villim

  2017-09-01
  大O表示法（稍后介绍）讨论运行时间时， log指的都是log2。使用大O表示法，这个运行时间为O(n)。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。 大O表示法让你能够比较操作数，它指出了算法运行时间的增速。