CODEWITHSUNDEEP
c++big-o
Babra Cunningham
Babra Cunningham

Reputation: 2967

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

I have two vectors:

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

Executing the following would result in quadratic run-time complexity:

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;}

  }
}

Are there any clear ways to bring this down to linear time?

Would using an STL algorithm enable this?

For instance:

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

Upvotes: 3

Views: 178

Answers (1)

Monza
Monza

Reputation: 755

You are going to need to keep one array at linear time (your source array as you're obviously searching from it's 0th to it's Nth element).

However, you can bring the other search term down by ensuring that the contents of the search space are sorted first. This will allow the use of binary search algorithms which are log(n) complexity.

Good luck!

An example of this:

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};
}

Upvotes: 3

Related Questions