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

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)]

也许您遗漏了问题中的更多信息？