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

Question

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

Answer 1

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