什麼是下面算法的複雜性順序查找給定字符串的子字符串

-1

我已經寫下面的代碼來查找給定的字符數組是否是主數組的子字符串。請說出以下代碼的最佳情況和最壞情況的複雜順序。什麼是下面算法的複雜性順序查找給定字符串的子字符串

我覺得這是非常有效的O（mainstring.lenth-substring.length）算法最複雜的算法。

public class SubstringOfString { 


    public static boolean isSubstring (char[] main , char[] sub){ 

     int base=0 ; 
     int i=0; 

     while(i<sub.length){ 
      if(sub[i]!=main[base] && i >0){ 
      base=base-i; 
       if (base>main.length-sub.length){ 
        System.out.println("not found"); 
        return false; 
       } 

      } 
      else { 
       i++;base++; 
      } 

     } 

     if (i==sub.length){ 
     System.out.println("found at"+(base-sub.length)); 
     return true; 
     } 
     return false; 

    } 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     char[] main = "i am hello as hello well".toCharArray(); 
     char[] sub="hello".toCharArray(); 
     SubstringOfString.isSubstring(main,sub); 

    } 

}

來源

2014-09-12 Mohit Gupta

我不這麼認爲，因爲你可以給它兩個非常長，相同的字符串。它仍然會檢查這些字符串的每個字符。另外，這個算法不適用於main =「aaab」和sub =「aab」嗎？ – guest 2014-09-12 20:41:16

[請參閱此處]（http://stackoverflow.com/questions/14615264/big-o-analysis-of-a-sub-string-of-string-algorithm-does-onlogn-simplify）與大O分析相關這個話題。我實際上並不相信你可以得到n的大O，除非在字符串中使用單個字符。 – Compass 2014-09-12 20:43:10

@guest這是否適用於main =「aaab」和sub =「aab」 – 2014-09-12 21:10:58

最好的情況複雜度：O（substring.length）最佳案例：串發現在出發mainstring

最壞情況的複雜性：O（mainstring.length）最壞情況：在主串找到。 length-sub.length

來源

2014-09-12 20:43:37 G8XSU

再次考慮你的迴應。 – 2014-09-12 20:44:09

首先，您當前的解決方案實際上並未按照您提供的示例運行：base很快變爲負值。

其次，最差情況下的運行時間爲（substring.length * mainstring.length），因爲每次找到不匹配的字符時都必須將多個位置回溯到子字符串長度。

例如：

char[] main = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".toCharArray(); //60 A's 
char[] sub = "aaaaaaaaaaaaaaaB".toCharArray(); //15 A's 
isSubstring(main,sub); //compares each 'a' in main up to 15 times

來源

2014-09-12 21:49:52 Andreas

什麼是下面算法的複雜性順序查找給定字符串的子字符串

回答

相關問題