图解算法读书笔记

第3章-递归

• 递归只是让解决方案更清晰，并没有性能上的优势。“如果使用循环性能可能更高；如果使用递归，程序可能更容易理解，如果选择要看什么对你来说更重要”

第4章- 快速排序

• 分而治之（divide and conquer，D&C）
• D&C的工作原理：
  1、找出基线条件；（基线条件通常是数组为空或者只包含一个元素）
  2、确定如何缩小问题的规模，使其慢慢靠近基线条件，最终符合基线条件

第5章- 散列表

• 填装因子 （已使用的元素/字典总长度）
• 一般填装因子超过0.7就要 调整散列表的长度了
• 因为键名唯一性，一般常用于缓存

第6章- 广度优先搜索

• breadth-first search BFS，广度优先搜索
• BFS主要用来解决两种问题：1、从节点A出发，有前往节点B的路径吗？2、从节点A出发，前往节点B的哪条路劲最短？
• 这是一种图算法，图由节点(node)和边(edge)组成
• 广度优先最明显的特征就是广
• 图的实现：一般由散列表和列队组成
• 有向图：A→B，单向指向
• 无向图：A⇄ B，双向流动
• 拓扑排序：如果任务A依赖于任务B，那么A就必须在B后面

第7章- 狄克斯特拉算法

第8章- 贪婪算法

第9章- 动态规划

第10章 - K最近邻算法