3

（我在这里敲我的头。令 X={x1,x2,...,xn} 是一个整数集。令 A1,A2,...Am 是 X 的 m 个子集。对于任何 i 和 j， Ai 和 Aj 不一定是不相交的，现在的目标是有效地找到每个 Ai (i=1,...,m) 上的最大值，同时尽可能减少操作次数。

例如，给定 X={2,4,6,3,1}，其子集 A1={2,3,1}，A2={2,6,3,1}，A3={4,2， 3,1}。我们需要分别找到 Max{A1}、Max{A2}、Max{A3}。

求Max{A1}、Max{A2}、Max{A3}的蛮力方法是扫描每个Ai中的所有元素，需要(m*d)次操作，其中m是X的子集数，和 d X 的子集 {Ai} 的平均长度。

现在，我有一些观察：

(1) 对于任意集合 Y⊆X，max{Y}≤max{X}，

例如，由于 Max{X}=6 且 6 在 A2 中，则可以直接找到 Max{A2}=6。

(2) 对于任意两个集合 A 和 B，如果 A∩B 不为空，则 Max{A} 和 Max{B} 可以识别为：

首先，我们找到 A 和 B 之间的共同部分，表示为 c=max{A∩B}。

然后，我们找到 Max{A}=Max{Max{A-(A∩B)}, c} 和 Max{B}=Max{Max{B-(A∩B)}, c}。

我不确定是否还有其他一些有趣的观察可以找到这些最大值。任何想法都受到热烈欢迎！

我的问题是，如果对于一般情况下 X={x1,x2,...,xn} 并且 X 有 m 个子集，表示为 A1,A2,...Am，是否有一些更有效的技术可以找到这样的最大值 Max{Ai} (i=1,...,m) ？

您的帮助将不胜感激！

4

2 回答 2

5

假设给定集合的典型表示，没有比蛮力渐近更好的方法。简单地扫描集合以找到每个集合中的最大成员需要线性时间，而线性时间是最佳的，因为必须读取集合的每个成员以确定最大值。

现在，如果输入表示不仅仅是每个集合中元素的列表，则可能会应用其他边界和算法。例如，如果我们知道输入集是排序的，并且集的长度作为输入的一部分给出，我们显然可以在时间上找到最大元素，仅与子集的数量有关，但与它们的长度无关。

于 2012-09-01T04:33:00.200 回答
3

如果您的集合是在散列中实现的（或者，更一般地说，如果您可以在 O(1) 时间内检查集合中是否存在值），您可以改进蛮力方法。

不是遍历子集的元素并保持最大值，而是按降序遍历父集的元素，检查子集中这些元素的存在。第一个找到的元素必然是子集的最大值。从技术上讲，这在一般情况下仍然需要 O(n) 时间（n = 子集肉体），但在实践中通常会带来很大的性能优势。（如果您有任何关于子集数量和大小的数据，并且他们喜欢这种方法，那么在平均情况下，您可以改进 O(n)。）

然而，这种方法需要对父集的元素进行排序（n log n），因此只有当子集的数量远大于父集的肉体时才值得。

于 2012-09-01T04:55:33.343 回答