亚线性空间算法1

流模型

问题：如果采用bit存储的话 可以是n或者是Logn 但是对于特别大的数据量 这也是不行的，所以我们思考是否有Loglogn的算法 来存储统计的数据。

问题1：近似计数Morris算法

• 多次实验 使结果更准确。

问题2：不重复元素/FM算法

• ?D 不重复元素的个数 m元素的值域是[0,m] n数据流中元素的个数

• 那么我们可以采用的第一种计数方式是类似于bitmap的方式记录元素存放的位置

• 第二种方式是我们维护一个集合，每个集合中的元素的大小是Logm 或者是logx具体取决于指派。

• 最后的估值大约是12-13?
• 因为哈希函数是随机的 所以我们得到的z值是随机的
• 下面是关于算法正确性的一点讨论

首先 右边的两种情况D是相同的 相当于哈希函数开了一个盲盒 最后的估值
只是取决于D和元素具体是什么没有关系

其次 D越大 越接近0的概率越大 因为他只要有个更小的那么他就一般很难进行更新了。

问题3 ：固定大小采样?

经典的水库抽样。 第二个证明略

有放回

?