Какая большая сложность этого алгоритма

Question

Необходимо найти сложность Big O для моего решения LeetCode problem.

Я не могу оценить сложность из-за повторяющихся удалений из очереди при обнаружении повторяющегося символа, без которого он должен быть O (n) из-за одиночного цикла, проходящего через строку.

Проводка суть проблемы и мое решение для вашей справки:

Дана строка, найти длину самой длинной подстроки без повторяющихся символов.

Примеры:

Учитывая "abcabcbb", ответ "ABC", которой длина равна 3.

Учитывая "BBBBB", то ответ "б", с длиной 1.

Учитывая «pwwkew», ответ «WKE», с длиной 3. следует отметить, что ответ должен быть подстроку, «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, не так важно, а количество циклов, которое будет выполняться циклом. Это связано с тем, что внутренняя часть цикла будет произвольным числом операций, которое будет просто константой. Поскольку в большом О мы не заботимся о константах, что является более важным является количество раз, которое запускает цикл, который был бы Н.

Может быть, некоторые математики может помочь продемонстрировать:

Say N = 5, и вы не знаю, сколько операций цикл будет делать, но вы знаете, что он будет работать 5 раз. Сначала сделайте вид, что он выполняет только одну операцию, тогда, конечно, число операций равно 5, что равно 1 * N. Затем сделайте вид, что цикл выполняет 100 операций, тогда число операций равно 500, что равно 100 * N. В обоих случаях большой O равен O (n). Затем вы можете предположить, что для некоторого произвольного числа операций цикла вы все равно получите O (n). Я не знаю, насколько действительна эта математика, но общая идея имеет смысл.