這個算法（代碼）的時間複雜度是多少？

-8

我有算法將六種類型的XPath查詢轉換爲SQL查詢。所以，我的代碼包含If-elseif-else語句（多個if）。我從互聯網上讀到，If-elseif-else語句的時間複雜度是其中一個如果有更多處理的最壞情況時間。我需要知道什麼是對這個代碼的時間複雜度：這個算法（代碼）的時間複雜度是多少？

} 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); 
     } 
     }

來源

2016-06-28 Amjad Qtaish

什麼阻止你計算它？或者讓別人跋涉一下你的代碼更容易？ – shmosel

-1

你有三個看起來有可能是O(N^2)。例如。

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)); 
     ... 
}

來源

2016-06-28 12:23:39

謝謝。此代碼處理一個輸入條件，但還有另外5個輸入條件。我的問題是具有if-elseif語句的代碼的時間複雜度是多少。我在這裏顯示if-elseif語句的部分，它比其他操作有更多的操作。所以，我們可以根據這個代碼計算算法的時間複雜度。你確定時間複雜度是O（n^2） –

我相信最壞的情況是'O（N^2）'。最好的情況是'O（N）'。平均而言......取決於輸入。 –

這個算法（代碼）的時間複雜度是多少？

回答

相關問題