La complessità del tempo di system.out.println

Question

Mi è stato detto cose diverse nel corso del mio corso sugli algoritmi e mi chiedevo se avrei potuto ottenere una risposta definitiva sulla complessità temporale del comando System.out.println() di Java.

Ad esempio, quale sarebbe la complessità temporale di quanto segue, rispetto a N?

String stringy = ""; 
while(stringy.length() < N) { 
    System.out.println(stringy); 
    stringy += "X"; 
} 

Grazie per l'aiuto del nuovo ragazzo!

Answer 1

la complessità temporale di questo codice è O (N * N) perché è un ciclo di N volte che viene stampato. Non so cosa ti è stato detto, ma la complessità temporale della stampa non è peggiore di O (N) in Java.

nel codice si aggiunge "X" per ciascuna linea, e per questo la stampa sarà:

X 
XX 
XXX 
XXXX 
XXXXX 
XXXXXX 
. 
. 
. 

quindi è la complessità è calcolato come Arithmetic progression e otteniamo:

(1+N)*N/2=O(N^2) 

a continuate a leggere come il lavoro di comando si può leggere here o here:

Esiste una nozione generale secondo cui le SOP hanno prestazioni scadenti. Quando analizziamo in profondità , la sequenza di chiamate è come println -> print -> write() + newLine(). Questo flusso di sequenza è un'implementazione di Sun/Oracle JDK. Write() e newLine() contengono un blocco sincronizzato . La sincronizzazione ha un piccolo sovraccarico, ma più di quello del costo dello di aggiungere caratteri al buffer e la stampa è alta.

Quando eseguiamo un'analisi delle prestazioni, eseguiamo più numeri di SOP e registriamo l'ora, la durata dell'esecuzione aumenta proporzionalmente. Le prestazioni si riducono quando si stampano più di 50 caratteri e si stampa oltre 50.000 righe.

Tutto dipende dallo scenario che usiamo. Qualunque sia il caso, fare non utilizzare System.out.println per accedere allo stdout.

Answer 2

Complessità di tempo del comando System.out.println(stringy); ???

Che, fondamentalmente, significava la complessità temporale del frammento di codice above.Look, tempo di complessità non è particolarmente legato a uno specifico codice o linguaggio fondamentalmente significa quanto tempo teoricamente sarà presa dalla riga di codice. Questo di solito dipende da due o tre cose:

• dimensione dell'input
• grado di un polinomio (in caso di risoluzione di equazioni polinomiali)

Ora, in questa parte del codice:

String stringy = ""; 
while(stringy.length() < N) {// the loop will execute in order of N times 
    System.out.println(stringy);//println will execute in order of N times too as in printing each character 
    stringy += "X"; 
} 

Dipenderà ovviamente dalla dimensione dell'input che è ovviamente la lunghezza della stringa. Prima il ciclo while viene eseguito meno di N (a causa della condizione stringy.length() < N che lo rende <= lo farà scorrere per l'intera lunghezza della stringa) che possiamo dire nell'ordine di N e la stampa della stringa verrà eseguita nell'ordine di N quindi il codice complessivo avrà un tempo di esecuzione di O(N^2)

Answer 3

La complessità di questo codice è O(n^2). It itera il ciclo N volte, e poiché System.out.println deve stampare ogni carattere, che stampa da 0 a N caratteri ogni iterazione, facendo una media di N/2, si rilascia la costante, N * N = N^2. Allo stesso modo, l'aggiunta alla stringa causerà la copia dell'intera stringa (le stringhe sono immutabili in Java, quindi qualsiasi modifica significa che devi copiare l'intera stringa in una nuova stringa). Questa è un'altra operazione lineare. Quindi hai n * (n/2 + n/2) ancora in ordine quadratico - O(n^2).

String stringy = ""; 
while(stringy.length() < N) { // will iterate N times 
    System.out.println(stringy); // has to print N letters 
    stringy += "X"; // has to copy N letters into a new string 
} 

Answer 4

complessità temporale ti dice quanto più lavorare l'algoritmo ha a che fare per incremento della dimensione dell'input, dare o prendere qualche coefficiente costante.

Quindi una complessità limite superiore di O (2 N) è uguale a complessità O (23587 N), perché la definizione stessa trovato qui

http://en.wikipedia.org/wiki/Big_O_notation

afferma che il coefficiente può essere qualsiasi numero, non importa quanto grande, a patto che sia fissato in base alla dimensione dell'input.

perché non si utilizza 'N' all'interno del ciclo, si sta solo aggiungendo un char a una stringa, la quantità di lavoro per ogni iterazione è uguale a quante iterazioni che hai -> O (N)

se avessi "stringy + = stringy;" invece sarebbe O (N^2) perché ogni iterazione stai raddoppiando la quantità di lavoro che dovete fare

* * NOTA

Io parto dal presupposto System.out.print è una dichiarazione atomica, vale a dire che stampa tutti i personaggi come una singola azione .. se è stampato ogni carattere singolarmente poi il suo O (N^2) ....

Answer 5

una grande risposta può essere trovata qui: http://www.quora.com/What-exactly-is-the-time-complexity-for-System-out-println-in-Java-O-1-or-O-N

Il principale l'idea è che la stampa di una stringa è in realtà copiandola allo stdout - e sappiamo che la copia di una stringa è o (n).

La seconda parte dice che si può provare a stampare un gran numero di volte: - un carattere - Una stringa di grandi dimensioni e vedrete la differenza di tempo !! (se la stampa fosse o (1) non lo faresti)