我正在设计一个工作原理如下的算法：
假设有 N 个插槽，它们最初是空的，并且每个插槽都有唯一的编号。
随着时间的流逝，物品将到达并存入编号与物品编号匹配的插槽中。但是，假定物品到达的顺序是随机的。
同时，会定期执行合并算法来合并相邻的占用槽，这样槽会随着时间的推移变得越来越“连接”，最终变成一个大的占用槽，此时算法终止。
PS我的算法是串行的。合并部分在新槽位被占用一定数量后定期激活。
问问题
69 次
1 回答
3
您可能正在寻找基于disjoint-set的东西。
从集合开始n，每个集合都有一个空槽，一旦填满两个相邻的槽，就“合并”[联合]它们。这可以通过在每个集合的每个根中维护“最高”和“最低”字段来完成。
一旦你输入一个元素，你需要找到它的根[用这个数据结构很容易做到]，并将它与 - 合并，set[root.highest+1]如果set[root.lowest-1]它们都已经“填充”了。
每次合并还必须修改 root.highest 和 root.lowest 字段，但是O(1)一旦你找到了新的根，这可以很容易地在 中完成。
如果将不相交集实现为 forests，则算法的初始化时间为O(n)[wheren是 slot 的数量]，并且每个插入操作是O(alpha(n))wherealpha(n)是 inverse ackerman function，它是亚对数的。
于 2012-04-13T09:22:42.470 回答