Qual è la complessità di questo semplice pezzo di codice?

Sto incollando questo testo da un ebook che ho. Dice la complessità se O (n 2 ) e dà anche una spiegazione per questo, ma non riesco a vedere come.

Domanda: qual è il tempo di esecuzione di questo codice?

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

La risposta che il libro ha dato:

O (n 2 ), dove n è il numero di lettere nella frase. Ecco perché: ogni volta che aggiungi una stringa alla frase, crei una copia della frase ed esegui tutte le lettere della frase per copiarle. Se devi ripetere iterando fino a n caratteri ogni volta nel ciclo, e sei looping almeno n volte, che ti dà un tempo di esecuzione O (n 2 ). Ahia!

Qualcuno può spiegare questa risposta in modo più chiaro?

Questa sembra essere una questione di ingannare, perché mi è capitato di leggere quel libro proprio ora. Questa parte del testo nel libro è un refuso! Ecco il contesto:

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

Domanda: qual è il tempo di esecuzione di questo codice?

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

Risposta: O (n 2 ), dove n è il numero di lettere nella frase. Ecco perché: ogni volta che si aggiunge una stringa alla frase, si crea una copia della frase e si eseguono tutte le lettere della frase per copiarle. Se devi ripetere iterando fino a n caratteri ogni volta nel ciclo, e stai eseguendo il ciclo almeno n volte, questo ti dà un tempo di esecuzione O (n 2 ). Ahia! Con StringBuffer (o StringBuilder) puoi aiutare a evitare questo problema.

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

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

Hai notato che l’autore lo ha incasinato? La soluzione O (n 2 ) da lei menzionata (la prima) era esattamente la stessa di quella “ottimizzata” (quest’ultima). Quindi, la mia conclusione è che l’autore stava cercando di rendere qualcos’altro, come ad esempio copiare sempre la vecchia frase in un nuovo buffer quando si aggiunge ogni stringa successiva, come l’esempio di un algoritmo O (n 2 ). StringBuffer non dovrebbe essere così sciocco, come l’autore ha anche menzionato “With StringBuffer (o StringBuilder) può aiutare a evitare questo problema”.

È un po ‘difficile rispondere a una domanda sulla complessità di questo codice quando è scritto ad alto livello che astrae i dettagli dell’implementazione. La documentazione Java non sembra dare alcuna garanzia in termini di complessità della funzione append . Come altri hanno sottolineato, la class StringBuffer può (e deve) essere scritta in modo che la complessità delle stringhe di accodamento non dipenda dalla lunghezza corrente della stringa contenuta in StringBuffer .

Tuttavia, sospetto che non sia così utile per la persona che fa questa domanda semplicemente dire “il tuo libro è sbagliato!” – invece, vediamo quali sono le ipotesi fatte e chiariamo cosa stava cercando di dire l’autore.

Puoi fare le seguenti ipotesi:

  1. La creazione di un new StringBuffer è O (1)
  2. Ottenere la stringa successiva w in words è O (1)
  3. Restituire sentence.toString è al massimo O (n).

La domanda è davvero quale sia l’ordine di sentence.append(w) , e questo dipende da come avviene all’interno di StringBuffer . Il modo ingenuo è farlo come Shlemiel il Pittore .

Il modo sciocco

Supponiamo di utilizzare una stringa con terminazione null in stile C per i contenuti di StringBuffer . Il modo in cui trovi la fine di tale stringa è leggendo ogni carattere, uno alla volta, finché non trovi il carattere nullo – quindi per aggiungere una nuova stringa S, puoi iniziare a copiare i caratteri da S alla stringa StringBuffer (finendo con un altro carattere null). Se scrivi append questo modo, è O ( a + b ), dove a è il numero di caratteri attualmente in StringBuffer , e b è il numero di caratteri nella nuova parola. Se si esegue il loop su un array di parole e ogni volta che si devono leggere tutti i caratteri appena aggiunti prima di aggiungere la nuova parola, la complessità del ciclo è O (n ^ 2), dove n è il numero totale di caratteri in tutte le parole (anche il numero di caratteri nella frase finale).

Un modo migliore

D’altra parte, supponiamo che il contenuto di StringBuffer sia ancora una matrice di caratteri, ma memorizziamo anche una size intera che ci dice quanto è lunga la stringa (numero di caratteri). Ora non dobbiamo più leggere ogni carattere in StringBuffer per trovare la fine della stringa; possiamo solo cercare la size dell’indice nella matrice, che è O (1) invece di O ( a ). Quindi la funzione append ora dipende solo dal numero di caratteri aggiunti, O ( b ). In questo caso la complessità del ciclo è O (n), dove n è il numero totale di caratteri in tutte le parole.

… Non abbiamo ancora finito!

Infine, c’è un altro aspetto dell’implementazione che non è stato ancora trattato, ed è quello effettivamente sollevato dalla risposta nel libro di testo – allocazione di memoria. Ogni volta che vuoi scrivere più caratteri sul tuo StringBuffer , non ti è garantito spazio sufficiente nel tuo array di caratteri per adattarsi effettivamente alla nuova parola. Se non c’è abbastanza spazio, il tuo computer deve prima allocare un po ‘di spazio in più in una sezione pulita della memoria, quindi copiare tutte le informazioni nel vecchio array StringBuffer e poi continuare come prima. La copia di dati come questa richiede O ( a ) tempo (dove a è il numero di caratteri da copiare).

Nel peggiore dei casi, devi allocare più memoria ogni volta che aggiungi una nuova parola. Questo in pratica ci riporta al punto in cui il ciclo ha complessità O (n ^ 2) ed è ciò che il libro sembra suggerire. Se si suppone che non stia accadendo nulla di pazzo (le parole non si allungano a un ritmo esponenziale !), Allora si può probabilmente ridurre il numero di allocazioni di memoria a qualcosa di più simile a O (log (n)) facendo crescere la memoria allocata in modo esponenziale. Se questo è il numero di allocazioni di memoria e le allocazioni di memoria in generale sono O ( a ), allora la complessità totale attribuita solo alla gestione della memoria nel ciclo è O (n log (n)). Poiché il lavoro di aggiunta è O (n) e inferiore alla complessità della gestione della memoria, la complessità totale della funzione è O (n log (n)).

Ancora una volta, la documentazione Java non ci aiuta in termini di crescita della capacità di StringBuffer , dice semplicemente “Se il buffer interno fuoriesce, viene automaticamente ingrandito”. A seconda di come accade, si potrebbe finire con O (n ^ 2) o O (n log (n)) nel complesso.

Come esercizio lasciato al lettore: trovare un modo semplice per modificare la funzione in modo che la complessità complessiva sia O (n), rimuovendo i problemi di riallocazione della memoria.

La risposta accettata è semplicemente sbagliata. StringBuffer ha ammortizzato O (1) append, quindi n appends sarà O ( n ).

Se non fosse O (1) append, StringBuffer avrebbe ragione di esistere, dal momento che scrivere quel loop con una semplice concatenazione di String sarebbe O ( n ^ 2)!

Ho provato a controllarlo usando questo programma

 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); } } 

E il risultato era, come previsto, O (n):

java Test 200000 - 128 ms

java Test 500000 - 370 ms

java Test 1000000 - 698 ms

Versione 1.6.0.21

Penso che questi testi nel libro debbano essere un refuso, penso che il contenuto giusto sia sotto, lo aggiusto:

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

Domanda: qual è il tempo di esecuzione di questo codice?

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

Risposta: O (n 2 ), dove n è il numero di lettere nella frase. Ecco perché: ogni volta che si aggiunge una stringa alla frase, si crea una copia della frase e si eseguono tutte le lettere della frase per copiarle. Se devi ripetere iterando fino a n caratteri ogni volta nel ciclo, e stai eseguendo il ciclo almeno n volte, questo ti dà un tempo di esecuzione O (n 2 ). Ahia! Con StringBuffer (o StringBuilder) puoi aiutare a evitare questo problema.

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

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

Ho ragione?

Questo dipende molto dall’implementazione di StringBuffer . Supponendo che .append() fosse un tempo costante, è chiaro che si ha un algoritmo O(n) nel tempo in cui n = length of the words array . Se .append non è un tempo costante, avrai bisogno di più O (n) per la complessità temporale del metodo. Se in effetti l’attuale implementazione di StringBuffer copia le stringhe carattere per carattere, allora l’algoritmo sopra è

Θ(n*m) o O(n*m) , dove n è il numero di parole e m è la lunghezza media delle parole, e il tuo libro è sbagliato. Presumo che tu stia cercando un limite stretto.

Semplice esempio che la risposta del libro non è corretta: String[] words = ['alphabet'] Secondo la definizione del libro, n=8 , quindi l’algoritmo sarà limitato da 64 passi. È questo il caso? Chiaramente non rigorosamente. Vedo 1 incarico e 1 operazione di copia con n caratteri, quindi ottieni circa 9 passaggi. Questo tipo di comportamento è previsto dai limiti di O(n*m) , come ho illustrato sopra.

Ho fatto qualche ricerca, e chiaramente non è una semplice copia di un personaggio. Sembra che la memoria sia stata copiata in blocco, il che ci riporta a O(n) , la tua prima ipotesi sulla soluzione.

 /* 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); } 

Il tuo libro è vecchio, terribile o entrambi. Non sono abbastanza determinato da scavare nelle versioni di JDK per trovare un’implementazione meno ottimale di StringBuffer, ma forse ne esiste una.

C’è un errore di battitura in questo libro.


1 ° caso :

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

Complessità: O (n ^ 2) -> (n parole) x (n caratteri copiati ad ogni iterazione, per copiare la frase corrente in un StringBuffer)


2 ° caso :

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

Complessità: O (n) -> (n parole) x O (1) (complessità ammortizzata per la concatenazione di StringBuffer)

Come la spiegazione fornita nel libro, per sempre la parola nell’array di stringhe viene creato un nuovo object di frase e quell’object frase copia prima la frase precedente e poi attraversa fino alla fine dell’array e quindi aggiunge la nuova parola, quindi la complessità di n^2 .

  1. Prima ‘n’ per copiare la frase precedente in un nuovo object
  2. Secondo ‘n’ per attraversare quella matrice e quindi aggiungerla

Quindi n*n sarà n^2 .

Sembra O (n) per me (con n è il numero totale di lettere in tutte le parole). Stai praticamente iterando su ogni carattere in words per aggiungerlo nel StringBuffer .

L’unico modo in cui potrei vedere questo come O (n ^ 2) è se append() itera tutti i contenuti nel buffer prima di aggiungere nuovi caratteri. E potrebbe effettivamente farlo occasionalmente se il numero di caratteri supera la lunghezza del buffer attualmente assegnata (deve allocare un nuovo buffer e quindi copiare tutto dal buffer corrente nel nuovo buffer). Ma non succederà ad ogni iterazione, quindi non avrai ancora O (n ^ 2).

Al massimo avresti O (m * n), dove m è il numero di volte in cui la lunghezza del buffer è aumentata. E poiché lo StringBuffer raddoppierà la sua dimensione del buffer ogni volta che assegna un buffer più grande, possiamo determinare che m è all’incirca uguale a log2(n) (in realtà log2(n) - log2(16) , poiché la dimensione del buffer iniziale predefinita è 16 di 1).

Quindi la vera risposta è che l’esempio del libro è O (n log n), e che puoi ottenerlo a O (n) preallando un StringBuffer con una capacità abbastanza grande da contenere tutte le tue lettere.

Si noti che in Java l’accodamento a una stringa usando += mostra il comportamento inefficiente descritto nella spiegazione del libro, poiché deve allocare una nuova stringa e copiare tutti i dati di entrambe le stringhe in essa contenuti. Quindi se lo fai, è O (n ^ 2):

 String sentence = ""; for (String w : words) { sentence += w; } 

Ma l’uso di StringBuffer non dovrebbe generare lo stesso comportamento dell’esempio precedente. Questo è uno dei principali motivi per cui StringBuffer esiste in primo luogo.

Ecco i miei calcoli per come hanno ottenuto O (n ^ 2)

Ignoreremo il tempo di CPU per la dichiarazione di StringBuffer, in quanto non varia con la dimensione della stringa finale.

Quando calcoliamo la complessità O ci occupiamo del caso peggiore, questo si verificherà quando ci sono stringhe di 1 lettera. Spiegherò dopo questo esempio:

Diciamo che abbiamo 4 stringhe di una sola lettera: “A”, “B”, “C”, “D”.

Leggi in A: CPU-time per trovare la fine di StringBuffer: 0 CPU-time per aggiungere ‘A’: 1

Leggi in B: CPU-time per trovare la fine di StringBuffer: 1 CPU-time per aggiungere “B”: 1

Leggi in C: CPU-time per trovare la fine di StringBuffer: 2 CPU-time per aggiungere “C”: 1

Leggi in D: CPU-time per trovare la fine di StringBuffer: 3 CPU-time per aggiungere “D”: 1

CPU-time per copiare StringBuffer in String alla fine: 4

Tempo totale CPU = 1 + 2 + 3 + 4 + 4

Se generalizziamo questo a n parole di 1 lettera:

1 + 2 + 3 + …… + n + n = 0.5n (n + 1) + n

L’ho fatto usando la formula per la sum di una sequenza aritmetica.

O (0.5n ^ 2 + 1.5n) = O (n ^ 2).

Se usiamo parole di più lettere, dovremo trovare la fine di StringBuffer meno frequentemente, portando a un tempo di CPU inferiore e un caso “migliore”.