Java application simple Complexité

Question

J'ai dû résoudre un problème pour une interview, et je n'ai pas compris quelque chose. Le problème était, pour une chaîne comme "nous aimons la randonnée" pour inverser la chaîne comme ceci: "ew ekil gnikih", cela signifie, pour exploser la chaîne comme: str.split ("") et ensuite, chaque mot pour inverser et d'ajouter à la nouvelle chaîne.

Le problème était à la fin du problème, parce que demandait quelque chose complexité, comme: « - attendu pire des cas la complexité est en O (N) » - complexité spatiale wors cas prévu est O (N) (sans compter le stockage nécessaire pour les arguments d'entrée)

Je résolu le problème comme celui-ci:

public static String solution(String S){ 

    if(S.length()>1 && S.length()<200000){ 

     String toReturn = ""; 

     String[] splitted = null; 
     if(S.contains(" ")){ 
      splitted = S.split(" "); 
     } 
     else{ 
      splitted = new String[]{S}; 
     } 

     for(int i=0;i<=splitted.length-1;i++){ 
      String wordToChange = splitted[i]; 
      String reversedWord = ""; 
      for(int j=wordToChange.length()-1;j>=0;j--) 
       reversedWord+=wordToChange.charAt(j); 

      toReturn+=" " + reversedWord; 

     } 

     return toReturn.trim(); 

    } 
    return null; 
} 

ce que je dois faire la demande de la complexité? Merci!

Answer 1

Je pense que ce n'est pas la bonne réponse au moins la complexité du temps. À mon avis, la division d'une chaîne sera très probablement une complexité de O (n). Et cela va ajouter à la complexité suivante, donc nous pouvons l'oublier.

Maintenant, vous créez une chaîne vide et concaténez un caractère au-dessus de chaque chaîne. Ici, vous supposez que cette opération est aussi peu coûteuse que l'insertion d'une valeur dans un tableau (O (1)).

Dans ce cas, vous devez supposer que vous créez une nouvelle chaîne à chaque fois avec la méthode membre concat(). Si vous avez la possibilité de regarder dans l'implémentation de String.concat (String), vous verrez que cette méthode crée un autre char [] dans la longueur de string1.length + string2.length et copie à la fois string1 et string2 dans ça. Donc, cette méthode à elle seule a une complexité de O (n). Parce que vous concaténez n caractères pour un mot de longueur n, il a la complexité de O (n * (n/2)) = O (n^2) pour un mot. En supposant le pire cas d'un seul mot, vous avez la classe de complexité de O (n^2).

Je suis d'accord avec la classe de complexité spatiale de O (n) pour votre code. Mais ceci est juste sous l'hypothèse de l'intelligence de la JVM réutilisant votre espace inutilisé.

Votre code devrait fonctionner, mais je pense que c'est vraiment pas bon code pour ce problème. Vous pouvez l'améliorer avec un StringBuilder ou des opérations directes sur un char [].

Le StringBuilder est une bonne idée, car il agit comme un vecteur ou un ArrayList. J'ai un char beaucoup plus grand [] travaillant dans son arrière-plan qu'une chaîne. Si sa capacité est dépassée (en utilisant la méthode append()), il va créer un tableau beaucoup plus grand, quelque chose comme 2 fois la taille de la matrice précédente. Cela pourrait être seulement une complexité temporelle de O (nlogn). Mais vous pouvez également le modifier en initialisant StringBuilder avec une capacité de la même taille que votre chaîne initiale. Cela signifie que le caractère de sauvegarde [] ne sera pas copié du tout, car vous ne dépasserez pas sa capacité.

Voici un exemple avec l'utilisation d'un char []:

private static void reverseCharArray(char[] result, int start, int end) { 
    int halfDifference = (end - start)/2; 
    for (int i = 0; i < halfDifference; i++) { 
     char buffer = result[start + i]; 
     result[start + i] = result[end - i - 1]; 
     result[end - i - 1] = buffer; 
    } 
}  

public static String reverseWordInString(String string) { 
    char[] stringAsCharArray = string.toCharArray(); 

    int indexStart = 0; 
    for (int indexEnd = 0; indexEnd < stringAsCharArray.length; indexEnd++) { 
     if (stringAsCharArray[indexEnd] != ' ') { 
      continue; 
     } 
     StringOperations.reverseCharArray(stringAsCharArray, indexStart, indexEnd); 
     indexStart = indexEnd + 1; 
    } 
    StringOperations.reverseCharArray(stringAsCharArray, indexStart, stringAsCharArray.length); 

    return String.valueOf(stringAsCharArray); 
} 

Answer 2

A propos de la complexité du temps:

pire cas O (N) signifie que vous devriez avoir un pire scénario dans lequel vous calculer N itération afin d'obtenir le résultat, dans votre cas, vous divisez la chaîne en un array of Strings [opération qui prend probablement O (N), mais cela dépend de la méthode split()], alors pour chaque String du tableau, vous commencez à la fin de la chaîne et inversez les caractères. donc votre pire des cas est O (N) + O (N) ... = O (N)

A propos de la complexité de l'espace:

Chaque chaîne est un objet et vous réserve un espace mémoire pour chaque chaîne que vous créer, ici vous avez un tableau de chaînes, signifie que vous créez un objet pour chaque mot ou lettre que vous avez séparé de la chaîne d'origine. Vous pire des cas est une chaîne comme «j'amtheone » dans lequel vous créez une chaîne pour chaque caractère -> O (N)

Hope this clarifie vos doutes