字谜时间复杂度

您将得到两个字符串。大小为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

字谜时间复杂度

回答

相关问题