tangdw

Appearance

《算法图解》笔记 ​

使用 js 实现书中 py 伪代码、习题

算法简介 ​

二分查找 ​

  • 情景：有序列表 + 有反馈（判断在左/右侧）

  • 复杂度：最糟糕的情况下需要判断 log2^n 次 -> O(logn)

js
const binary = (list, tar) => {
  let left = 0
  let right = list.length - 1
  while (left <= right) {
    const mid = Math.ceil((left + right) / 2)
    if (list[mid] === tar) {
      return mid
    } else if (list[mid] > tar) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return -1
}

binary([1, 3, 5, 7, 9], 7)

  • 常见大 O 运行时间 O(logn) 、 O(n) 、 O(n*logn) 、 O(n2) 、 O(n!)

    • 算法的速度指的是：随着输入的增加，其运行时间（操作次数）的增速（以什么样的速度增加）

选择排序 O(n²) ​

  • 数组：长度变化时将重新分配空间

  • 链表：无需修改内存空间（前一个元素存放后一个元素的地址）

  • 操作算法速度：读取、插入、删除 -> 大 O

js
const findSmallIndex = (list) => {
  let rtn = 0
  for (let i = 1; i < list.length; i++) {
    if (list[i] < list[rtn]) {
      rtn = i
    }
  }
  return rtn
}
const selectSort = (list) => {
  const rtn = []
  while (list.length) {
    const i = findSmallIndex(list)
    rtn.push(list[i])
    list.splice(i, 1)
  }
  return rtn
}

selectSort([5, 3, 6, 2, 10])

递归 ​

  • 要素

    1. 基线条件：函数不再调用自己
    2. 递归条件：函数调用自己

  • 调用栈

    • 在一个函数内调用另一个函数时，当前函数暂停并处于未完成状态
    js
    const fact = (x) => {
  if (x === 1) {
    // -- 基线
    return 1 // 开始弹出
  } else {
    // -- 递归
    return x * fact(x - 1) // 压入
  }
}

快速排序 O(nlogn) ​

分而治之 ​

  1. 找出基线条件，这种条件必须尽可能简单
  2. 不断将问题分解（或者说缩小规模），直到符合基线条件
js
const quickSort = (list) => {
  if (list.length < 2) {
    return list
  } else {
    // 性能与所取基准值 mid 相关，最佳情况（也是平均情况）复杂度 O(nlogn)
    const mid = list[0],
      left = [],
      right = []
    for (let i = 1; i < list.length; i++) {
      // O(n)
      const tar = list[i]
      if (tar <= mid) {
        left.push(tar)
      } else {
        right.push(tar)
      }
    }
    return [...quickSort(left), mid, ...quickSort(right)] // O(logn) 调用栈深度
  }
}

quickSort([10, 5, 2, 3])

散列表 O(1) ​

  1. 填装因子 元素数/位置总数 -> 要低
  2. 散列函数 -> 良好的散列函数使元素分布均匀

广度优先搜索 O(V + E) 顶点数 + 边数 ​

解决最短路径问题

  • 首先使用图来建立问题模型（模拟不同东西是如何连接的）
    • 一度关系：朋友
    • 二度关系：朋友的朋友
    • ...
  • 寻找芒果经销商 -> 'thom'
js
const search = (graph) => {
  const queue = [...graph.you] // 初始队列 -> 一度关系
  const checked = []
  while (queue.length) {
    const tar = queue.shift() // 先进先出
    if (checked.indexOf(tar) === -1) {
      if (tar === 'thom') {
        return true // 找到了
      } else {
        queue.push(...graph[tar]) // 将 “下一级关系” 添加到队列中
        checked.push(tar) // 可能再次出现（多重关系） -> 避免重复检查
      }
    }
  }
  return false
}

// 描述关系图
const graph = {
  you: ['bob', 'alice', 'claire'], // 一度关系
  bob: ['anuj', 'peggy'],
  alice: ['peggy'],
  claire: ['jonny', 'thom'],
  anuj: [],
  peggy: [],
  jonny: [],
  thom: [],
}

search(graph)

狄克斯特拉算法 ​

加权图中最短路径问题

  1. 找出最 “便宜” 的节点（前往该节点时间最短）
  2. 对该节点的邻居，检查是否有前往它们更短的路径，如果有就更新其开销
  3. 重复这个过程，直到所有的节点都处理过了
  4. 计算最终路径
js
// 描述加权图，求 start -> end 的最短路径
const graph = {
  start: { a: 5, b: 2 },
  a: { c: 4, d: 2 },
  b: { a: 8, d: 7 },
  c: { d: 6, end: 3 },
  d: { end: 1 },
  end: {},
}
// 描述开销
const costs = {
  a: 5,
  b: 2,
  c: 1 / 0, // 暂时无法直接得出的用无穷大表示
  d: 1 / 0,
  end: 1 / 0,
}
// 描述节点关系（用于生成最终路线）
const parents = {
  a: 'start',
  b: 'start',
  c: 'a',
  d: 'b',
  end: 'c',
}
// 寻找最便宜节点
const findLow = (costs, checked) => {
  let low = 1 / 0
  let lowNode = null
  Object.keys(costs).forEach((x) => {
    if (costs[x] < low && checked.indexOf(x) === -1) {
      low = costs[x]
      lowNode = x
    }
  })
  return lowNode
}

const proessed = []
let node = findLow(costs, proessed)

// 检查它的邻居节点，更新开销、路径
while (node) {
  const bors = graph[node]
  Object.keys(bors).forEach((x) => {
    const borCost = costs[node] + bors[x]
    // 如果经过它到邻居节点的开销，比这个邻居当前开销少，那么更新邻居的开销、路径
    if (borCost < costs[x]) {
      costs[x] = borCost
      parents[x] = node
    }
  })
  proessed.push(node)
  // 继续处理最便宜的节点
  node = findLow(costs, proessed)
}

// 由节点关系生成路线
let line = ['end']
let nextNode = parents['end']

while (nextNode !== 'start') {
  line.unshift(nextNode)
  nextNode = parents[nextNode]
}

line.unshift('start')

console.log(line)

贪婪算法 ​

  • NP 完全问题：没有快速算法的问题
    • 随着元素的增加，速度会变得非常慢 O(n!) 或 幂级
    • 涉及序列问题
    • 涉及集合问题
    • 不能将问题分成小问题
  • 贪婪算法 O(n²)
    • 每一步都采用最优解，那么最终得到的就是全局最优解
    • 只是一种近视算法，并不是精确算法

动态规划 ​

将问题分解成小问题，并先着手解决这些小问题（如果这些子问题是离散的，没有相互依赖）

  • 背包问题
js
const table = [] // 待填充的网格
const UNIT = 1 // 网格细粒度 -> 公因子
const COL = 6 // 网格列

// 以下是每种物品占用重量、价值
const list = [
  { name: '水', use: 3, value: 10 },
  { name: '书', use: 1, value: 3 },
  { name: '食物', use: 2, value: 9 },
  { name: '夹克', use: 2, value: 5 },
  { name: '相机', use: 1, value: 6 },
]

// 填充物品合并
const merge = (a, b) => {
  const rtn = {}
  for (const k in a) {
    rtn[k] = a[k] + b[k]
  }
  return rtn
}
// 从最小的问题开始 优化单元格的值
for (let i = 0; i < list.length; i++) {
  const row = []
  const item = list[i]
  for (let j = 0; j < COL; j++) {
    // 此级别背包已装下的物品
    const prev = (table[i - 1] && table[i - 1][j]) || {}
    // 如果装了当前物品，的价值
    const itemValue = item.use <= (j + 1) * UNIT ? item.value : 0
    // 如果装了当前物品，剩余空间可装下的物品
    const rest = (table[i - 1] && table[i - 1][j - item.use / UNIT]) || {}
    // 新方案的总价值更高
    if (itemValue + (rest.value || 0) > (prev.value || 0)) {
      row.push(rest.name ? merge(item, rest) : item) // 使用新方案填充当前网格
    } else {
      row.push(prev) // 仍然采用上次方案填充
    }
  }
  table.push(row)
}

console.log(table[list.length - 1][COL - 1])

K 最邻近算法 ​

  • KNN 算法
    • 取对象的 3 个邻居，对象的类别归为多数那一类
  • 分类
    • 抽取多维度特征，计算两点的多维空间距离，取距离最短的相似点
  • 回归
    • 使用历史数据预测结果

其他 ​

  • 二叉树：查找、插入、删除都是 O(logn)
  • 并行算法
    • 分布式算法 MapReduce
  • 检查密码
    • 存储 { 用户名：SHA }，使用散列函数（不可逆）比较 SHA 判断用户密码
  • 线性规划
    • 在给定的约束条件下最大限度的改善指定指标
    • 所有的图算法都可以用线性规划来实现，图只是其中一个子集

Copyright © 2016-present tangdw