分析一个O（n）算法来检查排序数组中的螺母/螺栓匹配

Question

我有一组n个螺母和一组n个螺栓，它们都按大小递增排列。我需要给出一个O（n）算法来检查一个螺母和螺栓是否具有相同的尺寸 。螺母尺寸在一个阵列中NUTS [1..n] 螺栓尺寸在一个阵列中BOLTS [1 ... n]

我不需要找到所有匹配，只要停止算法即使一个匹配被发现。在这里，我的psuedocode看起来像迄今为止

for each n in NUTS 
    for each b in BOLTS 
      if BOLTS[i] == NUTS[i] 
       break; 

因此，对于每个螺母，我正在寻找所有的螺栓。这是O（n^2），我将如何使这个O（n）？我的理解是我可能需要只有一个for循环来做到这一点。抱歉，我的理解有点不稳定

Answer 1

在最差的情况下，共享伪代码将会花费O（n^2），这是在没有匹配对的情况下。 但是，通过使用二进制搜索，您可以将其加速到O（nlogn），因为数组按排序顺序排列。

foreach A in nuts: 
if binarysearch (Bolts, Bolts+n , A) 
    break; 

此外，您也可以使用两个指针在每个数组中使用两个指针并相应地增加它们，从而加速到O（n）。

Bolt_index = Nut_index = 0 
while (Bolt_Index < Bolts.size && Nut_Index < Nuts.Size) 
     while(Bolt_Index < Bolts.Size && Bolts[Bolt_index] < Nuts[Nut_Index] ) 
     Bolt_index++ ; 
     while(Nut_Index < Nuts.Size && Nuts[Nut_index] < Bolts[Bolt_Index]) 
     Nut_index++ ; 
     if Bolt_Index< Bolts.Size && Nut_Index < Nuts.Size && Bolts[Bolt_Index] == Nuts[Nut_Index] 
     Match_found// break 
     else 
     Nut_Index++ // increment either Nut_Index or Bolt_Index 

Answer 2

您可以在同一个循环中遍历两个数组，但使用两个单独的索引变量。您总是增加数组值较小的索引变量。如果两者都不小，他们是平等的，你找到了一个匹配。

i = 0; 
j = 0; 
while (i < n and j < n) { 
    if (NUTS[i] < BOLTS[j]) { 
     i++; 
    } else if (NUTS[i] > BOLTS[j]) { 
     j++; 
    } else { 
     return true; // found a match 
    } 
} 
return false; // found nothing 

最好的情况是NUTS[0] == BOLTS[0]的时候，因为你进入决赛else条款并立即返回true。

最糟糕的情况是，当您从未输入最终的else子句时，因为您必须将循环一直循环到最后。如果您始终采用第一个或第二个if子句，则会发生这种情况，即增加i或j。在最坏的情况下，你在递增i和j之间交替，使得它们都增长得尽可能慢。这会导致最糟糕的情况，即至少有一个变量超过n之前的2*n步骤。

因此该算法在O（2 * n）中，即O（n）。