数组比较方法的时间复杂度

我有一个方法比较一个单维数组与二维数组中的每一行以查看它们是否相等。两个数组都有相同数量的列。例如，{1,0}和{{1,0}，{1,1}} - 我会比较{1,0}到{1,0}，然后到{1,1}。如果二维数组中有n行，两个数组中有m列，那么时间复杂度是多少？是O（mn）吗？数组比较方法的时间复杂度

来源

2013-03-20 John Roberts

1D数组中的每个条目都针对2D数组中的每个条目？那将是O（mmn）。 – nneonneo 2013-03-20 01:03:26

为什么两个米？我正在比较单维和多维数组中的相同列索引。 – 2013-03-20 01:10:30

啊。关于“每一个条目”的说法并不清楚。你正在比较行向量（1D数组）对2D矩阵的每一行，然后？在那种情况下，它是O（mn）。 – nneonneo 2013-03-20 01:11:18

-1

如果任何特定指数的元素不同，那么两个向量的比较可以提前退出。因此，除非您的数据分布非常不均匀，否则如果载体不同，则单个载体比较应该是O(1)，如果它们相同，则应该是O(m)。因此，如果有匹配，总体时间复杂度将是O(n + m)，如果没有，则总体时间复杂度将是O(n)。这当然是平均的，最坏的情况会是O（mn）。

来源

2013-03-20 15:43:52 nwellnhof

数组比较方法的时间复杂度

回答

相关问题