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

Question

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

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

下面是摘自java.util.Arrays类的片段：

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

我要向后推一点“总对象数的线性”概念，因为实际上输入是Object数组还是Object[]数组，或者其他什么都不重要。真正重要的是如何定义(大O符号)。也就是说:如果你想把算法的大O和输入的大小联系起来，你必须知道“你的输入的大小”是什么。您必须在n O(n).中定义例如：

1. 您的输入是MyObject[] of size = n，其中MyObject有一个接受k工作的equals方法，其中k是一个常量。deepEquals()的运行时是什么？好的，你在做k工作，n时间，所以你得到了O(n*k)，抛出常数得到了O(n)。很好！
2. 接下来，您的输入是MyObject[][]，其中顶级数组的大小为n，嵌套的数组为大小为j的常量。运行时是什么？n子数组，每个子数组的长度为j，其中每个MyObject负责k工作。O(n*j*k)，抛出常量以再次获得O(n)。注意到，我们的输入变大了一倍，但是大-O不会改变，因为我们假设j是常数，也就是说，我们要问的问题是“运行时如何随顶层数组长度的变化而变化”。
3. ，如果相反，我们问“运行时随顶级数组长度的变化和嵌套数组长度的变化如何变化？”让我们的输入是大小n，嵌套数组大小为m，这不是常量。现在我们得到O(n*m*k)，抛出常数k，得到O(n*m)。如果我们要求输入矩阵(嵌套数组)是正方形的，即O(n^2).

，那么我们的运行时现在是n = m。

什么？

在#2中，n是顶层数组的长度。我们选择忽略这样一个事实，即子数组的长度可能会变化。

在#3中，我们将这一事实内部化，并将子数组的长度表示为m，以获得n*m或n^2时的n = m。

我们可以更进一步

如果equals方法的MyObject方法不是k常量时间，而是O(p)，其中p是包含在MyObject中的集合的大小，那么上面#3的运行时变成O(n*m*p)，其中n*m是MyObject的数量，p是MyObject的集合的大小，而E 169您可以永远这样做E 270。

其结果是，大O表示法是一个绑定的，当您假设某些事情时，它是有效的。这些假设的一个主要部分(我们并不经常想到)是，每个变量(一个变量是一个真正可以改变的东西)，而不是O()括号内的变量，并不重要，因为它被括号内的是的东西所掩盖。这意味着，根据您的假设，取决于n是否比m重要得多，您可以说#3在O(n)中，#3在O(n*m)中，并且是正确的。