c++ - 如何在小于 O(n) 的时间复杂度内检查两个 std::vectors 是否相等
问题描述
我们可以像这样使用 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;
}
但这需要 O(n) 时间如果向量中的元素是 n 我想知道是否有更好的方法来检查两个向量是否相等
加上这个代码片段的时间复杂度是多少
if(A==B)
return true;
else
return false;
上面的代码是否比 O(n) 运行得更快
解决方案
有没有更好的方法来检查两个向量是否相等
是的:A == B
工作正常,并且比您的代码简单得多。
比
A == B
O(n) 快
不,在一般情况下这是不可能的。如果我们对数据有所了解,我们只能比 O(n) 做得更好,例如总是在开头或结尾处发现差异。
推荐阅读
- javascript - 如何在 message.mentions.has("") 中忽略所有人和这里?
- javascript - 以角度 2 显示嵌套列表
- android - 如何从 Jetpack Compose 中的 URL 加载图像?
- reactjs - 代理的 launchSettings.json 应用程序 url
- python - 如何高效地根据不同的概率生成一个0-1序列?
- java - ssl android studio的标签不匹配错误 - wifi问题
- c++ - Hashtable AddEntry 分离链分段错误
- time - 支持将有状态的事物作为参数传递的函数式语言
- google-sheets - 自动更新 Google 表格
- terraform - 预处理 Terraform Locals