算法学习纪要
算法，神秘而晦涩的词汇。算法，是计算机科学中最重要同时也是最基础的一环。而我却一直浅尝辄止，每念及此，懊悔不已，愿此番能坚守初心，持之以恒。
算法简介
算法描述指标
-
时间复杂度O 算法的时间复杂度反映了程序执行时间随输入规模变化而变化的规律，常见的时间复杂度:常数阶O(1)、对数阶O(log n)、线性阶O(n)、平方阶O(n^2)、指数阶O(2^n)、阶乘阶O(n!)
-
空间复杂度 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度
二分查找算法
原理
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
算法要求
- 必须采用顺序存储结构。
- 必须按关键字大小有序排列。
图算法
- 计算非加权图中的最短路径，使用
广度优先搜索算法。 - 计算加权图中的最短路径，使用
迪克斯特拉(Dijkstra)算法-只适用于有向无环图,且不能存在负权边。 - 包含负权边的图的最短路径问题可以使用
贝尔曼-福德(Bellman-Ford)算法。
贪婪算法
- 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解；
- NP完全问题，还没有找到快速解决方案；
- 面对NP完全问题，最佳做法是使用近似算法；
- 贪婪算法易于实现，运行速度快，是不错的近似算法；
动态规划
- 需要在给定约束条件下优化某种指标时，动态规划很有用；
- 问题可分解为离散子问题时，可使用动态规划来解决；
- 每种动态规划解决方案都设计网格；
- 单元格中的值通常就是你要优化的值；
- 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题；
- 没有放之四海皆准的计算动态规划解决方案的公式；
费曼算法(搞笑的)
- 将问题写下来；
- 好好思考；
- 将答案写下来。
K最近邻算法
- KNN用于分类和回归，需要考虑最近的邻居；
- 分类就是编组；
- 回归就是预测结果；
- 特征抽取意味着将物品转换为一系列可比较的数字；
- 能否挑选合适的特征事关KNN算法的成败。 延伸: 朴素贝叶斯分类器
知识拓展
- 树(B树、红黑树、堆、伸展树)；
- 反向索引（搜索引擎）；
- 傅里叶变换（处理信号）；
- 并行算法（并行性管理开销、负载均衡）；
- 分布式算法（MapReduce[映射函数 map、归并函数 reduce]）;
- 布隆过滤器和HyperLogLog（面对海量数据不要求绝对准确时，可使用概率型算法）;
- SHA算法；
- 局部敏感的散列算法（Simhash）；
- Diffie-hellman密钥交换；
- 线性规划（给定约束条件下最大限度改善指定指标 Simplex）；