提高运行比较向量元素的时间复杂度的效率？

Question

我有两个向量：

std::vector<int> V1 {1,2,3,4,5,6,7};
std::vector<int> V2 {1,2,3};

执行以下操作将导致二次运行时间复杂度：

for(auto IT = V1.begin(); IT != V1.end(), IT++)
{
  for(auto IT2 = V2.begin(); IT2 != V2.end(); IT2++)
  {
    if(*IT == *IT2){std::cout<<"Found a match!"<<std::endl;}
    else{std::cout<<"No match!"<<std::endl;}

  }
}

有没有明确的方法可以将其降低到线性时间？

使用 STL 算法可以实现吗？

例如：

for(auto IT = V1.begin(); IT != V1.end(); IT++)
{
  std::find(V2.begin(), V2.end(), *IT);
}

Answer 1

您将需要在线性时间保留一个数组（您的源数组，因为您显然是从第 0 个元素搜索到第 N 个元素）。

但是，您可以通过确保首先对搜索内容space进行排序来降低其他搜索词。这将允许使用复杂度为 log(n) 的二进制搜索算法。

祝你好运！

这方面的一个例子：

std::vector<int> V1 {1,4,5,6,3};
std::vector<int> V2 {100, 104,101,3};
bool condition {false};
std::sort(V2.begin(), V2.end());

for(auto IT = V1.begin(); IT != V1.end(); IT++)
{
  auto result {std::binary_search(V2.begin(), V2.end(), *IT)};
  if(result > 0){ condition = true};
}

提高运行比较向量元素的时间复杂度的效率？

Increasing efficiency of run-time complexity of comparing vector elements?

c++

big-o

提高 运行 比较向量元素的时间复杂度的效率？

Increasing efficiency of run-time complexity of comparing vector elements?

c++

big-o

提高运行比较向量元素的时间复杂度的效率？