Thời gian chạy bằng bằng() trong java.util.Arrays là gì?

Question

Như tiêu đề đã nêu, thời gian chạy của equals() trong java.util.Arrays là gì?

Ví dụ: nếu nó so sánh hai int[], nó có lặp qua mọi phần tử trong mảng không, vậy O (n)? Và đối với tất cả các equals() trong các lớp riêng lẻ 'equals() trong java, chúng ta có thể giả định rằng thời gian chạy luôn luôn là O (n) không?

Cảm ơn.

Answer 1

Như tiêu đề đã nói, thời gian chạy của bình đẳng mặc định() trong java.util.Arrays là gì?

Giá trị mặc định có thể có nghĩa là Object.equals. Các Arrays.equals() thường là những gì bạn thực sự muốn.

Ví dụ nếu nó so sánh hai int [], nó có lặp qua mọi phần tử trong mảng không, vậy O (n)?

có, đó là những gì nguồn đề xuất.

Và đối với tất cả các giá trị mặc định bằng() trong java, chúng ta có thể giả định rằng thời gian chạy luôn là O (n) không?

Đối với một số bộ sưu tập điều này đúng, nhưng đối với bộ sưu tập Tree, nó có thể là O (n log n). Trường hợp xấu nhất cho HashMap là O (N^2) Đối với các bộ sưu tập không n không có ý nghĩa.

Answer 2

thu thập từ mã nguồn (source code có giá trị 100 chữ: P):

/** 
* Returns <tt>true</tt> if the two specified arrays of ints are 
* <i>equal</i> to one another. Two arrays are considered equal if both 
* arrays contain the same number of elements, and all corresponding pairs 
* of elements in the two arrays are equal. In other words, two arrays 
* are equal if they contain the same elements in the same order. Also, 
* two array references are considered equal if both are <tt>null</tt>.<p> 
* 
* @param a one array to be tested for equality 
* @param a2 the other array to be tested for equality 
* @return <tt>true</tt> if the two arrays are equal 
*/ 
public static boolean equals(int[] a, int[] a2) { 
    if (a==a2) 
     return true; 
    if (a==null || a2==null) 
     return false; 

    int length = a.length; 
    if (a2.length != length) 
     return false; 

    for (int i=0; i<length; i++) 
     if (a[i] != a2[i]) 
      return false; 

    return true; 
} 

Answer 3

Nó kiểm tra đầu tiên theo chiều dài, và nếu bằng nhau, vòng qua tất cả các yếu tố và các cuộc gọi bằng vào chúng.

Vì vậy, nếu bạn muốn bỏ qua chi phí của cá nhân bằng, có, đó sẽ là O (n). Nhưng nếu các mục là Strings, ví dụ, nó cũng sẽ nhận được lâu hơn khi các chuỗi nhận được lâu hơn, không chỉ khi họ nhận được nhiều hơn (vì so sánh mình là O (m) là tốt).

Answer 4

javadoc states: hai mảng bằng nhau nếu chúng chứa cùng một phần tử theo cùng một thứ tự. Vì vậy, rõ ràng rằng đây sẽ là một hoạt động O (n) vì nó sẽ cần phải lặp qua tất cả các mục (ít nhất là nếu chúng đều bình đẳng).

Các default equals (tức là Object # tương đương) là một O (1) hoạt động, nó là một sự so sánh tài liệu tham khảo đơn giản:

đối với bất kỳ giá trị tham chiếu không null x và y, phương pháp này trả về true nếu và chỉ nếu x và y đề cập đến cùng một đối tượng (x == y có giá trị thực)