Java 中 Arrays.deepEquals() 的时间复杂度
Time complexity of Arrays.deepEquals() in Java
我正在尝试计算 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;
}
提前致谢。
该方法对元素总数运行线性。如果我们用 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个维度),那么你还必须检查这些维度的所有。所以它真的检查了所有元素。
我要稍微推翻 "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.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;
}
提前致谢。
该方法对元素总数运行线性。如果我们用 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个维度),那么你还必须检查这些维度的所有。所以它真的检查了所有元素。
我要稍微推翻 "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)
内并且是正确的,根据你的假设。