Quelle est la grande complexité Oh de cet algorithme

Question

Besoin de trouver la complexité Big O pour ma solution de ce LeetCode problem.

Je ne peux pas estimer la complexité due aux suppressions répétées de la file d'attente lorsqu'un caractère répétitif est détecté, sans lequel il devrait être O (n) en raison de la seule boucle for qui traverse la chaîne.

Affichage l'essentiel du problème et ma solution pour votre référence:

d'une chaîne, trouver la longueur de la plus longue sans sous-chaîne caractères répéter.

Exemples:

Compte tenu "abcabcbb", la réponse est "abc", dont la longueur est 3.

Compte tenu "bbbbb", la réponse est "b", avec la longueur de 1.

Compte tenu « pwwkew », la réponse est « WKE », avec la longueur de 3. Notez que la réponse doit être une sous-chaîne, « pwke » est une suite et non une sous-chaîne .

Ma solution:

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

Votre solution sera O (n). Tout ce qui est à l'intérieur de la boucle for n'est pas si important, c'est plutôt le nombre de fois que la boucle fonctionnera. C'est parce que la partie interne de la boucle sera un nombre arbitraire d'opérations qui sera juste une constante. Depuis dans le grand O nous ne se soucient pas de constantes ce qui est plus important est le nombre de fois les pistes de boucle, qui serait N.

Peut-être un peu de mathématiques pourrait aider à démontrer:

Say N = 5 et vous Je ne sais pas combien d'opérations la boucle va faire, mais vous savez qu'il fonctionnera 5 fois. D'abord prétendre qu'il ne fait qu'une opération, alors bien sûr le nombre d'opérations est de 5 qui est 1 * N. Alors prétendez que la boucle fait 100 opérations, alors le nombre d'opérations est 500 qui est 100 * N. Dans les deux cas, le grand O est O (n). Vous pouvez alors supposer que pour un nombre arbitraire d'opérations en boucle, vous obtiendrez toujours O (n). Je ne sais pas si les mathématiques sont valables, mais l'idée générale a du sens.