forループ内の2つの入れ子whileループの実行時間

Question

forループと2つのlinkedListsに関係する内部の2つの入れ子whileループでアルゴリズムの複雑さを見出そうとすると、私は非常に混乱します。次のコードを考えてみましょう：

public int func(ClassName b){ 
// int[] myArray = new Node[n]; 
Node curA; 
Node curB; 
int sum = 0; 
for(int i =0; i<n ; i++){ 
    curA = this.myArray[i]; 
    while(curA != null){ 
     curB = b.myArray[i] 
     while(curB != null){ 
      if(curA.data.equals(curB.data) sum++; 
      curB = curB.next; 
     } 
     curA = curA.next; 
    } 

    } 
    return sum; 
} 

をジャストフィールドmyarrayのよう含まれている（クラス名を言う）が二つのオブジェクトこれと同じクラスのBということを想像してみてください。このオブジェクトから関数funcを呼び出し、bオブジェクトを渡します。 this.myArray [i]リスト内のすべてのノードは、b.myArray [i] list内のすべてのノードと比較されます。 myArrayの各要素のリストはどれくらいの長さかわかりません。時には、b.myArray [i]がnullと等しいか、this.myArray [i]がnullと等しい場合でも、繰り返しと実行時間が短縮されます。私はこの複雑さがO（n^3）になると思った。しかしこれは正しいのですか？複雑なO（n）を持つforループについては確信していますが、whileループでは何が起こっているのか分かりません。 ご協力いただければ幸いです！

Answer 1

明らかにすると、myArrayフィールドはリンクリストの配列です。これはあなたのコードが実際に擬似コードで表現しなければ何です：

for each index i in this.myArray 
    iterate over all elements of this.myArray[i] 
    iterate over all elements of b.myArray[i] 
     do O(1) work 

this.myArrayの長さはN、this.myArrayでリストの最大長がMでさ、そしてb.myArrayでリストの最大長がKである場合には、実行時の複雑さはO（M x N x K）です。

Answer 2

あなたの混乱の原因は、nの機能に関してアルゴリズムの時間的複雑さを表現しようとしているようです。リストの長さがnから独立している場合は不可能です。 n-1から0からすべてのiについては

はAiがリストb.myArray[i]の長さリストthis.myArray[i]とBiの長さとします。

最も内側のループが実行された回数の正確な数は次のとおりです。あなたがAiとBiの値にいくつかの制限を配置する必要があり、時間の複雑さを決定するために

A0×B0 + A1×B1 + ... + An-1×Bn-1

。

いくつかの例：

• すべてのリストの長さがMで囲まれていると仮定します。 n-1

  A0×B0 + A1×B1 + ... + An-1×Bn-1 ≤ n×M²

  から0から0からのすべてのiためn-1

  Bi ≤ Mにすべてのiため

  Ai ≤ Mだから、時間の複雑さが(n×M²)です。

• すべてのオブジェクトのリストの要素の合計数がKであるとします。

  A0 + A1 + ... + An-1 ≤ K

  B0 + B1 + ... + Bn-1 ≤ K

  A0×B0 + A1×B1 + ... + An-1×Bn-1 ≤ (A0 + A1 + ... + An-1)×(B0 + B1 + ... + Bn-1) ≤ K²

  だから、時間の複雑さが(K²)です。

• リストの長さがわからないとします。次に、実行時間の上限も知られていません。最も外側にあるループは常にn回実行されるため、下限はΩ(n)です。