前言
- 问题解决技巧：分而治之 / 动态规划；贪婪算法
- 书目：Grokking algorithms: an illustrated guide for programmers and other curious people
- 中文名称：《算法图解——像小说一样有趣的算法入门书》
1 算法简介
- 二分查找：输入是一个有序的元素列表
- 运行时间：线性时间；对数时间
- 大O表示法：算法有多快，指出了算法需要执行的操作数，指出了最糟情况下的运行时间
- O(log n)
- O(n)
- O(n * log n)
- O(n 2 )
- O(n!)
2 选择排序
- 数组和链表
- 链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
- 数组的读取速度更快，支持随机访问，数组的元素都在一起。
- 数组的读取速度很快。
- 链表的插入和删除速度很快。
3 递归
- 递归只是让解决方案更清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。
- 基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。
- 调用栈：栈有两种操作：压入和弹出。
- 调用栈可能很长，这将占用大量的内存。
- 调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。
4 快速排序
-
分而治之（divide and conquer，D&C）
(1) 找出基线条件，这种条件必须尽可能简单。
(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。 -
编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。
-
平均情况和最糟情况
5 散列表
- 散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。将输入映射到数字
- 散列表（hash table）——字典
- 避免冲突，需要有：
- 较低的填装因子；
- 良好的散列函数。
6 广度优先搜索
- 图模拟一组连接。
- 图由节点（node）和边（edge）组成。
- 队列：队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。
- from collections import deque
- 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
- 对于检查过的人，务必不要再去检查，否则可能导致无限循环。
7 狄克斯特拉算法
- Dijkstra’s algorithm，总权重最小的路径。
- 带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。
- 狄克斯特拉算法只适用于有向无环图（directed acyclic
graph，DAG）。 - 如果有负权边，就不能使用狄克斯特拉算法。
- 贝尔曼-福德算法（Bellman-Ford algorithm）。
- infinity = float(“inf”)
8 贪婪算法
- 每步都选择局部最优解；
- 教室调度问题；背包问题；集合覆盖问题；旅行商问题
- 很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。NP-complete
- 没办法判断问题是不是NP完全问题：
- 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
- 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
- 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
9 动态规划
- 动态规划先解决子问题，再逐步解决大问题。
- 在背包问题中，你必须在背包容量给定的情况下，偷到价值最高的商品。
- 在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。
- 每种动态规划解决方案都涉及网格。单元格中的值通常就是你要优化的值。
- 费曼算法（Feynman algorithm）
- (1) 将问题写下来。
- (2) 好好思考。
- (3) 将答案写下来。
- 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
- 没有放之四海皆准的计算动态规划解决方案的公式。
10 K最近邻算法
- KNN用于分类和回归，需要考虑最近的邻居。
- 分类就是编组。
- 回归就是预测结果（如数字）。
11 10种算法
- 树：二叉查找树（binary search tree）；左子节点的值都比它小，而右子节点的值都比它大。
- 反向索引：
