• 二分查找

    • 不同于顺序查找,二分查找能显著降低查找次数

    • 二分查找时间复杂度为 O(logn) 「理解为二叉树的层级」

      • 大 O 表示法表示的是算法运行时间的增速(或者趋势?);举例 O(n) 即表示线性增速,O(logn) 表示对数增速,二者相比之下,数据越多后者相较前者越快。
      • 大 O 表示法指示出了最糟的运行时间
    • 二分查找只在「查找对象有序」的时候才有用

    • 二分查找的时间为「对数时间logn」,对应于「线性时间n」

  • 算法的速度

    • 算法的速度指的并非时间,而是操作数的增速
    • 讨论算法的速度时,我们说的是随着输入的增加,其运行时间以什么样的速度增加(增长趋势?)
    • 算法的运行时间用大O表示法表示。
    • O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快得越多。
  • 选择排序

    • 数组:数组各个元素之间内存地址连续
      • 存储的时候为了防止溢出一种解决方法是申请更多的空间,但是多余的空间可能用不到以及超过上限还是会溢出
      • 优势:读取速度快,可以以 O(1) 访问任意一个元素 [数组下标]
      • 缺点:内存连续,插入时需要移动元素
    • 链表:链表元素可以存储在内存任何位置 [广义的任何位置]
      • 优势:在插入元素不用移动其他元素,复杂度 O(1)
      • 缺点:不能直接访问最后元素
    • 选择排序
      • 一句话总结:每次选取后面最大(或小)的值放入前面
      • 选择排序时间复杂度为 O(n^2)
        • 大 O 表示法一般忽略计算前面的常数
  • 递归
    • 递归是自己调用自己的函数。
    • 递归只是让解决方案更清晰,并没有性能上的优势,有时候循环性能更好。
    • 编写递归函数时必须告诉他何时停止。
    • 递归函数的两部分:
      • 递归条件(recursive case):递归函数调用自己。
      • 基线条件(base case):递归函数不再调用自己,避免死循环。
    • 递归使用的是「栈」结构:第一个函数内调用的函数压在栈顶,以此类推。
    • 栈结构可能很长,会使用很多的内存(调用了大量函数),改善方法如下:
      • 重写代码,使用循环而不是递归。
      • 使用「尾递归」,不在此书范围。
    • ps.编写涉及数组的递归,基线条件通常是数组为空或者只有一个元素。
  • 快速排序

    • 快速排序使用著名的递归式问题解决方法 — 分而治之(devide and conquer,D&C)

    • D&C 分治解决问题过程[工作原理]:

      • 找出基线条件,必须尽可能简单
      • 不断将问题分解,缩小规模,直至符合基线条件
    • 使用 D&C 的基线条件通常为数组为空或者只有一个元素

    • 快速排序算法原理

      • 首先从数组中找到一个基准值(pivot),一般选择第一个元素[建议随机选择]
      • 将原数组分为两个子数组:(左)小于基准值的元素,(右)大于基准值的元素 [也可以相反, 左大右小]
      • 对两个子数组进行快速排序
    • 快速排序不检查数组是否有序,速度取决于选择的基准值

    • 当每次选择最小或最大的值为基准时为最糟情况[调用栈最长 O(n)],每次选择中间值为最佳[调用栈最短 O(logn)]。

    • 快速排序平均时间复杂度为 O(nlogn)

      • 平均调用栈高度为 O(logn)
      • 每一层调用时间复杂度为 O(n)
    • 快速排序算法是最快的排序算法之一

  • 散列表

    • 散列函数
      • 作用:将输入「映射」到数字
      • 散列函数要求:必须一致,不同输入必须映射到不同数字。
      • 散列函数特点
        • 散列函数总是将同样的输入映射到相同的索引
        • 散列函数将不同的输入映射到不同的索引
        • 散列函数知道数组有多大,只返回有效的索引
    • 可以将散列表用作缓存增加查询速度
    • 散列表适合模拟映射关系,防止重复和缓存/记住数据
    • 冲突
      • 可以使用链表解决冲突
      • 一个「冲突少的」散列函数很重要:理想情况下将键均匀的映射到散列表的不同位置。
      • 如果解决冲突的链表很长,速度会下降,但是一个好的散列函数很少导致冲突。
    • 性能

      enter image description here

      • 平均情况下散列表具有数组的查找速度和链表的插入删除速度,但是最糟情况下,散列表的各种速度都慢得多[冲突多?]
      • 避免冲突需要有以下两点
        • 较低的装填因子
          • 装填因子 = 散列表包含的元素个数 / 位置总数
          • 装填因子大于1表示元素的数量超过散列表的数量
          • 一旦装填因子开始增大,就需要在散列表中添加位置 [称为调整长度]
          • 理论上,装填因子越小冲突概率越小
        • 良好的散列函数
          • 良好的散列函数让数值均匀分布;糟糕的散列函数让数值扎堆
  • 广度优先搜索

    • 解决最短路径的算法被称为广度优先搜索
    • 广度优先搜索解决可以解决两类问题:
      • 第一类问题:从节点 A 出发有通往 B 的路径吗 [存在问题]
      • 第二类问题:从节点 A 出发,通往节点 B 的哪条路径最短 [最短问题]
    • 一句话概括:广度优先搜索从二叉树自顶向下搜索,经过的层数即是最短路径长度.
    • 队列

      队列是一个先进先出的结构,和栈类似,不过是两端操作,一段入队,一端出队。

    • 广度优先搜索依赖有向图

    • 广度优先搜索沿着边前行,所以广度优先搜索的时间复杂度至少是O(边数),但是还使用了队列,所以将每个人添加到队列中的总时间为 O(人数),所以广度优先搜索运行的总时间是 O(人数 + 边数), 通常写作 O(V+E) [V → vertice; E → edge]
    • 请注意,广度优先搜索遇到环的情况可能会死循环,所以切记检查过的节点做好标记
  • 迪杰斯特拉算法
    • 狄克斯特拉算法适用于加权有向无环图
    • 狄利斯特拉算法权重不能为负数
    • 狄克斯特拉算法步骤:
      • (1) 找出“最便宜”的节点,即可在最短时间内到达的节点。
      • (2) 更新该节点的邻居的开销。
      • (3) 重复这个过程,直到对图中的每个节点都这样做了。
      • (4) 计算最终路径。
    • 总结:通过不断更新初始节点到其他节点的最短权重,来找到到目的节点的最短权重
  • 贪婪算法
    • 贪婪算法的优点:简单易行
    • 以教室选课为例:选择最早开始的课,然后以这节课结束为开始,选择之后最早开始的课,重复,这就是贪心算法。
    • 贪心算法只能给出策略,有时候不能得到最优解
    • 使用贪婪算法可以得到近似解,以书中,州广播电台举例
      • 首先选择覆盖最多未覆盖的州
      • 重复第一步知道覆盖所有州
      • 这样可以得到近似解并且速度也不慢 O(n^2)
    • 面对旅行商类似问题,最好的方法是使用近似解,这样虽然得不到最优解,但是近似解与最优解差距小,速度却快了很多。
  • 动态规划

    • 相对于贪心算法,动态规划能通过细化找到最优解
    • 动态规划要么考虑整件商品要么不拿
    • 以书中小偷例子实现动态规划算法:

      enter image description here

      • 吉他:重量一磅,价值1500; 音响:重量4磅,价值3000;笔记本电脑:重量3磅,价值2000
      • 从第一行开始,只能选吉他,所以无论背包大小多大,最大价值都是1500
      • 第二行,只能选吉他和音响,但是音响4磅,所以3磅之前只能选择吉他,到第四磅的时候,选择音响能够得到新的最优解3000磅[只选音响,正好4磅]
      • 第三行,三种都可以选择,但是笔记本3磅,所以一二磅之前都不变,到第三磅的时候可以选择笔记本电脑出现三磅的最优解,第四磅的时候可以选择笔记本电脑和吉他出现新的全局最优解3500,以此得出最优解。
    • 动态规划就是类似上面,将事项细分,由此推出全剧最优解。
    • 动态规划可以解决很多问题,但是要求每个子问题是离散的才行,即每个问题与其他无关,动态规划才管用
    • 动态规划需要根据不同的问题制定思路,没有通用的解决方法
  • K近邻算法(KNN)
    • 简单解释:未知类别分类的时候取离该点最近K个点的类别,最多的类别就是该类的类别
    • K近邻算法一般用于分类问题
    • 问题:如何确定两点(类别?)之间的相似程度?
      • 特征抽取
      • 特征绘图,将原始点抽取特征后绘制在图标或者坐标轴上,量化类别差距
    • KNN 用于回归
      • 简单解释:通过最近类别的 K 个点的平均值来确定该点的值,这就是回归
      • 做法:与之前 KNN 分类一致,首先确定最近 K 个点,然后取得 K 个点的值,取平均即为该点的值,与分类不同的是,分类是编组,二回归是预测结果。
    • 如何挑选合适的特征
      • 必须选择与问题联系紧密的特征
      • 不偏不倚的特征
    • 能否挑选合适的特征决定 KNN 的成败