java - Arrays.equals() 的时间复杂度

Question

我有两个从两个字符串生成的 char 数组。我想确定这两个数组是否相等。

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

我的理解是 str1Array.equals(str2Array) 只有当数组对象是内存中的同一对象时才会返回 true。如果我想检查每个索引是否相同，我应该使用 Arrays.equals(str1Array, str2Array)

我想知道这个 equals 方法的复杂性。

我假设它不能是 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))。

然而，它并不总是需要那么长时间。它确实有一些相等性、空值检查和长度检查的先决条件。它也会在找到匹配项后立即退出，因此花费的时间会少很多。