算法导论学习

lesson 0. 数据结构

1. 列表
2. 堆栈
3. 树
4. 散列

散列：

如何产生随机数

1. 除法
2. 乘法
3. md5
4. 梅森旋转算法

？随机数生成算法中哪一个算法最好

散列

1. 散列函数
2. 冲突 ####冲突的解决办法：
3. 链接法
4. 线性查探
5. 二次查探
6. 双重散列

随机数的应用

1. 布隆过滤器
2. simhash

第二课

前情回顾

bloomfilter

1. 基本原理
2. 实现与测试

simHash

1. 相似性哈希原理

bloomfliter 计算碰撞率

a ： 存储关键字个数 b ： 数组长度 c ： 已经翻转的元素数量 d ：一个关键字翻转的元素个数

占空比： $c/b$ 小 极端 1/b 碰撞概率 ： $(c/b)^d$

实际翻转的个数： $a * d$ 1 实际碰撞的翻转有： $ad - c$ 大 ad -1 碰撞概率为： $ (1 - \frac {c}{a*d})^d$

随机数发生器 更容易产生相关的随机数 而且是正相关

一个关键字翻转元素的最优取值 i

数组长度 ： L 存储元素 ： N 翻转个数 ： I 碰撞概率 ： p 翻转的元素个数 ： F $ p = （F/L）^ I $ 等式：1 $ p=(1- F/N/I )^I $

$log(p) = I * log(F/L) $ $F = L * e^{ln(p)/I} $

$p=(1- \frac{L}{NI} e^{ln(p)/I} )^I $

测试一： 2.1627440063152108e-15 0.10405075991724134 测试二： 3.5506068076608453e-15 0.08787481623866988

simHash 类似文本查找

汉明距离<=1的情况 simhash 值 64 bit 1亿

特定 hash值 前 32位 hash_pre 和 后 32位 hash_suf

精确匹配 | 精确匹配

索引1： 对前32位索引 索引2: 对后32位索引

减少汉明距离计算量

算法导论目录

1. 数据结构 ： B 树 （二分树 红黑树） 2。 排序 ： 比较排序: 冒泡排序 快速排 归并排序 计数排序 基数排序 桶排序 稳定排序

3。 hash

4。 图算法

6。 动态规划 贪心算法 吴亮 王颖 最优化方法 李忠凯

下周内容： 二叉树 红黑树 B树
索引 聚集索引 非聚集索引 （数据库） 位图索引