学习笔记

• 一个很长的二进制向量和一系列随机映射函数

• 用于检索一个元素是否在一个集合中

• 优点：

  • 空间效率和查询时间都远远超过一般的算法

• 缺点

  • 有一定的误识别率和删除困难
  • 布隆过滤器不存在的，一定不存在，如果布隆过滤器存在，元素不一定真的存在

• 最近最少被使用的元素优先移除

1. 比较类排序：

   • 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序

2. 非比较类排序：

   • 不通过比较来决定元素间的相对次序，他可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序

3. 重点了解比较类排序中非O(n*n)的排序方法：

   • 快排
   • 归并排序
   • 堆排序