Joh*_*ith 3 algorithm optimization performance graph-algorithm
(我在这里敲我的头.让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}.
我不确定是否还有一些其他有趣的obervations来找到这些最大值.热烈欢迎任何想法!
我的问题是,如果对于一般情况,当X = {x1,x2,...,xn}并且有m个子集X时,表示为A1,A2,... Am,是否有一些更有效的技术可供查找这样的最大值Max {Ai}(i = 1,...,m)？
我们将非常感谢您的帮助!
假设给定集合的典型表示,没有方法渐近地比蛮力更好.简单地扫描集合以找到每个集合的最大成员需要线性时间和线性时间是最佳的,因为必须读取集合中的每个成员以确定最大值.
现在,如果输入表示不仅仅是每个集合中元素的列表,则可以应用其他边界和算法.例如,如果我们知道输入集被排序并且集合的长度作为输入的一部分给出,我们显然可以仅在子集的数量上找到时间线性的最大元素而不是它们的长度.
| 归档时间： |
|
| 查看次数： |
790 次 |
| 最近记录： |