在次二次时间内找到两个排序数组的最大相容值的最大和

Question

假设我有两个排序列表，如下所示:

• a =[13,7,5,3,2，…]， 0]
• b =[16,12,8,4，…]1)

还有一个函数:

IsValid(x,y):

如果x和y兼容则返回true。兼容性完全是任意的，除了0可以与任何其他数字匹配。

那么我如何找到a和b中的两个数，使它们都是IsValid，从而产生最大的和呢?我要找出最大的有效和。

这是我在Python中的当前算法

def FindBest(a, b):
isDone = False
aChecked =[]
bChecked = []
aPossible = []
aIndex = 0
bPossible = []
bIndex = 0
posResult = []

#initialize
try:
    aPossible= (a[aIndex])
    aIndex+=1
    bPossible=(b[bIndex])
    bIndex+=1
except:
    print "Why did you run this on an empty list?"
    return
while not isDone:
    posResult = []

    if(len(aPossible)>0):
        for b in bChecked:
            if(IsValid(aPossible,b)):
                posResult.append(aPossible+b)
                isDone = True

    if len(bPossible)>0:
        for a in aChecked:
            if(IsValid(a,bPossible)):
                posResult.append(a+bPossible)
                isDone = True
    #compare the first two possibles
    if(IsValid(aPossible,bPossible)):
                posResult.append(aPossible+bPossible)
                isDone = True
    if(len(aPossible) > 0):
        aChecked.append(bPossible)
    if(len(bPossible) >0):
        bChecked.append(bPossible)
    if(aIndex<len(a)):
        aPossible= (a[aIndex])
        aIndex+=1
    if(bIndex<len(b)):
        bPossible =(b[bIndex])
        bIndex+=1
    if len(a)==len(aChecked) and len(b) == len(bChecked):
        print "none found"
        isDone = True
return posResult

Answer 1

但是正如其他人指出的那样，最糟糕的情况是O(n*n)，其中n是每个列表的大小。

对于最坏的情况，考虑a = [9,8,7,0]和b = [4,3,2,1]，其中除了(0,4),(0,3),(0,2),(0,1)之外没有兼容的对。

让我们乐观地假设你先检查并找到了这四对。所以你记得配对(0,4)是当前最好的答案。您仍然需要检查所有大于4码的对，以确保(0,4)确实是最佳答案。列出这些对:

(9,4)
(9,3) (8,4)
(9,2) (8,3) (7,4)
(9,1) (8,2) (7,3)

并且这些对的数量正在增长O(n*n)

因此不可能推导出子二次时间算法。[因为我假设最好的算法可以实现，该算法在某些情况下仍然至少需要O(n*n)]

也许你的问题遗漏了更多的信息?