該算法的時間複雜度查找前綴

我寫這個算法來檢查一個字符串是否是數組中另一個字符串的前綴。複雜度爲O（n *（n-1）* k），其中n是數組中字符串的數量，，K是字符串的最大長度。我在這裏進行復雜性分析嗎？該算法的時間複雜度查找前綴

public static void isPrefix(String[] strs){ 

    for(int i=0; i<strs.length; i++){ 
     for(int j=i+1; j<strs.length; j++){ 
      String a = strs[i]; 
      String b = strs[j]; 

      if(!commonStr(a,b).isEmpty()){ 
       System.out.println(a + "->" + b); 
      } 
     } 
    } 
} 

private static String commonStr(String a, String b){ 
    int smaller = Math.min(a.length(), b.length()); 
    for(int k=0; k<smaller; k++){ 
     if(a.charAt(k) != b.charAt(k)){ 
      return ""; 
     } 
    } 
    return a.substring(0,smaller); 
} 

public static void main(String[] args){ 
    String[] strs = {"ab", "abc", "cde", "abef"}; 
    isPrefix(strs); 
}

來源

2014-01-27 user697911

可能是一個愚蠢的問題（完全脫離主題），但爲什麼不使用startsWith？ – MrP

如果您添加或刪除數組中的單詞並希望檢查前綴大量時間，可能應考慮使用另一個數據結構，例如Trie：http://en.wikipedia.org/wiki/Trie – Traklon

是的，嘗試比較好，但是對於BigO分析而言，只有 – user697911

你說得對，我相信。這只是K不完全是那。但粗略地說，可以這麼說。

而且它是K * n * (n-1)/2因爲你不檢查所有
有序的字符串（你只檢查一半）。
在你的榜樣，你檢查6名新人，而不是12

需要注意的是，如果你的字符串表示字符100萬至200萬之間長，
但你的n是剛纔說20或50或100，則K盛行並且這個估計
要被仔細解釋。通常情況下，人們可能會期望n >> K，
我想這也是你的想法。

來源

2014-01-27 08:38:01

你爲什麼只檢查一半？一半是平均？最壞的情況應該是K * n^2？ – user697911

一半是好的。如果您已經這樣做了（strs [0]，strs [1]），則不需要檢查（strs [1]，strs [0]）。 –

該算法的時間複雜度查找前綴

回答

相關問題