このアルゴリズムの複雑さはどれくらいですか

Question

私の解決策はBig0の複雑さを見つける必要があります。LeetCode problem。

繰り返し文字が検出されたときにキューから繰り返し削除されるため複雑さを評価することはできません。文字列を通過するforループが1つあるためO（n）にする必要があります。

問題の要点やご参考のために私の解決策を投稿：文字列が与えられ

、 繰り返し文字なしで最長の部分文字列の長さを見つけます。

例：、答えは長さが1の長さと、3

考える "BBBBB"、答えは "B" である "ABC" が、 "abcabcbb" 考える

あります。 「pwwkew」を考える

が、答えは 答えは部分文字列でなければならないことに留意されたいの長さで、「WKE」で、「pwkeは」サブではなく ストリングです。

私のソリューション：

import java.util.Hashtable; 
public class Solution { 
    public int lengthOfLongestSubstring(String s) { 
     Queue<Character> q = new LinkedList<Character>(); 
     Hashtable<Character, Boolean> chars = new Hashtable<Character, Boolean>(); 
     int maxLen = 0; 
     for (int i = 0; i < s.length(); i++) 
     { 
      char ch = s.charAt(i); 
      if (!chars.containsKey(ch)) 
      { 
       q.add(ch); 
       chars.put(ch,true); 
      } 
      else 
      { 
       int len = q.size(); 
       System.out.println(len); 
       while(q.peek()!=ch) 
       { 
        chars.remove(q.remove()); 
       } 
       q.remove(); 
       q.add(ch); 
       if (len > maxLen) 
       maxLen = len; 
      } 
     } 
     if (q.size() > maxLen) 
      return q.size(); 
     return maxLen; 
    } 
} 

Answer 1

あなたのソリューションは、O（n）となります。 forループの中にあるものはどれも重要ではなく、ループが実行される回数です。これは、ループの内側の部分が、定数である任意の数の操作になるためです。大きなOに我々はより重要なものの定数を気にしないのでたぶん、いくつかの数学を発揮助けることができるN.

だろう回ループの実行回数、次のとおりです。

セイN = 5としますループが何回行うのか分かりませんが、ループが5回実行されることはわかります。最初に1つの操作しか行わないふりをして、もちろん操作の数は5で1 * Nです。その後、ループが100回の動作を行うと仮定すると、動作回数は100回* N回となります。どちらの場合も、大きなOはO（n）です。その後、任意の数のループ操作で、まだO（n）が得られると仮定できます。私はその数学がどれほど有効であるか分かりませんが、一般的な考え方は理にかなっています。