算法图解 8.3分
读书笔记 全书
Bear

I. 问题解决技巧:

  • 二分查找的速度比简单查找快得多
  • 0(log n)比0(n)快。需要搜索的元素越多,前者比后者快得越多
  • 算法运行时间并不以秒为单位
  • 算法运行时间是从其增速的角度度量的
  • 算法运行时间用大0表示法表示

II. 选择排序链表:linked list数组:array

  • 计算机内存犹如一大堆抽屉
  • 需要存储多个元素时,可使用数组或链表
  • 数组的元素都在一起
  • 链表的元素是分开的,其中每个元素都存储 下一个元素的地址
  • 数组的读取速度很快
  • 链表的插入和删除速度很快
  • 在同一个数组中,所有元素的类型都必须相同(都为int、double等)

III. 递归Recursion如果使用循环,程序的性能可能会更高。如果使用递归,程序可能更容易理解Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!每个递归函数都有两部分:

  • 基线函数base case:函数调用自己
  • 递归条件recursive case:函数不再调用自己,从而避免形成无限循环

调用栈call stack Resumé:

  • 递归指的是调用自己的函数
  • 每个递归函数都有两个条件:基线条件和递归条件
  • 栈有两种操作:压入和弹出
  • 所有函数调用都进入调用栈
  • 调用栈可能很长,这将占用大量的内存

IV. 快速排序分而治之(divide and conquer, D&C)

  1. 找出简单的基线条件
  2. 确定如何缩小问题的规模,使其符合基线条件

分区partitioning Resumé:

  • D&C 将问题逐步分解。使用D&C处理列表时,基线条件很可能是空数组或只包含一个元素的数组
  • 实现快速排序时,请随机选择用作基准值的元素。快速排序的平均运行时间为0(n log n)
  • 大0表示法中的常量有时候事关重大,这就是快速排序比合并排序快的原因
  • 比较简单查找和二分查找时,常量几乎无关紧要,因为列表很长时,0(log n)的速度比0(n)快

V. 散列表 hash table散列函数:将输入映射到数字散列表hash table

  • 模拟映射关系
  • 防止重复
  • 缓存/记住数据

冲突collision:给两个键分配的位置相同>>如果两个键分配的位置相同,就在这个位置存储一个链表 Resumé:几乎不用自己去实现散列表,因为你的编程语言提供了散列表实现。你可使用Python提供的散列表,并假定能够获得平均情况下的性能:常量时间

  • 你可以结合散列函数和数组来创建散列表
  • 冲突很糟糕,你应使用可以最大限度减少冲突的散列函数
  • 散列表的查找、插入和删除都非常快
  • 散列表适用于模拟映射关系
  • 一旦填装因子超过0.7,就应该调整散列表的长度
  • 散列表可用于缓存数据
  • 散列表非常适用于防止重复

VI. 广度优先搜索 Breath-first search, BFS找出两样东西之间的最短距离最短路径问题shortest-path problem图由节点node和边edge组成广度优先搜索可以回答两类问题:

  • 从节点A出发,有前往节点B的路径吗
  • 从节点A出发,前往节点B的哪条路径最短

队列queue

  • 队列:先进先出的数据结构First in First out, FIFO
  • 栈:后进先出的数据结构Last in First out, LIFO

拓扑排序 topological sorting

Resumé:

  • 广度优先搜索指出是否有从A到B的路径
  • 如果有,广度优先搜索将找出最短路径
  • 面临类似于寻找最短路径的问题时,可尝试使用图来建立模型,再使用广度优先搜索来解决问题
  • 有向图中的边为箭头,箭头的方向指定了关系的方向
  • 无向图中的边不带箭头,其中的关系是双向的
  • 队列是先进先出的FIFO
  • 栈是后进先出的LIFO
  • 你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径,因此搜索列表必须是队列
  • 对于检查过的人,务必不要再检查,否则可能导致无限循环

VII. 狄克丝特拉算法Dijkstra's algorithm权重weight;带权重的图是加权图 weighted graph;不带权重的图称为非加权图unweighted graph狄克丝特拉算法只适用于有向无环图directed acyclic graph, DAG贝尔曼——福德算法Bellman-Ford algorithmResumé:

  • 广度优先搜素用于在非加权图中查找最短路径
  • 狄克拉斯特算法用于在加权图中查找最短路径
  • 仅当权重为正时狄克拉斯特算法才管用
  • 如果图中包含负权边,请使用贝尔曼——福德算法

VIII. 贪婪算法 Greedy algorithm每步都选择局部最优解近似算法approximation algorithm阶乘函数factorial functionResumé:

  • 贪婪算法寻找局部最优解
  • 对于NP完全问题,还没有找到快速解决方案
  • 面临NP完全问题时,最佳的做法是使用近似算法
  • 贪婪算法易于实现、运行速度快,是不错的近似算法

IX. 动态规划Dynamic programming (DP)费曼算法Feynman algorithm

  1. 将问题写下来
  2. 好好思考
  3. 将答案写下来

Resumé:

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

X. K最近邻算法K-nearest neighbours, KNN余弦相似度cosine similarity光学字符识别OCR: optical character recognition朴素贝叶斯分类器Naive bayers classifierResumé:

  • KNN用于分类和回归,需要考虑最近的邻居
  • 分类就是编组
  • 回归就是预测结果(如数字)
  • 特征抽取意味着将物品转换为一系列可比较的数字
  • 能否挑选合适的特征事关KNN算法的成败

XI. 接下来如何做

  • 二叉查找树Binary search tree
  • 反向索引inverted index
  • 傅里叶变换
  • 并行算法
    • 分布式算法, e.g. MapReduce,基于映射map函数和归并reduce函数
  • 布隆过滤器和HyperLogLog
  • SHA(secure hash algorithm)算法:安全散列算法
  • Diffie-Hellman密钥交换
  • 线性规划:在给定约束条件下最大限度地改善指定的指标,simplex算法
0
《算法图解》的全部笔记 19篇
豆瓣
免费下载 iOS / Android 版客户端