Quelle est la complexité de ce simple morceau de code?

Je suis coller ce texte à partir d'un ebook que j'ai. Il est dit de la complexité si O(n²) et donne aussi une explication pour cela, mais je ne vois pas comment.

Question: qu'est-Ce que le temps d'exécution de ce code?

public String makeSentence(String[] words) {
    StringBuffer sentence = new StringBuffer();
    for (String w : words) sentence.append(w);
    return sentence.toString();
}

La réponse que le livre a donné:

O(n²), où n est le nombre de lettres dans la phrase. Voici pourquoi: chaque fois que vous
ajouter une chaîne à la peine, vous créez une copie de la sentence et courir à travers toutes les lettres dans
peine de les copier sur Si vous devez parcourir jusqu'à n caractères à chaque fois dans l'
boucle, et vous êtes en boucle au moins n fois, ce qui vous donne un O(n²) temps d'exécution. Ouch!

Quelqu'un peut-il expliquer cette réponse plus clairement?

Khan: Ce n'est pas son/sa réponse. C'est la réponse dans le livre qui est en cours de lecture, qui est ce qui est remis en question.
StringBuffer a une mémoire tampon interne qui obtient doublé dès qu'il déborde. Que vraiment signifie que la copie de la "phrase" ne se produit pas, chaque fois que vous ajouter quelque chose à cela. Il ne va se passer si les dépassements de tampon.
Si vous êtes préoccupé par la performance, utiliser StringBuilder "à partir de la version du JDK 5, cette classe a été complétée par une classe équivalente conçu pour une utilisation par un seul thread, StringBuilder. La classe StringBuilder doit généralement être utilisé de préférence à celui-ci, car il prend en charge tous les mêmes opérations, mais il est plus rapide, car il n'effectue aucune synchronisation. "

InformationsquelleAutor Someone | 2011-08-23

23

Cela semble être une question d'induire en erreur, car il m'est arrivé de lire ce livre tout à l'heure. Cette partie de texte dans le livre est une faute de frappe! Voici le contexte:

===================================================================

Question: qu'est-Ce que le temps d'exécution de ce code?
```
1 public String makeSentence(String[] words) {
2 StringBuffer sentence = new StringBuffer();
3 for (String w : words) sentence.append(w);
4 return sentence.toString();
5 }
```
Réponse: O(n²), où n est le nombre de lettres dans la phrase. Voici pourquoi: chaque fois que vous ajouter une chaîne à la peine, vous créez une copie de la sentence et courir à travers toutes les lettres en peine de les copier sur. Si vous avez à parcourir jusqu'à n caractères à chaque fois dans la boucle, et vous êtes en boucle au moins n fois, ce qui vous donne un O(n²) temps d'exécution. Ouch!
Avec StringBuffer (ou StringBuilder) peut vous aider à éviter ce problème.
```
1 public String makeSentence(String[] words) {
2 StringBuffer sentence = new StringBuffer();
3 for (String w : words) sentence.append(w);
4 return sentence.toString();
5 }
```
=====================================================================

Avez-vous remarqué que l'auteur a tout fait foiré? Le O(n²) solution elle a mentionné (le premier) était exactement le même que le "optimisé" (ce dernier). Donc, ma conclusion est que l'auteur a été d'essayer de rendre quelque chose d'autre, comme toujours de la copie de la vieille phrase à un nouveau tampon lors de l'ajout de chaque côté chaîne, comme dans l'exemple de O(n²) de l'algorithme. StringBuffer ne doit pas être si bête, que l'auteur a également mentionné "Avec StringBuffer (ou StringBuilder) peut vous aider à éviter ce problème".
- À droite, l'erreur a été corrigé dans le prochain livre de l'édition
- Qu'est-ce que la complexité? Votre réponse n'a pas dit qu'.
InformationsquelleAutor Han Zhou
17

C'est un peu difficile de répondre à une question au sujet de la complexité de ce code, lorsqu'elle est écrite à un haut niveau des résumés loin les détails de la mise en œuvre. Le La documentation Java ne semble pas apporter toutes les garanties en termes de complexité de la append fonction. Comme d'autres l'ont souligné, le StringBuffer classe peut (et doit) être écrit de telle sorte que la complexité de concaténer des chaînes de caractères ne dépend pas de la longueur actuelle de la chaîne tenu à StringBuffer.

Je soupçonne cependant, il n'est pas utile à la personne qui pose cette question pour dire simplement "votre livre est mal!" - au lieu de cela, nous allons voir quelles sont les hypothèses sont formulées et à faire comprendre ce que l'auteur voulait dire.

Vous pouvez faire les hypothèses suivantes:
1. La création d'un new StringBuffer est O(1)
2. Arriver la prochaine chaîne de w dans words est O(1)
3. Retour sentence.toString est au plus O(n).
La question est de savoir vraiment quel est l'ordre de sentence.append(w), et qui dépend de comment ça se passe à l'intérieur de la StringBuffer. Le naïf est de faire comme Shlemiel le Peintre.

L'bêtement

Supposons que vous utilisez un style C nul chaîne de caractères pour le contenu de StringBuffer. La façon dont vous trouvez la fin d'une telle chaîne est par la lecture de chaque personnage, un par un, jusqu'à ce que vous trouver le caractère null - ensuite, pour ajouter une nouvelle chaîne de caractères S, vous pouvez commencer à copier les caractères de S à la StringBuffer chaîne (finition avec un autre caractère null). Si vous écrivez append de cette façon, il est O(un + b), où un est le nombre de caractères actuellement dans le StringBuffer, et b est le nombre de caractères dans le mot nouveau. Si vous passez en boucle sur un tableau de mots, et chaque fois que vous devez lire tous les caractères que vous simplement ajoutés avant d'ajouter un nouveau mot, puis la complexité de la boucle est O(n^2), où n est le nombre total de caractères dans tous les mots (d'ailleurs, le nombre de caractères dans la dernière phrase).

Une meilleure façon

D'autre part, supposons que le contenu de StringBuffer est encore un tableau de caractères, mais nous avons également stocker un nombre entier size qui nous dit combien de temps la chaîne (nombre de caractères). Maintenant nous n'avons plus à lire tous les caractères dans le StringBuffer afin de trouver la fin de la chaîne; il nous suffit de regarder l'indice de size dans le tableau, qui est O(1) au lieu de O(un). Puis le append fonction ne dépend que du nombre de caractères ajoutés, O(b). Dans ce cas, la complexité de la boucle est O(n), où n est le nombre total de caractères dans tous les mots.

...Nous ne sommes pas encore fait!

Enfin, il y a un autre aspect de la mise en œuvre qui n'a pas été couvert encore, et qui est celui apporté par la réponse dans le manuel de l'allocation de mémoire. Chaque fois que vous voulez écrire plus de caractères à votre StringBuffer, vous n'êtes pas la garantie d'avoir assez d'espace dans votre tableau de caractères à fait s'adapter à la nouvelle parole. Si il n'y a pas assez d'espace, votre ordinateur doit d'abord allouer plus de place dans une partie propre de la mémoire, et ensuite copier toutes les informations de l'ancien StringBuffer tableau de partout, et puis il peut continuer comme avant. La copie de données comme cela va prendre O(un) temps (où un est le nombre de caractères à copier).

Dans le pire des cas, vous devez allouer plus de mémoire chaque fois que vous ajoutez un nouveau mot. En fait cela nous ramène à la case départ où la boucle est O(n^2) complexité, et est ce que le livre semble le suggérer. Si vous supposez que rien de fou qui se passe (les mots ne sont pas plus longtemps à un taux exponentiel!), ensuite, vous pouvez probablement réduire le nombre d'allocations de mémoire à quelque chose de plus comme O(log(n)) en ayant la mémoire allouée à croître de façon exponentielle. Si c'est le nombre d'allocations de mémoire, et les allocations de mémoire en général sont O(un), puis le total de la complexité attribué seulement à la gestion de la mémoire dans la boucle est O(n log(n)). Depuis l'ajout de travail est O(n) et moins de la complexité de la gestion de la mémoire, de la complexité de la fonction est en O(n log(n)).

Encore une fois, la documentation de Java ne nous aide pas en termes de la façon dont la capacité de la StringBuffer grandit, il dit seulement "Si l'interne dépassements de la mémoire tampon, il est automatiquement agrandie". En fonction de comment ça se passe, vous pourriez vous retrouver avec soit O(n^2) ou O(n log(n)) dans l'ensemble.

Comme un exercice laissé au lecteur: Trouver un moyen facile de modifier la fonction, de sorte que l'ensemble de la complexité est O(n), par la suppression de réallocation de mémoire problèmes.
- La complexité est O(n), même avec la redistribution. Multipliant log(n) par n est trompeur parce que pas tous les réaffectation a le même coût. La finale de la réaffectation a environ le même prix que tous les autres réunis.
- D'accord, @BrianL besoin de lire sur l'amorti de l'analyse.
- Je pense que les performances de la mémoire comme: O(log(n) * log(n)) si je ne suis pas sûr si c'est une bonne façon de penser de l'amortissement. Il ne me rappelle il peut être proche de O(n) et supporte plus de regarder dans. Dans ce cas, vous êtes de la copie d'un avg de près de log(n) caractères à peu près log(n) fois.
InformationsquelleAutor Brian L
17

Accepté la réponse est tout simplement faux. StringBuffer a amorti O(1) ajouter, donc n ajoute O(n).

Si ce n'était pas O(1) ajouter, StringBuffer aurait pas de raison d'exister, depuis la rédaction de cette boucle avec la plaine String concaténation serait O(n^2) ainsi!
- Notez que javac optimise en fait la concaténation de chaîne d'utiliser StringBuilders.
- L'aiic vous citez la source de la complexité?
- Ahh StringBuffer sous essentiellement des copies de tout pour un seul tableau d'octets, qui "double" de taille quand sa taille est élargi, donc l'amorti O(1). Gotcha.
- Vous êtes dans l'erreur. Avec la complexité serait n^3. Depuis, la complexité serait n+2n+...n^2 qui est proportionnelle à n^3.
InformationsquelleAutor porges

J'ai essayé de le vérifier à l'aide de ce programme

public class Test {

    private static String[] create(int n) {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = "abcdefghijklmnopqrst";
        }
        return res;
    }
    private static String makeSentence(String[] words) {
        StringBuffer sentence = new StringBuffer();
        for (String w : words) sentence.append(w);
        return sentence.toString();
    }


    public static void main(String[] args) {
        String[] ar = create(Integer.parseInt(args[0]));
        long begin = System.currentTimeMillis();
        String res = makeSentence(ar);
        System.out.println(System.currentTimeMillis() - begin);
    }
}

Et le résultat a été, comme prévu, O(n):

java Test de 200000 - 128 ms

java Test de 500000 - 370 ms

java Test 1000000 - 698 ms

Version 1.6.0.21

InformationsquelleAutor Nikita Beloglazov

11

Je pense que ce texte dans le livre doit être une faute de frappe ,je pense que le bon contenu est ci-dessous,je résoudre ce problème:

===================================================================

Question: qu'est-Ce que le temps d'exécution de ce code?
```
public String makeSentence(String[] words) {
    String sentence = new String("");
    for (String w : words) sentence+=W;
    return sentence;
}
```
Réponse: O(n²), où n est le nombre de lettres dans la phrase. Voici pourquoi: chaque fois que vous ajouter une chaîne à la peine, vous créez une copie de la sentence et courir à travers toutes les lettres en peine de les copier sur. Si vous avez à parcourir jusqu'à n caractères à chaque fois dans la boucle, et vous êtes en boucle au moins n fois, ce qui vous donne un O(n²) temps d'exécution. Ouch! Avec StringBuffer (ou StringBuilder) peut vous aider à éviter ce problème.
```
public String makeSentence(String[] words) {
    StringBuffer sentence = new StringBuffer();
    for (String w : words) sentence.append(w);
    return sentence.toString();
}
```
=====================================================================

Suis-je droit?
- Si vous pensez que le contenu de la question d'origine est mauvais en aucune façon modifier
- Je crois que le livre voulu dire cela ainsi.
InformationsquelleAutor Tyler.Zhang
2

Cela dépend vraiment de la mise en œuvre de StringBuffer. En supposant .append() était constante de temps, il est clair que vous avez un O(n) algorithme dans le temps où n = length of the words array. Si .append n'est pas constante de temps, vous aurez besoin de plusieurs votre de O(n) par le temps de la complexité de la méthode. En effet, si la mise en œuvre actuelle de StringBuffer copies des chaînes de caractère par caractère, alors l'algorithme ci-dessus est

Θ(n*m), ou O(n*m), où n est le nombre de mots et m est la moyenne de la longueur des mots, et votre livre est mauvais. Je suppose que vous êtes à la recherche d'un strict lié.

Exemple Simple que le livre la réponse est incorrecte:
String[] words = ['alphabet'] Par le livre de la définition de, n=8, de sorte que l'algorithme sera délimitée par 64 étapes. Est-ce le cas? Clairement pas strictement. Je vois 1 affectation et 1 opération de copie avec n caractères, de sorte que vous obtenez environ 9 étapes. Ce genre de comportement qui est prédit par les limites de O(n*m), comme je l'ai montré ci-dessus.

J'ai fait quelques recherches, et ce n'est pas une simple copie des personnages. Il ressemble à de la mémoire est en train d'être copié en vrac, ce qui nous met à O(n), votre premier deviner la solution.
```
/* StringBuffer is just a proxy */
public AbstractStringBuilder append(String str) 
{
        if (str == null) str = "null";
        int len = str.length();
        ensureCapacityInternal(count + len);
        str.getChars(0, len, value, count);
        count += len;
        return this;
}

/* java.lang.String */
void getChars(char dst[], int dstBegin) {
             System.arraycopy(value, offset, dst, dstBegin, count);
}
```
Votre livre est ancien, terrible, ou les deux. Je ne suis pas assez déterminé à creuser par le biais de JDK versions de trouver une mise en œuvre optimale de StringBuffer, mais peut-être qu'il en existe un.
- Le Sun/Oracle JVM (Hotspot) met en œuvre l'opération d'ajout à l'aide de System.arraycopy qui à son tour repose sur un O(n) opération (mise en œuvre en objArrayKlass.cpp de l'OpenJDK distribution) pour effectuer la copie de tableau, les membres de l'objet en mémoire. Alors, O(M*n) est correct. Je doute qu'un autre JVM ne copie en temps constant, étant donné que la mémoire occupée les blocs doivent être redéfinies.
- Est Système.arraycopy nécessairement de série sur toutes les machines virtuelles? Je ne pouvais imaginer que d'une certaine manière d'être optimisé pour les super-simultanée du matériel qui fait de ce presque linéaire pour la plupart des tailles d'une chaîne donnée.
- Ah. Eh bien, que diriez-vous d'une mise en œuvre qui augmente la longueur de la mémoire tampon en reportant la copie réelle de la mémoire? Je suppose que la vraie réponse est ici que la mise en œuvre de StringBuffer est entièrement la solution à cette question, et qui peut et est susceptible de varier au cours du temps et dans la JVM implémentations.
- le problème avec le redimensionnement/copier le tableau, c'est que la mise en œuvre effective varie d'une architecture à l'autre (en supposant que les tableaux de char ici, par souci de concision). Sur Windows et SPARC, il semble être en O(n) comme il en existe au moins une boucle qui parcourt le nombre de caractères à copier. Sur Linux et Solaris pour plates-formes x86, la JVM des délégués à la extern C appels (dont l'une des caractéristiques que je ne suis pas au courant; je suis tout à fait avoir une lutte avec le langage d'assemblage).
- Il est sûr de supposer que la copie des données d'un tampon à l'autre est O(n). Au moins jusqu'à ce que quelqu'un montre un algorithme qui peut le faire au plus vite. Je pense que, au mieux, certaines architectures peuvent inclure des instructions spéciales qui permettent la reproduction de quelques-correction de plusieurs mots dans le cadre d'une seule opération. Mais même avec une telle instruction, l'opération de copie est toujours réduit à O(n).
- oui, c'est mon point de vue. Compte tenu de tous les autres contrôles qui sont mis en œuvre dans la JVM, la matrice de la copie tend à O(n). Constante de temps les copies semble presque impossible, que les meilleures possibilités sont memcpy/memmove, qui sont encore O(n), bien que OpenJDK apparaît à l'utilisation de ces primitives et pas pour les tableaux d'objets.
InformationsquelleAutor Stefan Kendall

Il y a une faute de frappe dans ce livre.

1er cas :

public String makeSentence(String[] words) {
    String sentence = new String();
    for (String w : words) sentence += w;
    return sentence;
}

Complexité : O(n^2) -> (n mots) x (n caractères copiés à chaque itération, pour la copie de la phrase en cours dans un StringBuffer)

2e cas :

public String makeSentence(String[] words) {
    StringBuffer sentence = new StringBuffer();
    for (String w : words) sentence.append(w);
    return sentence.toString();
}

Complexité : O(n) -> (n mots) x O(1) (amorti complexité pour StringBuffer concaténation)

InformationsquelleAutor Dimos

1

Que l'explication donnée dans le livre, pour de mot dans le tableau de chaîne d'un nouvel objet de la phrase est créée, et cette phrase, l'objet de la première copie la phrase précédente, puis traverse jusqu'à la fin du tableau et ajoute ensuite le nouveau mot, d'où la complexité de n^2.
1. Premier 'n' pour copier la phrase précédente dans un nouvel objet
2. Deuxième " n " pour parcourir ce tableau et ensuite ajouter
Donc n*n sera n^2.

InformationsquelleAutor tryit
0

Ressemble à O(n) pour moi (avec n étant le nombre total de lettres de tous les mots). Vous êtes essentiellement en une itération sur chaque personnage dans words les ajouter dans la StringBuffer.

La seule façon que je pouvais voir cela comme étant O(n^2) est si append() parcourt tout le contenu dans la mémoire tampon avant d'ajouter de tout nouveaux personnages. Et il peut effectivement le faire à l'occasion si le nombre de caractères dépasse la actuellement affectés longueur de la mémoire tampon (il a d'allouer un nouveau tampon, puis de copier tout le tampon courant dans le nouveau tampon). Mais il n'arrivera pas à chaque itération, de sorte que vous ne parvenez toujours pas à avoir O(n^2).

Au plus vous avez de O(m * n), où m est le nombre de fois que la longueur de la mémoire tampon est augmenté. Et parce que le StringBuffer sera le double de sa taille de la mémoire tampon à chaque fois qu'il alloue un tampon plus large, nous pouvons déterminer que m est à peu près égale à log2(n) (en fait log2(n) - log2(16), puisque le défaut initial de la taille de la mémoire tampon est de 16 au lieu de 1).

La vraie réponse est que le livre de l'exemple est O(n log n), et que vous pouvez obtenir à O(n) par preallocating un StringBuffer avec une capacité assez grande pour contenir toutes vos lettres.

Noter que dans Java en ajoutant une chaîne à l'aide += ne présentent inefficace comportement décrit dans le livre de l'explication, comme il a allouer une nouvelle chaîne et de copier toutes les données de deux chaînes en elle. Donc, si vous faites cela, il est O(n^2):
```
String sentence = "";
for (String w : words) {
    sentence += w;
}
```
Mais en utilisant StringBuffer ne devrait pas générer le même comportement que dans l'exemple ci-dessus. C'est l'une des principales raisons pour StringBuffer d'exister en premier lieu.

InformationsquelleAutor aroth
-1

Voici mon calcul pour la façon dont ils ont obtenu O(n^2)

Nous allons ignorer le temps de calcul pour la déclaration d'StringBuffer, car il ne varie pas avec la taille de la chaîne finale.

Lors du calcul de la complexité O nous craignons le pire des cas, cela se produit lorsqu'il y a 1 lettre de Chaînes. Je vous expliquerai après cet exemple:

Disons que nous avons 4 une lettre de chaînes de caractères: 'A', 'B', 'C', 'D'.

Lire dans Un:
CPU-temps pour trouver la fin de StringBuffer: 0
CPU-temps d'ajouter 'A': 1

Lire dans B:
CPU-temps pour trouver la fin de StringBuffer: 1
CPU-temps d'ajouter "B": 1

Lire dans C:
CPU-temps pour trouver la fin de StringBuffer: 2
CPU-temps d'ajouter "C": 1

Lire dans D:
CPU-temps pour trouver la fin de StringBuffer: 3
CPU-temps d'ajouter "D": 1

CPU-temps de copier StringBuffer Chaîne à la fin: 4

Total CPU-temps = 1 + 2 + 3 + 4 + 4

Si nous généralisons ce n 1-lettre de mots:

1 + 2 + 3 + ...... + n + n = 0,5 n(n+1) + n

Je l'ai fait en utilisant la formule de la somme d'une séquence arithmétique.

O(0,5 n^2 + 1,5 n) = O(n^2).

Si nous utilisons multi-lettre des mots, nous allons avoir à trouver la fin de la StringBuffer moins fréquemment, conduisant à une diminution de l'UC-temps et un "meilleur" des cas.

InformationsquelleAutor George Wooding

Vous devez vous connecter pour publier un commentaire.

L'bêtement

Une meilleure façon

...Nous ne sommes pas encore fait!