O(n)具有O(1/epsilon)空间的重击者？
对于重击者，我知道以下算法：
Algorithm findHeavyHitters(epsilon, inputStream)
integer k = ceiling(1 / epsilon) - 1
initialize hashmap H of size k
while an item i from the input stream arrives:
if H[i] exists
increment the value associated with H[i]
elsif number of items in H < k
put H[i] into map with value of 1
elseif there exists an entry j with a value of 0
remove j and put H[i] into map with value of 1
else
decrement all values in H by 1
endwhile
return H如果我错了，请纠正我，但是这个算法不会在O(n)中运行。是否可以修改该算法，使其在O(n)中运行，同时保持O(1/epsilon)对空间的使用？
对于数据流，算法的重点是返回顶部epsilon*t项。Epsilon按百分比计算(例如，对至少10%时间发生的数据输入0.1 )。
回答 1
Stack Overflow用户
发布于 2016-06-16 06:57:31
该算法在平均运行时间O(n)的基础上，哈希查找平均为O(1)。
有两个实现细节。首先，最后一步似乎涉及触及H中的每一个价值：
- 将H中的所有值减少1
为了实现这个O(1)，我们添加了一个名为base的额外存储位置，它被初始化为0。然后，我们将算法修改如下：
while an item i from the input stream arrives:
if H[i] exists
increment the value associated with H[i]
elsif number of items in H < k
put H[i] into map with value of base + 1
elseif there exists an entry j with a value of base
remove j and put H[i] into map with value of base + 1
else
increment base
endwhile第二个问题是在O(1)中找到一个值为base (或0)的条目。这可以通过将元素保持在一个“梳子”中来实现:双链接列表的链接列表。每个内部链接列表都包含具有特定计数的条目。外部链接列表包含按计数顺序排列的计数列表，其中头部指向具有最小计数的列表。如果您绘制这个数据结构，它看起来就像一个梳子：
[ base ] -> entry a -> entry b -> entry c
|
[ base + i ] -> entry d
|
[ base + j ] -> entry e -> entry f
|
etc.哈希表现在指向条目，而不是包含它们。若要增加单个条目的计数，则从其列表中删除该条目(如果该列表包含多个元素)，并将其插入到下一个列表中或放入一个元素列表中，该列表将在其所在的列表之后插入，这取决于与下一个列表相关联的计数。这个操作是O(1)。
梳状数据结构仍然是O(k)，其中k是散列中的元素数，因为不能有比元素更明显的计数。
您可以使用一个简单的数组和一个包含每个计数的第一个条目的索引列表，而不是双链接列表。要将一个条目移动到下一个计数桶，首先用最后一个计数项替换它，然后推进下一个计数列表的开头，或者插入一个新的计数列表条目，这取决于下一个计数列表的计数是大还是多。要完成交换，有必要更新散列中两个交换项的位置，但这仍然是O(1)。
https://stackoverflow.com/questions/37851407
复制相似问题
腾讯云开发者
