找到最大的最大總和，兼容，在子二次時間兩個已排序的陣列的值

Question

說我有兩個已排序的列表如下所示：

• A = [13，7,5，3，2， ...，0]
• b = [16，12，8,4，...，1]

另外我有一個函數：

IsValid(x,y): 

如果x返回true和y是compat IBLE。兼容性完全是任意的，除了值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

我目前ALG但正如其他人所指出的那樣，這種最壞的情況是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）]

也許您遺漏了一些您的問題的更多信息？