Donner une analyse d'un algorithme O (n) pour vérifier la correspondance des écrous/boulons dans les rangées triées

Question

J'ai une collection de n écrous, et une collection de n boulons, tous deux disposés par ordre croissant de taille. Je dois donner un algorithme O (n) pour vérifier si un écrou et un boulon ont la même taille. Les tailles des écrous sont dans un tableau NUTS [1..n] Les tailles des boulons sont dans un tableau BOLTS [1 ... n]

Je n'ai pas besoin de trouver tous les résultats, il suffit d'arrêter l'algorithme même si un correspond est trouvé. Voici à quoi ressemble mon code-barres

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

Donc, pour chaque écrou, je cherche tous les boulons. C'est O (n^2), Comment ferais-je O (n)? Ma compréhension est que je n'aurais probablement besoin que d'une boucle pour le faire. Désolé, ma compréhension est un peu floue

Answer 1

Le pseudo-code partagé prendra O (n^2) dans le pire des cas, c'est-à-dire lorsqu'il n'y a pas de paire correspondante. Cependant, vous pouvez accélérer ceci jusqu'à O (nlogn) en utilisant la recherche binaire, car les tableaux sont triés.

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

vous pouvez également accélérer ce jusqu'à O (n) en utilisant bien deux pointeurs un dans chaque tableau, et incrémenter en conséquence.

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

Vous pouvez parcourir les deux tableaux dans la même boucle, mais en utilisant deux variables d'index distinctes. Vous incrémentez toujours la variable d'index pour laquelle la valeur du tableau est plus petite. Si aucun n'est plus petit, ils sont égaux et vous avez trouvé une correspondance.

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 

Le meilleur des cas est quand NUTS[0] == BOLTS[0], parce que vous entrez dans la clause else finale et retour true immédiatement.

Le pire des cas est lorsque vous ne saisissez jamais la clause else finale, car vous devez alors répéter la boucle jusqu'à la fin. Cela se produit si vous prenez toujours la première ou la deuxième clause if, en incrémentant soit i ou j. Dans le pire des cas, vous alternez entre incrémenter i et j, ce qui fait croître les deux aussi lentement que possible. Cela conduit à un pire cas de 2*n étapes avant qu'au moins une variable dépasse n.

Par conséquent cet algorithme est dans O (2 * n), qui est O (n).