Tôi đã được nói những điều khác nhau về khóa học của mình về thuật toán, và tự hỏi liệu tôi có thể nhận được câu trả lời dứt khoát về độ phức tạp của lệnh System.out.println() của Java hay không.Độ phức tạp về thời gian của system.out.println
Ví dụ: độ phức tạp của thời gian sau đây đối với N là bao nhiêu?
String stringy = "";
while(stringy.length() < N) {
System.out.println(stringy);
stringy += "X";
}
Cảm ơn bạn đã giúp đỡ người mới!
Độ phức tạp thời gian của mã này là O (N * N) vì đó là vòng lặp N lần in. Tôi không biết những gì bạn đã được nói nhưng thời gian phức tạp của in ấn nó không tồi tệ hơn sau đó O (N) trong Java.
trong mã của bạn bạn thêm "X" để mỗi dòng, và therefor in ấn của bạn sẽ là:
X
XX
XXX
XXXX
XXXXX
XXXXXX
.
.
.
do đó, nó phức tạp được tính như một Arithmetic progression và chúng tôi nhận được:
(1+N)*N/2=O(N^2)
để đọc về cách hoạt động của lệnh bạn có thể đọc here hoặc here:
Có một khái niệm chung rằng các SOP có hiệu suất kém. Khi chúng tôi phân tích sâu, chuỗi các cuộc gọi giống như println -> print -> write() + newLine(). Luồng chuỗi này là việc triển khai Sun/Oracle JDK. Cả hai hàm write() và newLine() chứa một khối được đồng bộ hóa. Đồng bộ hóa có một ít chi phí, nhưng nhiều hơn chi phí của việc thêm các ký tự vào bộ đệm và in cao.
Khi chúng tôi chạy phân tích hiệu suất, hãy chạy nhiều số SOP và ghi lại thời gian, thời gian thực hiện tăng tương ứng. Hiệu suất giảm khi chúng tôi in nhiều hơn 50 ký tự và in hơn 50.000 dòng.
Tất cả phụ thuộc vào kịch bản chúng tôi sử dụng. Dù có thể là gì, hãy làm không sử dụng System.out.println để ghi nhật ký.
Nếu bạn thừa nhận rằng vòng lặp chạy N lần, và đó là một hoạt động 'O (n)', làm thế nào bạn có thể nói rằng toàn bộ mã là 'O (n)'? – corsiKa
@corsiKa bạn hoàn toàn chính xác, và tôi đã không hoàn thành cà phê buổi sáng của mình, tôi sẽ chỉnh sửa nó và thêm ví dụ –
@corsiKa vào đây, chỉnh sửa –
Độ phức tạp của thời gian là System.out.println(stringy); lệnh ???
Về cơ bản, độ phức tạp của thời gian không liên quan đặc biệt đến một mã hoặc ngôn ngữ cụ thể mà về cơ bản nó có nghĩa là thời gian về mặt lý thuyết sẽ được thực hiện theo dòng mã. Điều này thường phụ thuộc vào hai hoặc ba điều:
Bây giờ trong phần này của mã của bạn:
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";
}
Nó rõ ràng sẽ phụ thuộc vào kích thước đầu vào, tất nhiên là độ dài của chuỗi. Đầu tiên vòng lặp while thực hiện ít hơn N (vì điều kiện stringy.length() < N làm cho nó <= sẽ làm cho nó chạy qua toàn bộ chiều dài của chuỗi) mà chúng ta có thể nói theo thứ tự của N và in chuỗi sẽ được thực hiện theo thứ tự trong tổng số mã N sẽ có thời gian chạy là O(N^2)
Độ phức tạp của mã này là O(n^2). Nó lặp lại vòng lặp N lần, và vì System.out.println phải in từng ký tự, in từ 0 đến N ký tự mỗi lần lặp, trung bình N/2, bạn thả hằng số, N * N = N^2. Theo cách tương tự, việc thêm vào chuỗi sẽ làm cho toàn bộ chuỗi được sao chép (Các chuỗi không thay đổi trong Java, vì vậy bất kỳ thay đổi nào có nghĩa là bạn phải sao chép toàn bộ chuỗi thành một chuỗi mới). Đây là một hoạt động tuyến tính khác. Vì vậy, bạn có n * (n/2 + n/2) vẫn còn trên thứ tự bậc hai - 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
}
Độ phức tạp về thời gian cho bạn biết thuật toán của bạn phải làm bao nhiêu công việc hơn, tăng hoặc lấy một số hệ số không đổi.
Vì vậy, một phức tạp ràng buộc trên của O (2 N) bằng với độ phức tạp O (23.587 N) vì định nghĩa thực tế tìm thấy ở đây
http://en.wikipedia.org/wiki/Big_O_notation
bang rằng hệ số có thể được bất kỳ số lượng bất kể có bao lớn, miễn là nó được cố định liên quan đến kích thước của đầu vào.
bởi vì bạn đang không sử dụng 'N' trong vòng lặp, bạn chỉ thêm một char vào một String, khối lượng công việc mỗi lần lặp bằng bao nhiêu lần lặp bạn có -> O (N)
nếu bạn có "stringy + = stringy;" thay vào đó nó sẽ là O (N^2) vì mỗi lần lặp bạn đang tăng gấp đôi số lượng công việc bạn phải làm
* * LƯU Ý
Tôi giả định system.out.print là một tuyên bố nguyên tử, tức là nó sẽ in tất cả các nhân vật như một hành động đơn lẻ .. nếu nó được in từng nhân vật riêng rẽ sau đó O của nó (N^2) ....
Đó là 'O (N^2)' thậm chí không có println, bởi vì việc thêm ký tự vào chuỗi cũng là một phép toán tuyến tính. NẾU bạn đã thêm 's + = s' như bạn đề nghị, AND println là hằng số (nó không phải là) so với toàn bộ mã sẽ là' O (n lg n) '. – corsiKa
một câu trả lời tuyệt vời có thể được tìm thấy ở đây: http://www.quora.com/What-exactly-is-the-time-complexity-for-System-out-println-in-Java-O-1-or-O-N
các chính ý tưởng là in một chuỗi là thực sự sao chép nó vào stdout - và chúng ta biết rằng bản sao của một chuỗi là o (n).
Phần thứ hai nói rằng bạn có thể thử in nhiều lần: - một ký tự - Một chuỗi rất lớn Và bạn sẽ thấy sự khác biệt về thời gian !! (nếu in sẽ là o (1) bạn sẽ không)
Nó luôn luôn là tốt xem xét một phần quan trọng của liên kết trong câu trả lời. – serenesat
Bạn đã có một vòng lặp vô hạn nếu N lớn hơn 0. Vì vậy, đó sẽ là O (Vô cực). Chức năng sẽ không hoàn thành. –
Nó không phải là một vòng lặp vô hạn. – Leigh
Độ phức tạp của các hoạt động này là O (n^2). '+ =' Là O (N) và bạn thực hiện N lần này. –