- 时间复杂度 大O表示法
- 二分查找
- 选择排序
- 快速排序
- 散列表数据结构
- 广度优先搜索
- 迪克斯特拉算法(Dijkstra’s algorithm)
- 贪婪算法
- 动态规划
- k最近邻算法(KNN) k-nearest neighbours
- 朴素贝叶斯分类
- 树
- 反向索引
- 傅里叶变换
- 分布式算法
- 布隆过滤器
- HyperLogLog
- 跳跃表
- SHA(secure has algorithm)安全散列
- simhash 散列
- Diffie-Hellman 非对称加密
- RSA 非对称加密
- 线性规划
时间复杂度 大O表示法
- 时间复杂度指的是执行步骤的数量,而不是时间
- 表示算法耗时随数据增加的增速,重在趋势,因此常量一般忽略,当复杂度相同时才需要常量
- 表示最差情况下的步骤数,即不可能超过的步骤数
- $O(log(n))$ 表示 $O(log_2(n))$
二分查找
- $O(log(n))$
- 必须有序
选择排序
- $O(n^2)$
- 每趟在剩余的数据中选择一个放到排序好的数据后
- 平均运行步骤 $1/2n^2$
快速排序
- $O(n*log(n))$
- 分治的思想,分治一般会使用递归 D&C(divide and conquer)
- 使用尾递归减少深度或转换为循环
- 选择一个值将数据分为两部分,递归直到数据<=2个
- qsort使用快速排序
散列表数据结构
- $O(1)$
- 填装因子,当占用到百分比,好的hash一般在70%时需要扩容
- 数组+链表结构
- SHA是一个比较常用的散列函数
广度优先搜索
- $O(定点+边)$记做$O(V+E)
- 以图为基础、解决跳跃最少路径、是否可达问题
- 通过队列来实现,将一度可达压入队列,出队列的值做标记并继续一度压入
- 图一般以散列表做数据结构,即map的value是链表
- 有向图并单方向向下形成树结构
迪克斯特拉算法(Dijkstra’s algorithm)
- 以加权有向无环图为基础(权值不能有负数)、解决最快路径
- 出发点A,通过表记录A到所有节点的权值,不可直达权无穷大,并记录其父节点
- 找出A一度权值最小节点B
- 计算A经过B到达B邻居的权值,如果比记录小更新记录及父节点
- 对B点从第二步开始重复做权值更新直到到达最终点的最小一度权值
- 从终点的父节点开始倒推路径
- 负权边可使用贝尔曼-福德算法(Bellman-Ford algorithm)
贪婪算法
- 每步在可以选择的数据中找到最优解,即为最终解
- 结果可能不是最优解、但简单且接近最优
- 在集合覆盖问题上,计算需要得出所有的解(NP完全问题),但计算量以阶乘速率上升
动态规划
- 把问题简化到最少数据的单问题
- 每次把子问题最优答案保存,继续添加数据更新最优答案
- 只适用于子问题是离散的,即数据间没有依赖问题
k最近邻算法(KNN) k-nearest neighbours
- 分类:查看附近的数据所属的类型
- 推荐:查看附件的数据喜好推荐
- 回归:根据附件数据的选择猜测本数据的选择
- 距离计算即附件的定义:坐标系距离、余弦相似度等
朴素贝叶斯分类
- 垃圾邮件过滤
树
- 二叉树
- 平衡二叉树(红黑树)
- B树
反向索引
- 搜索算法
傅里叶变换
- 音视频压缩
分布式算法
- map-reduce
布隆过滤器
- 类似散列,但给出可能的答案,不存在(100%),存在(可能错误)
- 占用内存少,查找快
HyperLogLog
- 类似布隆过滤给出集合中元素个数
跳跃表
SHA(secure has algorithm)安全散列
- sha1前版本有漏洞、使用sha3.
- 最安全散列函数bcrypt
- 局部不敏感
simhash 散列
- 局部敏感散列,判断文章是否类似
Diffie-Hellman 非对称加密
- 比RSA易于理解
RSA 非对称加密
线性规划
- 所有图算法都可以使用线性规划代替
- 使用simplex算法
