近似计数1近似计数解决什么问题
当数据特别大的时候,在二进制的条件下,存储一个数字N,需要log(N)的空间,如果N特别大而且这样的N又特别的多,该怎么办呢?我们的解决办法是行省一些准确性,从而节省更多的空间。使用近似计数算法,每一个数字的存储只需要loglog(N)的空间复杂度就行了。
流模型的计数问题
流模型
定义一个数据流,
。 数 据 流 是 无 限 的 , 当 数 据 流 流 过 个 时 , 出 现 了 个
morris算法
算法
将X初始化为0
循环
如果
返回
证明的目标
我们期望返回的值与N的差别尽量小,换句话说就是如果
利用切比雪夫不等式证明这一点
证明
计算期望
计算方差
令切比雪夫不等式中的
其中,
设定