算法 | learning

算法

时间复杂度

桶排序:数据值范围较小
计数排序:数据值范围较小,比如500万考生成绩排序,成绩值最大600分
基数排序:对要排序的数据有要求,需要按照”位”来比较,而且位之间有递进关系

单模式串匹配算法

BF(Brute Force)算法: 又称暴力匹配算法朴素匹配算法
- 拿模式串与主串中是所有子串匹配，看是否有能匹配的子串
- 时间复杂度O(n*m) n、m 表示主串和模式串的长度
- 适合数据量少情况
RK(Rabin-Karp)算法
- 借助哈希算法对 BF算法进行改造
- 对每个子串求哈希值,然后模式串的哈希值与子串的哈希值比较
- 时间复杂度是 O(n)
BM（Boyer-Moore)算法理解BM算法
- 根据坏字符规则和好后缀规则进行匹配,遇到模式串中不能匹配的时候,将模式串多滑动几位
- 匹配的效率却很高
KMP算法理解KMP算法
- 借鉴 BM 算法的思想,利用好前缀规则
- 时间复杂度是 O(n+m)
- 构建一个next数组,构建方法就是前缀与后缀交集的最大长度
- 遇到不匹配的字符,不需要从头开始匹配,移动到不同位置开始匹配,移动的位数=已匹配的长度-对应的部分匹配值

多模式串匹配算法

Trie树也叫“字典树” “前缀树”
- Trie树不如红黑树和散列表适合精确匹配,它更加适合前缀匹配
- 比较耗内存
- 时间复杂度是 O(k)，k 表示要匹配的字符串的长度
- 应用场景:字符串的字符集不能太大，前缀重合比较多
AC自动机
- 借助KMP算法对BF算法的改进思想,对Trie树改进,增加了失败指针,类似KMP算法中的next数组,进行下次匹配的多滑动定位,不是从头开始
- 算法实现:1.将多个模式串构建AC自动机(有分2步,1:将模式串构建Trie树 2:在Trie树上构建失败指针), 2.AC自动机中匹配主串

文本结构化算法

TF-IDF
- TF : Term Frequency，是词频的意思,在本文档出现的次数
- IDF : Inverse Document Frequency 是逆文档词频,在所有的文档(N)出现的次数(n) IDF=log(N/(n+1))
- TF-IDF=TF*IDF
TextRank
- 是PageRank的私生子
内容分类
- 冷启动是的用户标注
- SVM算法,如facebook开源的FastText
实体识别
- 算法: 隐马尔科夫模型（HMM）或者条件随机场（CRF）
聚类
- LDA 训练工具有 Gensim，PLDA 等可供选择
词嵌入
- 词之间的相似度如:”北京” 相识度”首都” “直辖市”等

递归和递推算法

参考

递归

程序中不断反复调用自身来达到求解问题的方法

递推

其根据已有的数据和关系，逐步推导而得到结果

区别

相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值

哈希算法

应用

安全加密
唯一标示
数据校验
散列函数
负载均衡
数据分片
分布式存储

算法思想

贪心算法

特点:

一条路走到黑，就一次机会，只能哪边看着顺眼走哪边
其他条件一样的情况下,先选贡献最大的

应用:

哈弗曼编码
Prim
Kruskal最小生成树
Dijkstra

分治算法

分治算法是一种处理问题的思想，递归是一种编程技巧

条件:

原问题与分解成的小问题具有相同的模式
原问题分解成的子问题可以独立求解，子问题之间没有相关性
具有分解终止条件，也就是说，当问题足够小时，可以直接求解
可以将子问题合并成原问题

应用:

MapReduce

回溯算法

特点:

一条路走到黑，无数次重来的机会，还怕我走不出来

应用:

八皇后
数独
0-1背包
图的着色

动态规划

特点:

把原来的问题分解成了几个相似的子问题。（强调“相似子问题”）
所有的子问题都只需要解决一次。（强调“只解决一次”）
储存子问题的解。（强调“储存”）
无后效性 —未来与过去无关

通俗理解:

拥有上帝视角，手握无数平行宇宙的历史存档，同时发展出无数个未来
大部分动态规划能解决的问题，都可以通过回溯算法来解决,只不过回溯算法解决起来效率比较低，时间复杂度是指数级的
空间换时间思路
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到–>这个性质叫做最优子结构

区别

每个阶段只有一个状态->递推；每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划

learning_notes

学习笔记

算法