《算法图解》

发表于 | 分类于 | 阅读 次
字数统计: 1.6k | 阅读时长 ≈ 5 
这几天看完了《算法图解》这本书，确实这是一本好的算法入门书。在此记录一些书中的知识点。
  1. 算法运行时间并不以秒为单位，用大O表示法表示，是从其增速的角度度量的。算法的速度指的并非时间， 而是操作数的增速。谈论算法的速度时， 我们说的是随着输入的增加， 其运行时间将以什么样的速度增加。大O表示法指出了最糟情况下的运行时间。比如把一张正方形的纸平均裁成16份，一种方式是算出每一份的大小，一份一份的裁，一共要操作16次。这种裁法用算法时间O(n)来表示,也称线性时间,另一种方法就是对折4次再裁就能得到均分的16份，这种操作数只需4次，用大O表示法O(log n )，也称对数时间。O(log n )比O(n )快， 当需要搜索的元素越多时， 前者比后者快得越多。
    （1） O (log2 n )， 也叫对数时间 ， 这样的算法包括二分查找。
    （2） O (n )， 也叫线性时间 ， 这样的算法包括简单查找。
    （3） O (n * log2 n )， 这样的算法包括快速排序——一种速度较快的排序算法。
    （4） O (n 2 )， 这样的算法包括选择排序——一种速度较慢的排序算法。
    （5） O (n !)， 这样的算法包括旅行商问题的解决方案——一种非常慢的算法。

  2. 计算机内存犹如一大堆抽屉。需要存储多个元素时，可使用数组或链表。数组的元素都在一起，所以读取特别快。链表的元素是分开的，其中每个元素都存储了下一个元素的地址，所以插入和删除特别快。

  3. 栈有两种操作： 压入和弹出。递归指的是调用自己的函数，每个递归函数都有两个条件： 基线条件和递归条件。基线条件用来结束递归，递归条件用来调用自己。比如一个倒计时3 2 1 方法：

    1
    2
    3
    4
    5
    6
    7
    function countdown(i){
      console.log(i)
      if (i <= 0) ←------基线条件
      return
      else ←------递归条件
      countdown(i-1)
    }

  4. 分而治之 （divide and conquer， D&C） ——一种著名的递归式问题解决方法。D&C将问题逐步分解。 使用D&C处理列表时， 基线条件很可能是空数组或只包含一个元素的数组。实现快速排序时， 请随机地选择用作基准值的元素。 快速排序的平均运行时间为O(n log n )。大O表示法中的常量有时候事关重大， 这就是快速排序比合并排序快的原因所在。

  5. 散列表也就是哈希表。你几乎根本不用自己去实现散列表， 因为你使用的编程语言提供了散列表实现。散列表是一种功能强大的数据结构，其操作速度快， 还能让你以不同的方式创建数据模型。比如我们常用的js对象就是基于散列表实现的。

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

  7. 广度优先搜索用于在非加权图中查找最短路径（比如地图中寻找最短路径，不考虑其他情况）。狄克斯特拉算法用于在加权图中查找最短路径（当路上堵车或者其他情况，每段路径花费的时间不同，时间就是加权）。仅当权重为正时狄克斯特拉算法才管用。如果图中包含负权边（比如我想用华为换我弟的iPhone8，我弟说可以直接换，但是我又可以用华为加1000元换iphoneX,我弟又愿意用iPhone8加1500元换iPhone X，这样我还能赚500元，如果用狄克斯特拉算法就会选择直接换了），请使用贝尔曼-福德算法。

  8. 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。贪婪算法很简单： 每步都采取最优的做法。用专业术语说， 就是你每步都选择局部最优解 ， 最终得到的就是全局最优解。对于NP完全问题， 还没有找到快速解决方案。面临NP完全问题时， 最佳的做法是使用近似算法。贪婪算法易于实现、 运行速度快， 是不错的近似算法。

  9. 需要在给定约束条件下优化某种指标时， 动态规划很有用。问题可分解为离散子问题时， 可使用动态规划来解决。每种动态规划解决方案都涉及网格。单元格中的值通常就是你要优化的值。每个单元格都是一个子问题， 因此你需要考虑如何将问题分解为子问题。没有放之四海皆准的计算动态规划解决方案的公式。

  10. K最近邻算法：用于推荐系统。KNN用于分类和回归， 需要考虑最近的邻居。分类就是编组。回归就是预测结果（如数字） 。特征抽取意味着将物品（如水果或用户） 转换为一系列可比较的数字。能否挑选合适的特征事关KNN算法的成败。

  11. 其他还有树、反向索引、傅里叶变换、并行算法、线性规划等等复杂的算法，都是需要单独去研究学习的。