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)).

但是,它并不总是需要那么久.它确实有一些前提条件,用于相等,空检查和长度检查.一旦找到匹配,它也会退出,因此可能会花费更少的时间.