9

如标题所述， in 的运行时间是equals()多少java.util.Arrays？

例如，如果它比较两个int[]，它是否会遍历数组中的每个元素，所以 O(n)？对于javaequals()中各个类equals()中的所有内容，我们可以假设运行时总是 O(n) 吗？

谢谢。

4

4 回答 4

11

从源代码中获取（源代码价值 100 字：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;
}
于 2012-12-27T10:43:49.923 回答
8

如标题所述，java.util.Arrays 中默认 equals() 的运行时间是多少？

默认 equals 可能意味着 Object.equals。Arrays.equals() 通常是您真正想要的。

例如，如果它比较两个 int[]，它是否会遍历数组中的每个元素，所以 O(n)？

是的，这就是消息来源所暗示的。

对于java中所有默认的equals()，我们可以假设运行时总是O(n)吗？

对于某些集合，这是正确的，但对于树集合，它可以是 O(n log n)。HashMap 最坏的情况是 O(N^2) 因为非集合n没有意义。

于 2012-12-27T10:52:26.527 回答
6

它首先检查长度，如果相等，则遍历所有元素并在它们上调用 equals。

所以，如果你想忽略个人等价的成本，是的，那将是 O(n)。但是，例如，如果条目是字符串，它也会随着字符串变长而变长，而不仅仅是因为它们变得更多（因为比较本身也是 O(m)）。

于 2012-12-27T10:43:58.510 回答
0

javadoc 声明：如果两个数组以相同的顺序包含相同的元素，则它们是相等的。所以很明显，这将是一个 O(n) 操作，因为它需要遍历所有项目（至少如果它们都相等）。

默认equals（即Object#equals）是 O(1) 操作，它是一个简单的引用比较：

对于任何非空引用值 x 和 y，当且仅当 x 和 y 引用同一个对象（x == y 的值为 true）时，此方法才返回 true

于 2012-12-27T10:46:39.703 回答