スライディングウィンドウの時間の複雑さ

Question

私はこのスライディングウィンドウアルゴリズムを問題に持っています。 Given a string s and a non-empty string p, find all the start indices of p's anagrams in s. 人々は、このアルゴリズムの実行時間はo(len(s))であると私は正しく理解していることを確認したいと思います。

したがって、外側whileはo(len(s))です（mapルックアップはo（1）と仮定します）。最悪の場合は内側whileループもo(len(s))で実行できます。例の場合、Sがaxyzzzzzzzbcで、Pがabcの場合、inner whileループは開始ポインタを末尾に移動するため、o(len(s) + len(s))になりますので、o(2len(s))ですが、最終的な実行時間がo(len(s))になるように定数を落とします。

これが正しいかどうかお知らせください。

public List<Integer> findAnagrams(String s, String p) { 
    List<Integer> ret = new ArrayList<>(); 
    Map<Character, Integer> map = new HashMap<>(); 
    for (Character c : p.toCharArray()) { 
     map.put(c, map.get(c) == null ? 1 : map.get(c) + 1); 
    } 
    int b = 0, i = 0; 
    int c = map.size(); 
    while (i < s.length()) { 
     if (map.containsKey(s.charAt(i))) { 
      int t = map.get(s.charAt(i)) - 1; 
      map.put(s.charAt(i), t); 
      if (t == 0) c--; 
     } 
     i++; 
     while (c == 0) { 
      if (map.containsKey(s.charAt(b))) { 
       int t = map.get(s.charAt(b)) + 1; 
       map.put(s.charAt(b), t); 
       if (t > 0) c++; 
        c++; 
      } 
      if (i - b == p.length()) { 
       ret.add(b); 
      } 
      b++; 

     } 
    } 
    return ret; 

Answer 1

はい、複雑さは線形です。 ほとんどの文字は最後のM=p.length-1文字を除いて2回扱われます。

だからO(N + N - M) = O(N)