Java 中 Arrays.deepEquals() 的时间复杂度

Question

我正在尝试计算 java.util.Arrays deepEquals() 方法的时间复杂度。

我可以从源代码中了解到 equals() 方法在 O(n) 时间内运行，但是从 deepEquals() 方法推断时间复杂度并不是那么清楚。它在循环中运行，但也调用 deepEquals0 方法，该方法应该递归地检查元素是否相等？那么最坏的情况会是什么？

这是摘自 java.util.Arrays class 的片段：

public static boolean deepEquals(Object[] a1, Object[] a2) {
    if (a1 == a2)
        return true;
    if (a1 == null || a2==null)
        return false;
    int length = a1.length;
    if (a2.length != length)
        return false;

    for (int i = 0; i < length; i++) {
        Object e1 = a1[i];
        Object e2 = a2[i];

        if (e1 == e2)
            continue;
        if (e1 == null)
            return false;

        // Figure out whether the two elements are equal
        boolean eq = deepEquals0(e1, e2);

        if (!eq)
            return false;
    }
    return true;
}

static boolean deepEquals0(Object e1, Object e2) {
    assert e1 != null;
    boolean eq;
    if (e1 instanceof Object[] && e2 instanceof Object[])
        eq = deepEquals ((Object[]) e1, (Object[]) e2);
    else if (e1 instanceof byte[] && e2 instanceof byte[])
        eq = equals((byte[]) e1, (byte[]) e2);
    else if (e1 instanceof short[] && e2 instanceof short[])
        eq = equals((short[]) e1, (short[]) e2);
    else if (e1 instanceof int[] && e2 instanceof int[])
        eq = equals((int[]) e1, (int[]) e2);
    else if (e1 instanceof long[] && e2 instanceof long[])
        eq = equals((long[]) e1, (long[]) e2);
    else if (e1 instanceof char[] && e2 instanceof char[])
        eq = equals((char[]) e1, (char[]) e2);
    else if (e1 instanceof float[] && e2 instanceof float[])
        eq = equals((float[]) e1, (float[]) e2);
    else if (e1 instanceof double[] && e2 instanceof double[])
        eq = equals((double[]) e1, (double[]) e2);
    else if (e1 instanceof boolean[] && e2 instanceof boolean[])
        eq = equals((boolean[]) e1, (boolean[]) e2);
    else
        eq = e1.equals(e2);
    return eq;
}

提前致谢。

Answer 1

该方法对元素总数运行线性。如果我们用 n 表示它是 O(n).

听起来比实际情况要好，假设您有一个嵌套数组 int[][][]，例如：

{                     // int[][][]
    { 1, 2, 3 },      // int[]
    { 4, 5 },         // int[]
    {                 // int[][]
        { 6, 7, 8 },  // int[]
        { 9 }         // int[]
    }
}

那么我们总共有 9 int 个值。 n 我的意思是那些 9 元素，而不是外部结构数组的 4。它在 n.

上线性运行

同样，我不是在谈论 outer.length（即 4），我是在谈论如果您完全遵循整个结构，如果您将其展平，则元素的实际数量。实际上不可能用 outer.length 来表达复杂度，因为它完全不相关。证明这一点的小例子：

{
    {
        { 1, 2, 3, 4, ..., 1_000_000 }
    }
}

这里的input.length只是1，但实际的元素数量是相当庞大的。你看，它是无关的。

之所以再次调用自己是因为，假设你有一个Object[][][][]（4个维度），那么你还必须检查这些维度的所有。所以它真的检查了所有元素。

Answer 2

我要稍微推翻 "linear in the number of total objects" 的想法，因为输入是 Object 的数组还是 Object[] 的数组实际上并不重要或其他任何东西。真正重要的是你如何定义你的big-O符号。即：如果您想将算法的 big-O 与输入的大小相关联，则必须知道 "the size of your input" 是什么 。 您必须在 O(n) 中定义 n。例如：

您的输入是 size = n 的 MyObject[]，其中 MyObject 有一个需要 k 工作的 equals 方法，其中 k 是一个常数。 deepEquals() 的运行时间是多少？嗯，你正在做 k 次工作，n 次，所以你得到 O(n*k)，抛出常量得到 O(n)。太棒了！
接下来，您的输入是 MyObject[][]，其中 top-level 数组的大小为 n，嵌套数组的大小为 j，一个不变。什么是运行时间？ n 个子数组，每个长度 j，其中每个 MyObject 需要 k 工作。 O(n*j*k)，抛出常量再次得到O(n)。注意我们的输入已经 j 倍大但是 big-O 没有改变，因为我们假设 j 是常数，即我们要问的问题是 "how does the runtime vary with changes in the length of the top-level array".
如果相反，我们问“运行时如何随着顶层数组长度的变化和嵌套数组长度的变化而变化？让我们的输入是大小n，嵌套数组大小 m，其中 不是常量 。现在我们得到 O(n*m*k)，抛出常量 k 得到 O(n*m)。如果我们要求我们的输入矩阵（嵌套数组）是正方形的，即 n = m，我们的运行时间现在是 O(n^2).

什么？？？？？

#2中，n是top-level数组的长度。我们选择忽略 sub-arrays 的长度可以变化的事实。

在#3 中，我们将这个事实内在化，并将 sub-arrays 的长度表示为 m，以便在 [= 时得到 n*m 或 n^2 41=].

我们可以更进一步:

如果 MyObject 的 equals 方法不占用 k 常数时间，而是 O(p)，其中 p 是collection 包含在 MyObject 中，那么上面#3 的运行时间变为 O(n*m*p) 其中 n*m 是 MyObject 的数量，而 p 是MyObject 的 collection 和 的大小，您可以一直这样做 。

结果是 big-O 表示法是 bound，当你假设某些事情时它是有效的。这些假设的主要部分（我们不经常想到）是每个变量（一个变量是一个真正可以改变的东西）不在 O() 括号内没关系，因为括号内的是的东西使它黯然失色。这意味着根据 n 是否比 m 重要得多，您可以说 #3 在 O(n) 内并且 #3 在 O(n*m) 内并且是正确的，根据你的假设。

Java 中 Arrays.deepEquals() 的时间复杂度

Time complexity of Arrays.deepEquals() in Java

java

arrays

time-complexity

big-o

deepequals