1

我试图找出 java.util.Arrays deepEquals() 方法的时间复杂度。

我可以从源代码中理解 equals() 方法在 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;
}

提前致谢。

4

2 回答 2

3

该方法对元素的总量线性运行。如果我们用 来表示，那就是。nO(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.lengthis just 1，但元素的实际数量相当庞大。你看，这无关紧要。

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

于 2019-10-30T19:27:02.030 回答
2

我将稍微推翻“对象总数线性”的想法，因为输入是数组Object还是数组Object[]或其他任何东西实际上并不重要。真正重要的是你如何定义你的大 O 符号。即：如果您想将算法的大 O 与输入的大小联系起来，您必须知道“输入的大小”是什么。您必须n在O(n). 例如：

  1. 您的输入是MyObject[]哪里size = n有MyObject一个equals需要k工作的方法，哪里k是一个常数。的运行时间是deepEquals()多少？好吧，你在做k工作，n时间，所以你得到O(n*k)，扔掉常数得到O(n)。伟大的！

  2. 接下来，您的输入是MyObject[][]，其中顶级数组是 size n，嵌套数组是 size j，一个常数。什么是运行时？n子数组，每个长度j，每个都MyObject需要k工作。O(n*j*k), 抛出常量重新获得O(n)。请注意，我们的输入已经变大了j几倍，但 big-O 并没有改变，因为我们假设j是恒定的，即我们要问的问题是“运行时如何随着顶级数组长度的变化而变化”。

  3. 相反，如果我们问“运行时如何随着顶级数组长度的变化以及嵌套数组长度的变化而变化？让我们的输入为 size n，嵌套数组 size不是恒定m的。现在我们得到，扔掉常数得到。如果我们要求我们的输入矩阵（嵌套数组）是正方形的，即，我们的运行时间是。O(n*m*k)kO(n*m)n = mO(n^2)

什么？？？？？

在#2 中，n是顶级数组的长度。我们选择忽略子数组的长度可以变化的事实。

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

我们可以更进一步：

如果equalsa 的方法MyObject不需要k固定时间，而是O(p)wherep是包含在其中的集合的大小MyObject，那么上面#3 的运行时间变成O(n*m*p)wheren*m是 a 的集合的数量MyObject和p大小MyObject，而你可以一直这样做下去。

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

于 2019-10-30T20:46:29.090 回答