Quelle est la complexité temporelle de cet algorithme récursif

Question

Voici une question de l'algorithme:

d'une chaîne s et un dictionnaire de mots DICT, ajouter des espaces en s à construire une phrase où chaque mot est un dictionnaire valide mot.

Renvoyer toutes ces phrases possibles. Par exemple, étant donné s = "catsanddog", dict = ["chat", "chats", "et", "sable", "chien"].

Une solution est ["chats et chiens", "chat chien de sable"].

La solution est la suivante, mais j'ai eu du mal à déterminer la complexité temporelle de cette solution. Quelqu'un peut-il me donner quelques indices, surtout si les intervieweurs ont demandé cette fois-ci de la complexité dans les entretiens, y a-t-il un moyen rapide de le trouver sans trop de maths?

public class Solution { 
    Map<String,List<String>> map = new HashMap(); 
    public List<String> wordBreak(String s, Set<String> wordDict) { 
     List<String> res = new ArrayList<String>(); 
     if(s == null || s.length() == 0) { 
      return res; 
     } 
     if(map.containsKey(s)) { 
      return map.get(s); 
     } 
     if(wordDict.contains(s)) { 
      res.add(s); 
     } 
     for(int i = 1 ; i < s.length() ; i++) { 
      String t = s.substring(i); 
      if(wordDict.contains(t)) { 
       List<String> temp = wordBreak(s.substring(0 , i) , wordDict); 
       if(temp.size() != 0) { 
        for(int j = 0 ; j < temp.size() ; j++) { 
         res.add(temp.get(j) + " " + t); 
        } 
       } 
      } 
     } 
     map.put(s , res); 
     return res; 
    } 
} 

Answer 1

La complexité temporelle est O(2^n * n).

Le nombre de maximal de telles ruptures de mot est 2^(n-1), avec les bijection à des vecteurs binaires de longueur n-1: Pour chaque espace entre deux caractères, vous pouvez casser le mot il (1 dans le vecteur) ou non (0 dans le vecteur), vous donnant 2^(n-1) ces mots possibles.

Depuis la création de chaque chaîne, le calcul de son hachage et son ajout à l'ensemble est O(n) (la longueur de la sous-chaîne), vous obtenez O(2^n * n).

Vous obtenez le pire des cas pour:

dict = [a, aa, aaa, aaaa, ....] 
s = "aaaaaaaaa...a" 

Votre map vous assure ne pas faire reprenaient le travail, en utilisant memoization. (Sans cela, la complexité aurait été factorielle de n, mais en l'utilisant vous évitez le travail en double comme recalculer de zéro le préfixe "aaa ... a | a | a" et "aa ... a | aa"