如何在小于 O(n) 的时间复杂度内检查两个 std::vectors 是否相等

Question

我们可以像这样使用 for 循环比较两个向量

    bool checkEquality(vector<int> &A, vector<int> &B){
         if(A.size() != B.size())
             return false;
         int i=0,j=0;
         while(i<A.size() && j<B.size()){
             if(A[i++] != B[j++])
                 return false;
         return true;
    }

但是如果向量中的元素是 n，这需要 O(n) 时间 我想知道有没有更好的方法来检查两个向量是否相等

加上这段代码的时间复杂度是多少

if(A==B) 
   return true;
else 
   return false;

上面的代码是否比 O(n)

运行得更快

Answer 1

is there any better way to check whether two vectors are equal

是的：A == B 工作正常，并且比您的代码简单得多。

is A == B faster than O(n)

不，一般情况下那是不可能的。如果我们对数据有所了解，例如总是在开头或结尾附近发现差异，我们只能比 O(n) 做得更好。