算法複查時間複雜度

我想知道這是否在最壞的情況下作爲Θ(n+m)？

n是i_StringForSearch大小，m是i_SubStringToFind大小。算法複查時間複雜度

2.是否有任何程序建議檢查給定代碼的時間複雜度，我更喜歡免費的工具，它是公認的。

謝謝

public static boolean isSubstring(String i_StringForSearch, String i_SubStringToFind) 
    { 
     int strForSearchIndex = 0; 
     int subStrToFindIndex = 0; 
     boolean endOfStringToSearch = false; 
     boolean foundSubString = false; 
     boolean isThereASequenceOfMatching = false; 


     while(!endOfStringToSearch && !foundSubString) 
     { 
      if(strForSearchIndex == i_StringForSearch.length()) 
      { 
       endOfStringToSearch = true; 
      } 

      else if(i_StringForSearch.charAt(strForSearchIndex) == i_SubStringToFind.charAt(subStrToFindIndex)) 
      { 
       isThereASequenceOfMatching = true; 
       if(subStrToFindIndex == i_SubStringToFind.length() -1) 
       { 
        foundSubString = true; 
       } 
       subStrToFindIndex++; 
       strForSearchIndex++; 
      } 

      else if(i_StringForSearch.charAt(strForSearchIndex) != i_SubStringToFind.charAt(subStrToFindIndex)) 
      { 
       if(isThereASequenceOfMatching) 
       { 
        subStrToFindIndex = 0; 
        isThereASequenceOfMatching = false; 
       } 
       strForSearchIndex++; 
      } 
     } 

     return foundSubString; 
    }

來源

2012-09-04 JavaSa

看看我相信算法是錯誤的。 'isSubstring（「aaab」，「aab」）== false' – amit

回答你的問題：是的，該算法是O(n+m)。每個迭代增加strForSearchIndex，所以最多隻有n 迭代。 [這假定i_StringForSearch.length()完成在O(1)，這通常是真實的]。
該算法與isSubstring("aaab","aab") == false的計數器示例有誤。
你可能想對Knuth Morris Pratt algorithm和/或Rabin-Karp algorithm和/或Aho-Corasick Algorithm

來源

2012-09-04 10:52:43 amit

好吧一個免費的工具來計算時間複雜度，你知道嗎？ – JavaSa

@JavaSa：這樣的算法不存在。它與[暫停問題]（http://en.wikipedia.org/wiki/Halting_problem）密切相關（沒有通用算法可以確定是否另一個算法會停止）。我相信有啓發式，但我對這些恐怕不熟悉。 – amit

算法複查時間複雜度

回答

相關問題