Arrays.equals()의 시간 복잡도

Question

두 개의 문자열에서 두 개의 char 배열이 생성되었습니다. 배열이 같음을 확인하고 싶습니다.

str1Array = str1.toCharArray(); 
str2Array = str2.toCharArray(); 

나의 이해는 배열 객체가 메모리에서 같은 객체가있는 경우 str1Array.equals(str2Array) 만 true를 반환 할 것입니다. 각 인덱스가 같은지 여부를 확인하려면 사용해야합니다. Arrays.equals(str1Array, str2Array)

이 같음 메서드의 복잡성에 대해 궁금합니다.

O(1) 각 인덱스에 대한 동일성을 확인하지 않고 배열 개체의 콘텐츠 같음을 평가할 수 없으므로이를 가정 할 수 없습니다. 내 생각 엔 O(n)입니다. n은 min(str1Array.length, str2Array.length)에 해당합니다.

그렇지 않으면 다른 사람이이를 확인할 수 있습니까?

Answer 1

음, 소스 코드를 살펴 보자 :

public static boolean equals(Object[] a, Object[] 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++) { 
     Object o1 = a[i]; 
     Object o2 = a2[i]; 
     if (!(o1==null ? o2==null : o1.equals(o2))) 
      return false; 
    } 

    return true; 
} 

을 (그것은 방법의 다른 변화에 대해 동일한 관하여).

우리가 볼 수 있듯이 배열을 반복합니다. 따라서 최악의 경우의 복잡도는 O(n)입니다. 여기서 n은 비교 한 배열의 길이입니다. 배열의 크기가 다른 경우 배열은 즉시 종료되어 O(1)이됩니다.

그러나 항상 오래 걸리지는 않습니다. 평등, 널 확인 및 길이 확인에 대한 몇 가지 전제 조건을 가지고 있습니다. 또한 경기가 발견되는 즉시 종료되므로 시간이 많이 걸릴 수 있습니다.