Độ phức tạp về thời gian của chuỗi con của Java()

Question

Độ phức tạp của phương pháp String#substring() trong Java là bao nhiêu?

Answer 1

câu trả lời mới

Tính cập nhật 6 trong đời Java 7, hành vi của substring thay đổi để tạo ra một bản sao - vì vậy mỗi String đề cập đến một char[] đó là không chia sẻ với bất kỳ đối tượng khác, như theo như tôi biết. Vì vậy, tại thời điểm đó, substring() trở thành một hoạt động O (n) trong đó n là các số trong chuỗi con.

Cũ câu trả lời: pre-Java 7

khống và - nhưng trong thực tế O (1), nếu khẳng định không có rác thải thu gom được yêu cầu, vv

Nó chỉ đơn giản xây dựng một String đối tượng mới đề cập đến cùng một cơ sở char[] nhưng với các giá trị bù và đếm khác nhau. Vì vậy, chi phí là thời gian thực hiện để thực hiện xác nhận và xây dựng một đối tượng mới (hợp lý nhỏ). Đó là O (1) theo như nó là hợp lý để nói về sự phức tạp của hoạt động mà có thể thay đổi theo thời gian dựa trên thu gom rác, CPU cache vv Đặc biệt, nó không trực tiếp phụ thuộc vào độ dài của chuỗi gốc hoặc chuỗi con .

Answer 2

O (1) vì không sao chép chuỗi gốc được thực hiện, nó chỉ tạo đối tượng trình bao bọc mới với thông tin bù khác nhau.

Answer 3

Thẩm phán cho chính mình sau, nhưng nhược điểm hiệu suất của Java nằm ở một nơi khác, không phải ở đây trong chuỗi con của chuỗi. Code:

public static void main(String[] args) throws IOException { 

     String longStr = "asjf97zcv.1jm2497z20`1829182oqiwure92874nvcxz,nvz.,xo" + 
       "aihf[oiefjkas';./.,z][p\\°°°°°°°°?!(*#&(@*&#!)^(*&(*&)(*&" + 
       "fasdznmcxzvvcxz,vc,mvczvcz,mvcz,mcvcxvc,mvcxcvcxvcxvcxvcx"; 
     int[] indices = new int[32 * 1024]; 
     int[] lengths = new int[indices.length]; 
     Random r = new Random(); 
     final int minLength = 6; 
     for (int i = 0; i < indices.length; ++i) 
     { 
      indices[i] = r.nextInt(longStr.length() - minLength); 
      lengths[i] = minLength + r.nextInt(longStr.length() - indices[i] - minLength); 
     } 

     long start = System.nanoTime(); 

     int avoidOptimization = 0; 
     for (int i = 0; i < indices.length; ++i) 
      //avoidOptimization += lengths[i]; //tested - this was cheap 
      avoidOptimization += longStr.substring(indices[i], 
        indices[i] + lengths[i]).length(); 

     long end = System.nanoTime(); 
     System.out.println("substring " + indices.length + " times"); 
     System.out.println("Sum of lengths of splits = " + avoidOptimization); 
     System.out.println("Elapsed " + (end - start)/1.0e6 + " ms"); 
    } 

Output:

substring 32768 times 
Sum of lengths of splits = 1494414 
Elapsed 2.446679 ms

Nếu nó là O (1) hay không, phụ thuộc. Nếu bạn chỉ tham chiếu cùng một chuỗi trong bộ nhớ, hãy tưởng tượng rất dài chuỗi dài, bạn tạo chuỗi con và dừng tham chiếu chuỗi dài. Sẽ không được tốt đẹp để phát hành bộ nhớ lâu dài?

Answer 4

Đó là O (1) trong các phiên bản Java cũ hơn - như Jon đã nói, nó vừa tạo một Chuỗi mới với cùng một ký tự cơ bản [], và độ lệch và chiều dài khác.

Tuy nhiên, điều này đã thực sự thay đổi bắt đầu với Java 7 update 6.

Các char [] chia sẻ đã bị loại, và bù đắp và các lĩnh vực chiều dài đã được gỡ bỏ. chuỗi con() bây giờ chỉ sao chép tất cả các ký tự vào một Chuỗi mới.

Ergo, chuỗi con là O (n) trong bản cập nhật Java 7 6

Answer 5

Hiện tại, tính phức tạp tuyến tính. Đây là sau khi sửa chữa một vấn đề rò rỉ bộ nhớ cho chuỗi con.

Vì vậy, từ Java 1.7.0_06 hãy nhớ rằng String.substring bây giờ có một sự phức tạp tuyến tính thay vì một hằng số.