在每个子集上查找最大值
(我在这里撞到头了。设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)？
我们将非常感谢您的帮助！
回答 2
Stack Overflow用户
发布于 2012-09-01 12:33:00
假设给定集合的典型表示，没有比蛮力更好的渐近方法。简单地扫描集合以找到每个集合的最大成员需要线性时间，并且线性时间是最佳的，因为为了确定最大值，必须读取集合的每个成员。
现在，如果输入表示不是每个集合中元素的简单列表，那么可以应用其他界限和算法。例如，如果我们知道输入集合是排序的，并且集合的长度是输入的一部分，那么我们显然可以只根据子集的数量找到时间上的最大元素，而不是它们的长度。
Stack Overflow用户
发布于 2012-09-01 12:55:33
如果您的集合是在散列中实现的(或者，更一般地，如果您可以在O(1)时间内检查集合中是否存在值)，则可以改进暴力方法。
不是遍历子集的元素并保持最大值，而是按降序遍历父集的元素，检查子集中是否存在这些元素。第一个找到的元素必须是子集的最大值。从技术上讲，在一般情况下，这仍然需要O (n )时间(n=子集carnality)，但在实践中通常会带来很大的性能优势。(如果您有关于子集的数量和大小的任何数据，并且他们支持这种方法，那么在平均情况下，您可以改进O(n)。)
然而，这种方法需要对父集的元素(n log n)进行排序，因此只有当子集的数量远远大于父集的数量时，它才是值得的。
https://stackoverflow.com/questions/12224887
复制相似问题
腾讯云开发者
