问题一
问题描述
对比分析折半查找与斐波那契查找的性能与应用场景
折半查找
折半查找介绍
本算法使用前提是静态查找表中的数据必须是有序的，定义两个指针low和high指向查找表的第一个元素和最后一个元素，指针mid指向处于low和high指针中间位置的元素，在查找过程中，每次都同mid指向的元素进行比较，在比较之后确定下一次比较的区间，重置low和high其中一个指针，在下一区间进行比较。
折半查找算法的实现
循环实现
int BinarySearch_c(int array[], int n, int key) {
int low = 0, high = n;
int mid;
while (low <= high) {
mid = (low + high) >> 1;
if (key < array[mid]) {
high = mid - 1;
}
else if (key > array[mid]) {
low = mid + 1;
}
else {
return mid;
}
}
return -1;
}递归实现
int BinarySearch_r(int array[], int low, int high,int key) {
int mid = (low + high) >> 1;
if (key < array[mid]) {
return BinarySearch_r(array, low, mid - 1, key);
}
else if (key > array[mid]) {
return BinarySearch_r(array, mid + 1, high, key);
}
else {
return mid;
}
return -1;
}折半查找的性能及应用场景
在有序表中，折半查找的效率比较高，折半查找每进行依次比较就能拍出表长度的一半，时间复杂度是$O(log_2n)$，如果查找表是无序的，先要将表进行排序，排序本身耗费的时间会比查找时间多，因此二分查找适用于一经建立就很少改动的线性表或者是静态有序数据集，二分查找不适合数据量太大或者太小的场景，数据量太大消耗太多的连续内存，数据量太小，其表现不如顺序查找。
斐波那契查找
斐波那契查找介绍
斐波那契查找原理和二分查找相似，仅仅改变了中间结点的位置，在斐波那契查找算法中，mid位于黄金分割点附近，在斐波那契数列($F(k)=F(k-1)+F(k-2),F(1)=1,F(2)=1$)中有结论：
$$
\lim\limits_{k\rightarrow\infty}F(k-1)/F(k)=\frac{\sqrt{5}-1}{2}
$$
本查找算法关键是找到mid的位置，在n=F(k)情况下，mid=low+F(k-1)-1，进行完一次查找后，排除其中一个区间，确定新的low和high区间。
斐波那契查找算法实现
int FibSearch(int arr[], int key,int n) {
int low = 0, high = n - 1;
int mid;
int k = 0;
while (n > Fibonacci(k) - 1)
k++;
while (low <= high) {
mid = low + Fibonacci(k - 1) - 1;
if (key < arr[mid]) {
high = mid - 1;
k--;
}
else if (key > arr[mid]) {
low = mid + 1;
k -= 2;
}
else {
if (mid <= n - 1)
return mid;
else
return n - 1;
}
}
return -1;
}斐波那契查找算法性能及应用场景
斐波那契查找算法是二分查找的一种改进算法，运用黄金比例的概念提高查询速率，但同样也是一种有序表查找算法，它的平均性能比折半查找好，但最坏情况下查找时间比折半查找长，虽然时间复杂度仍是$O(log~n)$，但是在斐波那契查找中，分割只需要用到加减法而不需要用到除法，虽然折半查找的除2可以用移位运算代替，对于大样本查找效率更高。
问题二
问题描述
调研学习Bloom过滤器的原理
Bloom过滤器
Bloom Filter介绍
Bloom Filter是1970年Bloom提出的一种数据结构，实际上是一个很长的二进制向量和一系列随机映射函数。Bloom过滤器可以用于检索一个元素是否在一个集合中。
Bloom Filter优点
- 时间复杂度低，增加、查询元素的时间复杂度为$O(N)$(N为哈希函数的个数)
- 保密性强，过滤器不存储元素本身
- 存储空间小
Bloom Filter缺点
- 存在一定的误判率
- 无法获取元素本身
- 很难删除元素
Bloom Filter的使用场景
过滤器可以告知元素一定不存在或者可能存在，也就是说如果过滤器告知某元素可能存在，实际会有两种可能性，通过查阅资料查找到过滤器的使用场景
- 解决Redis缓存穿透问题
- 邮件过滤
- 对爬虫网址进行过滤
- 解决重复出现元素问题
Bloom Filter过滤器的原理
Data Structure
一个很长的二进制向量+一系列随机映射函数
以Redis中的布隆过滤器实现为例：
一个大型位数组+多个无偏hash函数
空间计算
在布隆过滤器增加元素之前，首先需要初始化布隆过滤器的空间，也就是上面说的二进制数组，除此之外还需要计算无偏hash函数的个数。布隆过滤器提供了两个参数，分别是预计加入元素的大小n，运行的错误率f。布隆过滤器中有算法根据这两个参数会计算出二进制数组的大小l，以及无偏hash函数的个数k。
它们之间的关系比较简单：
- 错误率越低，位数组越长，控件占用较大
- 错误率越低，无偏hash函数越多，计算耗时较长
增加元素
往布隆过滤器增加元素，添加的key需要根据k个无偏hash函数计算得到多个hash值，然后对数组长度进行取模得到数组下标的位置，然后将对应数组下标的位置的值置为1
- 通过k个无偏hash函数计算得到k个hash值
- 依次取模数组长度，得到数组索引
- 将计算得到的数组索引下标位置数据修改为1
查询元素
布隆过滤器最大的用处就在于判断某样东西一定不存在或者可能存在，而这个就是查询元素的结果。其查询元素的过程如下：
- 通过k个无偏hash函数计算得到k个hash值
- 依次取模数组长度，得到数组索引
- 判断索引处的值是否全部为1，如果全部为1则存在（这种存在可能是误判），如果存在一个0则必定不存在
