Trong Java, với chuỗi x, chi phí thời gian chạy của s.length() là bao nhiêu? Có phải O (1) hoặc O (n)?

Question

Tôi đã nói với mã như:

for (int i = 0; i < x.length(); i++) { 
    // blah 
} 

thực sự là O (n^2) vì các cuộc gọi lặp đi lặp lại để x.length(). Thay vào đó, tôi nên sử dụng:

int l = x.length(); 
for (int i = 0; i < l; i++) { 
    // blah 
} 

Điều này có đúng không? Là chuỗi chiều dài được lưu trữ như là một thuộc tính số nguyên riêng của lớp String? Hoặc không String.length() thực sự đi bộ toàn bộ chuỗi chỉ để xác định chiều dài của nó?

Answer 1

Không, độ dài của chuỗi java là O (1) vì lớp chuỗi của java lưu trữ độ dài dưới dạng trường.

Lời khuyên bạn đã nhận được là đúng với C, trong số các ngôn ngữ khác, chứ không phải java. C strlen đi qua mảng char tìm kiếm ký tự kết thúc chuỗi. Joel đã nói về nó trên podcast, nhưng trong ngữ cảnh của C.

Answer 2

Theo this, độ dài là trường của đối tượng String.

Answer 3

Tôi không biết liên kết sẽ dịch tốt như thế nào, nhưng hãy xem source of String#length. Tóm lại, #length() có độ phức tạp O (1) vì nó chỉ trả lại một trường. Đây là một trong nhiều ưu điểm của các chuỗi bất biến.

Answer 4

Trái với những gì đã được nói cho đến thời điểm này, không có gì đảm bảo rằng String.length() là hoạt động liên tục trong số lượng ký tự chứa trong chuỗi. Cả javadocs cho lớp String cũng như Đặc tả Ngôn ngữ Java đều yêu cầu String.length là hoạt động liên tục trong thời gian.

Tuy nhiên, trong quá trình thực hiện của Sun, String.length() là hoạt động liên tục trong thời gian. Cuối cùng, thật khó để tưởng tượng tại sao việc thực hiện bất kỳ sẽ có một thời gian thực hiện không liên tục cho phương pháp này.

Answer 5

Bạn nên lưu ý rằng phương thức length() trả về số lượng điểm mã UTF-16, không nhất thiết giống với số ký tự trong tất cả các trường hợp.

OK, cơ hội thực sự ảnh hưởng đến bạn khá mỏng, nhưng không có hại khi biết điều đó.

Answer 6

Chuỗi lưu trữ độ dài trong một biến riêng biệt. Vì chuỗi là bất biến, độ dài sẽ không bao giờ thay đổi. Nó sẽ cần phải tính toán chiều dài chỉ một lần khi nó được tạo ra, điều này xảy ra khi bộ nhớ được cấp phát cho nó. Do đó O của nó (1)

Answer 7

Trong trường hợp bạn không biết bạn có thể viết nó theo cách này:

for (int i = 0, l = x.length(); i < l; i++) { 
    // Blah 
} 

Nó chỉ là một chút bụi từ l 's phạm vi nhỏ hơn.