Xin chào, tôi muốn biết độ phức tạp về thời gian của hàm "replaceAll" của lớp String nhưng tôi không thể tìm thấy bất kỳ thông tin nào về nó. (http://docs.oracle.com/javase/6/docs/api/java/lang/String.html)Tại sao Java không bao gồm độ phức tạp về thời gian/không gian của mỗi hàm trong javadoc?
Sẽ tốt hơn nếu Java đưa vào sự phức tạp trong Javadoc? Tôi tin rằng đó là một điều rất quan trọng đối với một ai đó để biết.
Hầu hết các chức năng có độ phức tạp tương đối thẳng về phía trước. AFAIK, replaceAll là O (n)
IMHO. Không có gì tự mình đánh bại thử nghiệm này, ví dụ: với một hồ sơ, bởi vì rất có khả năng là 99% các phương pháp bạn sử dụng có ít hoặc không ảnh hưởng đến hiệu suất của ứng dụng của bạn.
Mức độ phức tạp có thể được ghi lại nếu được đảm bảo. Ví dụ, một số các lớp bộ sưu tập tài liệu phức tạp đảm bảo. Ví dụ, từ HashMap:
thực hiện này cung cấp hiệu suất không đổi theo thời gian cho các hoạt động cơ bản (get và put) ...
Tuy nhiên, đôi khi sự phức tạp là:
Các javadocs của API Java chỉ định một hợp đồng chung của những gì phải được thực hiện theo từng phương pháp, không phải cách. Mỗi người triển khai API (ví dụ, OpenJDK, JDK của Oracle, v.v.) có một sự tự do nhất định về cách thực hiện từng hợp đồng và quyền tự do đó có thể bao gồm việc tối ưu hóa, thậm chí hy sinh hiệu suất. Vì vậy, các javadocs nói chung không chỉ rõ các chi tiết như thời gian/độ phức tạp của các hàm, trừ khi nó hoàn toàn cần thiết cho một phương thức để đáp ứng các yêu cầu hiệu suất nhất định.
Nếu bạn đang sử dụng không gian/thời gian phức tạp của các hoạt động cơ bản để đưa ra quyết định thiết kế, thì bạn gần như chắc chắn làm sai.
Trước tiên hãy tạo ứng dụng chính xác, sau đó sắp xếp nó. Sau đó, tối ưu hóa quy trình lược tả sẽ hiển thị như những nút cổ chai.
Câu trả lời chung là độ phức tạp thường phụ thuộc vào các yếu tố quá khó phân tích. Điều này chắc chắn áp dụng cho String.replaceAll, trong đó độ phức tạp hiệu quả phụ thuộc rất lớn vào chuỗi regex. (Một regex được thiết kế kém có thể làm cho phù hợp với veerryyy chậm.)