| 查看: 1842 | 回复: 2 | ||
[求助]
求助！关于Misra-Gries 算法和数据流的两道题！万分感谢！
|
 求助两道计算题，请各路大神帮忙看看！1. 假设有一个包含 90 个数据的数据流，该数据流一共有 5 个不同的元素，即 （x1, x2, x3, x4, x5），其中 x1 出现的频率为 50， x2 出现的频率为 10， x3 出 现的频率为 10， x4 出现的频率为 10， x5 出现的频率为 10。考虑在该数据流 上运行参数为 k=2 的 Misra-Gries 算法， 尝试解决以下问题： (a) 数据流中的数据以怎样的到达顺序可以使得元素 x1 的计数最大（也就是 Misra-Gries 算法在最终状态下 x1 的计数最大）？该最大的计数值是多少？ (b) 数据流中的数据以怎样的到达顺序可以使得元素 x1 的计数最小（也就是 Misra-Gries 算法在最终状态下 x1 的计数最小）？该最小的计数值是多少？ 2. 假设有两个数据流 E1 和 E2，其中 E1 包含 n1 个数据， E2 包含 n2 个数据。 令 E 为 E1 和 E2 合并后的数据流，即 E={E1, E2}。 例如， E1={a, b, a, c}， E1={a, b, c, c, d}，那么 E= { a, b, a, c, a, b, c, c, d}。考虑两个蓄水池采样算法，分别对 数据流 E1 和 E2 进行采样。两个采样算法的蓄水池大小都为 k (k<n1, k<n2)， 也即对于每个数据流，我们可以得到 k 个均匀的样本。请设计一个样本合并 算法将这 2k 个样本进行合并，得到 k 个合并流 E 中的均匀样本？ 并证明得到 的 k 个样本中的任何一个样本数据被抽取的概率为 k/(n1+n2)。 |
回复此楼» 猜你喜欢
津理工大学晶体材料全国重点实验室刘红军教授课题组招收博士生一名
已经有0人回复
-
【原创讨论】从电子约束到物质编辑：一套可迭代的环形磁场科技树
已经有0人回复
-
物理学I论文润色/翻译怎么收费?
已经有274人回复
-
【方案分享】单环磁场+轴心控制+偏转导出电子束约束系统（可行性实验）
已经有6人回复
-
【修正版】单环用磁约束低速电子实验方案（简化版）
已经有0人回复
-
桂林理工大学物理学专业招收调剂，还有三个名额！！！
已经有22人回复
-
考博自荐
已经有4人回复
-
山东大学第二批博士研究生招生
已经有0人回复
-
中国科学院东莞材料科学与技术研究所-2026年博士招生-吴昊研究员-磁学与自旋电子学
已经有0人回复
-
《电磁学》教材推荐
已经有1人回复
-
【急招】合肥工大核聚变材料计算方向2026级工程博士生
已经有4人回复
2楼2019-10-13 09:50:41
3楼2019-10-13 23:59:26