このアルゴリズム（コード）の時間複雑度はどのくらいですか？

Question

私は、6種類のXPathクエリをSQLクエリに変換するアルゴリズムを持っています。したがって、私のコードにはIf-elseif-else文（複数のif）が含まれています。私はインターネットから、If-elseif-elseステートメントの時間的複雑さが、より多くの処理を有するifの1つの最悪ケース時間であることを読む。私はこのコードのための時間の複雑さが何であるかを知っておく必要があります。

} else if (Query_Type == 5){ 
for (int i = strXPathQuery.length()-1; i > 0; i--) { 
     if (strXPathQuery.charAt(i) == '/') { 
      position = i; 
      break; 
     }  
} // end for loop        
Last_Node = strXPathQuery.substring(position+1); 
strAncestor_Path = ""; 
int bracket_pos=0; 
for (int i = 0; i < position; i++) { 
    if (strXPathQuery.charAt(i) == '[') { 
      bracket_pos = i; 
      break; 
    } else if (strXPathQuery.charAt(i) == '/' && strXPathQuery.charAt(i+1) == '/') { 
      strAncestor_Path = strAncestor_Path + "%"; 
    } 
    else { 
      strAncestor_Path = strAncestor_Path + strXPathQuery.charAt(i); 
    } // end if statement 
} // end for 
    int operator_pos = 0; 
    String Node_condition=""; 
    for (int i = bracket_pos+1; i < position-2; i++) { 
     if ((strXPathQuery.charAt(i) == '<') || (strXPathQuery.charAt(i) == '>') || (strXPathQuery.charAt(i) == '=') || (strXPathQuery.charAt(i) == '!')) { 
       operator_pos = i; 
       break; 
       } 
     else { 
      Node_condition = Node_condition + strXPathQuery.charAt(i); 
     } // end if   } 
    String Value_condition=""; 
    for (int i = operator_pos; i < position-1; i++) { 
     Value_condition = Value_condition + strXPathQuery.charAt(i); 
    } // end for loop 
    strSQLQuery = "SELECT L2.Node_Value \n" + 
        "FROM Leaf_Node L1, Leaf_Node L2, Ancestor_Path P\n" + 
        "WHERE P.Ances_PathExp LIKE '" + strAncestor_Path + "'\n" + 
        "AND L1.Ances_PathID = P.Ances_PathID \n" + 
        "AND L1.Node_Name = '" + Node_condition + "'\n" + 
        "AND L1.Node_Value '".replace("'", "") + Value_condition + "'\n".replace("'", "") + 
        "AND L2.Node_Name = '" + Last_Node + "'\n" + 
        "AND L1.Ances_PathID = L2.Ances_PathID \n" + 
        "AND L1.Ances_Pos = L2.Ances_Pos " ; 
    txtSQLQuery.setText(strSQLQuery); 
     } 
     } 

Answer 1

あなたはO(N^2)可能性がある3人のルックスを持っています。例えば。

for (int i = 0; i < position; i++) { 
     ... 
     strAncestor_Path = strAncestor_Path + strXPathQuery.charAt(i); 
     ... 
} 

は、そのループのために、positionの値はstrXPathQuery.length() ...またはNあること（最悪の場合）と仮定する。つまり、同じ文字列に文字を追加しています。N回。文字を文字列に追加すると、O(N)の操作になります。 （追加すると、新しい文字列が作成され、既存の文字列のすべての文字がコピーされます）。N回の複雑さはO(N^2)です。

の平均複雑度はである可能性がありますが、入力によって異なります。

（そして、私はあなたが実際にここにしようとしているもののまわりで私の頭を取得するために忍耐を持っていません。あなたのコードのがらくたのスタイルは私の目を傷つける行っています。）

---

したい場合パフォーマンスを実行するには、そのような文字列を作成しないでください。 StringBuilderを使用します。

StringBuilder path = new StringBuilder(); 

for (int i = 0; i < position; i++) { 
     ... 
     path.append(strXPathQuery.charAt(i)); 
     ... 
}