Złożoność czasu system.out.println

Question

Powiedziano mi o różnych rzeczach na temat algorytmów i zastanawiałem się, czy mogę uzyskać ostateczną odpowiedź na temat złożoności czasowej polecenia Java System.out.println().

Na przykład, jaka byłaby złożoność czasu w odniesieniu do N?

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

Dzięki za pomoc nowemu facetowi!

Answer 1

Czas złożoności tego kodu to O (N * N), ponieważ jest to pętla N razy, która drukuje. Nie wiem, co ci powiedziano, ale złożoność czasu drukowania nie jest gorsza niż O (N) w Javie.

w kodzie dodać znak „X” na każdej linii, i do nich swoją drukowanie będzie:

X 
XX 
XXX 
XXXX 
XXXXX 
XXXXXX 
. 
. 
. 

więc złożoność jest obliczana jako Arithmetic progression i otrzymujemy:

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

do przeczytać, w jaki sposób praca poleceń można przeczytać here lub here:

Istnieje ogólna koncepcja, że ​​standardowe procedury operacyjne są złe w działaniu. Gdy analizujemy głęboko, sekwencja wywołań przypomina println -> print -> write() + newLine(). Ten sekwencyjny przepływ jest implementacją Sun/Oracle JDK. Zarówno write(), jak i newLine() zawierają zsynchronizowany blok . Synchronizacja ma niewielki narzut, ale więcej niż koszt dodania znaków do bufora i drukowania jest wysoki.

Po uruchomieniu analizy wydajności, uruchom wiele SOP i nagraj czas, czas realizacji wzrasta proporcjonalnie. Wydajność pogarsza się, gdy wydrukujemy więcej niż 50 znaków i wydrukujemy ponad 50 000 linii.

Wszystko zależy od tego, z jakiego scenariusza go używamy. Niezależnie od okoliczności, nie należy używać System.out.println do logowania się na standardowe wyjście.

Answer 2

Złożoność czasowa polecenia System.out.println(stringy); ???

Zasadniczo rozumie złożoność czas Fragment kodu above.Look, czas złożoność nie jest szczególnie związany z jednym konkretnym kodem lub języka to w zasadzie oznacza, ile czasu teoretycznie zostanie podjęta przez linię kodu. To zazwyczaj zależy od dwóch lub trzech rzeczy:

• wielkości wejściowych
• stopień wielomianu (w przypadku rozwiązywania równań wielomianowych)

Teraz w tej części kodu:

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

Oczywiście będzie to zależeć od wielkości wejścia, która jest oczywiście długością struny. Najpierw pętla while wykonuje trochę mniej niż N (z powodu warunku stringy.length() < N, dzięki czemu <= spowoduje, że będzie przebiegać przez całą długość ciągu), co możemy powiedzieć w kolejności N i drukowanie ciągu znaków zostanie wykonane w kolejności N, więc całkowity kod będzie miał czas działania O(N^2)

Answer 3

Złożoność tego kodu to O(n^2). It iteruje pętlę N razy, a ponieważ System.out.println musi wydrukować każdy znak, który drukuje od 0 do N znaków w każdej iteracji, uśredniając N/2, upuszczasz stałą, N * N = N^2. W ten sam sposób dodanie do napisu spowoduje skopiowanie całego ciągu znaków (Ciągi są niezmienne w Javie, więc wszelkie zmiany oznaczają, że musisz skopiować cały łańcuch na nowy ciąg). To kolejna liniowa operacja. Więc masz n * (n/2 + n/2) jest nadal na porządku kwadratowym - 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

czas złożoność powie Ci, jak dużo więcej pracy Twój algorytm ma robić za przyrost wielkości wejściowej, lub dać jakiś stały współczynnik.

więc górną granicę złożoność O (2 n) jest równa złożoności O (23.587 N), ponieważ okazało się, że rzeczywista definicja tutaj

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

stany że współczynnik może być dowolną liczbę nie ważne jak duże, o ile jest ono ustalone w odniesieniu do rozmiaru danych wejściowych.

ponieważ nie używasz „n” w pętli, jesteś po prostu dodanie char na ciąg znaków, ilość pracy za iteracji jest równa ile powtórzeń masz -> O (N)

jeśli masz "stringy + = stringy;" zamiast byłoby O (n^2), ponieważ każda iteracja jesteś podwojenie ilości pracy trzeba zrobić

* * UWAGA

jestem zakładając System.out.print jest stwierdzenie atomowej, tzn drukuje wszystkie znaki jako pojedynczy działania .. jeśli drukowane każdy znak indywidualnie następnie swoją o (n^2) ....

Answer 5

wielki odpowiedź można znaleźć tutaj: http://www.quora.com/What-exactly-is-the-time-complexity-for-System-out-println-in-Java-O-1-or-O-N

głównym Pomysł polega na tym, że drukowanie ciągu jest w rzeczywistości kopiowaniem go na standardowe wyjście - i wiemy, że kopia ciągu jest o (n).

Druga część mówi, że można spróbować drukowania dużej liczby godzinach: - jeden znak - bardzo duży ciąg I widać różnicę czasu !! (jeśli drukowanie byłoby o (1) to nie byłoby)