字謎時間複雜度

您將得到兩個字符串。大小爲n的B，大小爲m的B。與n相比，m是非常非常非常小的數字。找出一個包含子這是B的字謎

，我採取的方法是如下

public static boolean ana_check(String a, String b) 
{ 
    int n=a.length(); 
    int m=b.length(); 
    boolean k; 
    for(int i=0;i<=(n-m);i++){ 
     k= anagram((a.substring(i,i+m)),b); 
     if(k) 
      return true; 
} 
    return false; 
}

正如你可以看到我提取從頭開始的長度爲m每串的字符串A並檢查它是否是B的一個字母。爲了檢查謎語，我爲每個字符串建立一個頻率映射，如果發現它們是相同的，我會返回true。代碼如下：

public static boolean anagram(String s, String t) { 
     // Strings of unequal lengths can't be anagrams 
     if(s.length() != t.length()) { 
      return false; 
     } 

     // They're anagrams if both produce the same 'frequency map' 
     return frequencyMap(s).equals(frequencyMap(t)); 
    } 

    private static Map<Character, Integer> frequencyMap(String str) { 
     Map<Character, Integer> map = new HashMap<Character, Integer>(); 
     for(char c : str.toLowerCase().toCharArray()) { 
      Integer frequency = map.get(c); 
      map.put(c, frequency == null ? 1 : frequency+1); 
     } 
     return map; 
    }

我相信anagram方法運行在O（n）時間。方法ana_check的時間複雜度是多少？整體代碼是線性的還是二次的？

來源

2013-12-20 Abhiroop Sarkar

好了，讓我們看看...

假定length（）方法在固定時間內運行（即：它不喜歡工作的strlen（））。您的方法frequencyMap是o（m），anagram將其稱爲兩次。 anagram被稱爲n-m次。總複雜度大約爲o（2 * m * n）。隨着m的增加，'大o'是O（n）。

我可以建議一些優化。首先，您每次調用anagram時都會重新生成字符串b的頻率圖。在ana_check的開頭執行一次。你可以使用一個帶有字符串和頻率映射而不是兩個字符串的anagram方法。

我會做的另一件事是從字謎中刪除長度檢查。是的，這是一項安全功能，但您已經知道您通過的字符串大小相同。無論如何，如果它們的長度不同，頻率映射將仍然不匹配，所以功能是正確的。

更棘手的優化是修改字符串a的頻率映射，而不是每次都重新執行一次。對於第一個子字符串，您照常執行。但是，你繼續前進一個角色，從地圖中減去第一個角色並添加新角色。當然，如果米是< = 3它不會有所作爲，但比這更大的任何東西都將是一場勝利。

來源

2013-12-20 17:46:19

您不需要比較每個位置的整個地圖。

首先創建一個簽署頻率圖並減去B中的每個字母。保持地圖中含有多少個非零條目的計數器c。

接下來在地圖中加入第一個m（長度爲B）的字母A。對於您添加的每個字母，如果該計數曾經爲零，則增量爲c, ，或者在添加字母后變爲零，然後遞減c。

如果c現在是零，那麼你已經找到了一個字謎（每負計數從B已經被肯定計從A平衡），否則矣。

添加的A下一個字母給頻率映射，並且之前 m字母刪除字母，適當地調整c兩個操作。

重複最後兩個步驟，直到c變爲零或用完字母A。

您可能會嘗試通過識別每個時候你添加未出現在B字符進一步優化本，保證是你不匹配下一個m字符（這是從哪兒不同的數量只會變得積極，因爲您通過的其他角色可能會在m之前取消）。所以你可以在那封信之後重新啓動前提條件。這個操作的複雜性可以讓你跳過的不是很高，但是這個特例的代碼可能不會更快。

來源

2015-04-23 18:23:54 sh1

字謎時間複雜度

回答

相關問題