算法图解 - K 最近邻算法

K 最近邻 (K-nearest neighbours, KNN) 算法

1. 特征抽取

  • 抽取特征

  • 根据特征绘图

  • 计算距离

    • 使用毕达哥拉斯公式

      (x1−x2)2+(y1−y2)2\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}

    • 特征更多时仍然使用相同的计算公式

      (a1−a2)2+(b1−b2)2+(c1−c2)2+(d1−d2)2+(e1−e2)2\sqrt{(a_1 - a_2)^2 + (b_1 - b_2)^2 + (c_1 - c_2)^2 + (d_1 - d_2)^2 + (e_1 - e_2)^2}

  • 结果越小则表示特征越相似

算法图解 动态规划

背包问题

假设你是一个小偷，背着一个可装 4 磅东西的背包。

  • 音响 3000 美元 4 磅
  • 笔记本电脑 2000 美元 3 磅
  • 吉他 1500 美元 1 磅

简单算法

列出所有可能的组合，并找出价格最高的组合。

这样可行，但是速度非常慢。算法的运行时间为 O(2n)O(2^n)。

算法图解 贪婪算法

教室调度问题

假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。

课程 开始时间 结束时间
美术 09:00 AM 10:00 AM
英语 09:30 AM 10:30 AM
数学 10:00 AM 11:00 AM
计算机 10:30 AM 11:30 AM
音乐 11:00 AM 12:00 AM
算法图解 - 散列表

散列函数

  • 将输入映射到数字

  • 散列函数必须满足以下要求

    1. 它必须是一直的。即相同的输入总是映射到相同的数字。

    2. 它应将不同的输入映射到不同的数字。

散列表 (hash table)

  • 结合使用散列函数和数组

  • 散列表也被成为散列映射,映射,字典和关联数组.

  • 散列表适用于

    1. 模拟映射关系

    2. 防止重复

    3. 缓存/记住数据,以免服务器再通过处理还生成它们

算法图解 - 狄克斯特拉算法

若图中的边加了权值，如何找出权值最小的路径? => 狄克斯特拉算法 (Dijkstra's algorithm)

步骤

  1. 找出 "最便宜" 的节点。

  2. 更新该节点的邻居的开销 (为了计算最终路径，需要保存到达该节点的最小开销时的父节点)。

  3. 重复这个过程，直到对图中的每个节点都这么做了。

  4. 计算最终路径 (根据保留的父节点生成最终路径)。

术语

  • 权重 (weight)

  • 非加权图 (unwighted graph) => 广度优先搜索

  • 加权图 (weighted graph) => 狄克斯特拉算法

  • 狄克斯特拉算法只适用于有向无环图 (directed acyclic graph，DAG)

算法图解 - 广度优先搜索

最短路径问题 (shortest-path problem)

  • 解决最短路径问题的算法被称为广度优先搜索

图

  • 图模拟一组连接

  • 图由 节点 (node) 和 边 (edge) 组成

  • 一个节点可能于众多节点直接连接，这些节点被称为 邻居

  • 分为有向图 (directed graph) 和无向图 (undirected graph)

算法图解 - 选择排序

数组

  • 优点

    • 可以随机读取数据

  • 缺点

    • 增加和删除性能很差

链表

  • 优点

    • 增加和删除很方便，只需要修改相邻的数据即可

  • 缺点

    • 必须先访问前一个数据才能知道后一个数据的位置

选择排序

  • 遍历列表找出第一条数据，找出第一条数据，再遍历剩下的数据，找出第二条数据，以此类推，找出所有的数据

  • 运行时间为 O(n2)O(n^2)

算法图解 - 递归

递归

  • 函数调用自己，既是递归

  • 每个递归函数都有两部分：基线条件 ( base case ) 和递归条件 ( recursive case )

栈

  • 栈只有两个操作

    1. 压入（插入）

    2. 弹出（删除并读取）

  • 后进先出 ( Last In First Out, LIFO )

算法图解 - 快速排序

分而治之

  • 分而治之（divide and conqure，D&C） -- 一种著名的递归式问题解决方法

  • 使用 D&C 解决问题的过程包含两个步骤

    1. 找出基线条件，这种条件必须尽可能简单

    2. 不断将问题分解（或者说缩小规模），直到符合基线条件

快速排序

  • 工作原理

    1. 从数组中选择一个元素，这个元素被称作基准值

    2. 找出比基准值小的元素及比基准值大的元素，这被称为分区（partitioning）

    3. 对 2 中找到的比基准值小的元素和比基准值大的元素分别重复执行 1，2 步骤，直到数组的长度小于 2

    用 FlowChart 画了一个流程图，感觉不是很匹配，先凑活着看吧.

  • 大 O 表示法

    • 快速排序的最糟糕情况下，运行时间为 O(n2)O(n^2)

    • 在平均情况下，运行时间为 O(nlog2n)O(n log_2 n)

    • 只要每次随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为 O(nlog2n)O(n log_2 n)

  • 快速排序是最快的排序算法之一，也是 D&C 的典范

算法图解 - 大 O 表示法

大 O 表示法

大 O 表示法是一种特殊的表示法，指出了算法的速度有多快。大 O 表示法指出了最糟情况下的运行时间。

一些常见的大 O 运行时间：

  1. O(log2n)O(log_2 n) 也叫对数时间

  2. O(n)O(n) 也叫线性时间

  3. O(n∗log2n)O(n * log_2 n)

  4. O(n2)O(n^2)

  5. O(n!)O(n!) n 的阶乘