我知道以下针对重击手的算法:
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)。