Quelle est la complexité du code ci-dessous par rapport à la mémoire?

Question

J'ai lu à propos de Big-O Notation de here et avait quelques questions sur le calcul de la complexité.Pour le code ci-dessous, j'ai calculé la complexité. besoin de vos entrées pour le même.

private void reverse(String strToRevers) 
    { 
     if(strToRevers.length() == 0) 
     { 
      return ; 
     } 
     else 
     { 
      reverse(strToRevers.substring(1)); 
      System.out.print(strToRevers.charAt(0)); 
     } 
    } 

Si le facteur de mémoire est pris en compte alors la complexité du code ci-dessus pour une chaîne de n caractères est O (n^2). L'explication est pour une chaîne composée de n caractères, la fonction ci-dessous serait appelée récursivement n-1 fois et chaque appel de fonction crée une chaîne de caractère unique (stringToReverse.charAT (0)). C'est donc n * (n-1) * 2 qui se traduit par o (n^2). Faites-moi savoir si c'est juste?

Answer 1

D'où il est n * (n-1) * 2 qui se traduit par o (n^2). Faites-moi savoir si c'est juste?

Presque: il est n * (n-1)/2, pas *2, qui est également O (n^2). Notez que o (n^2) (little-O) means something else, donc la distinction est importante.

Cela suppose que nous considérons cela comme pseudocode. Les implémentations spécifiques aux langages et les compilateurs intelligents peuvent améliorer considérablement le temps de fonctionnement. Par exemple, un compilateur qui peut observer que vous inversez simplement la chaîne peut simplement faire un reverse sur place, qui est O (n).

Answer 2

Apparemment Java, c'est pas O (n ** 2). C'est parce que les chaînes partagent les tampons de séquence de caractères sous-jacents; ils peuvent le faire parce qu'ils sont des objets immuables.

Mais c'est O (n) dans l'espace de pile. Ce n'est pas bon. Il est préférable d'allouer un tampon de travail mutable, d'inverser la chaîne dans ce cas, puis d'imprimer le lot entier à la fois.