java - 这个算法的大O复杂度是多少

Question

需要找到我的解决方案的 Big O 复杂度 LeetCode problem .

我无法估计复杂性，因为当检测到重复字符时，会从队列中重复删除，如果没有重复删除，由于遍历字符串的单个 for 循环，它应该是 O(n)。

发布问题要点和我的解决方案供您引用:

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

我的解决方案:

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 次。首先假设它只做了一次操作，那么操作次数当然是5，即1*N。然后假设循环执行了 100 次操作，则操作次数为 500，即 100*N。在这两种情况下，大 O 都是 O(n)。然后，您可以假设对于任意数量的循环操作，您仍然会得到 O(n)。我不知道这个数学有多有效，但总体想法是有道理的。