提问者:小点点

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


我们可以使用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)快


共1个答案

匿名用户

有没有更好的方法来检验两个向量是否相等

是的,有:a==b工作得很好,而且比您的代码简单得多。

a==b比O(n)快吗

不,这在一般情况下是不可能的。 我们只有对数据有所了解,比如在接近开始或结束时总是发现差异,才能做得比O(n)更好。