CODEWITHSUNDEEP
c++loopstime-complexitybig-o
Babra Cunningham
Babra Cunningham

Reputation: 2967

Nested loops causing reduced complexity efficency?

I've written a simple function that removes elements from a vector (V2), based upon the values of another vector (V1):

std::vector<int> V1={6,2,3,4};
std::vector<int> V2={9,4,8,6,7};

for(int i=0; i<V1.size(); i++)
{
   if(!V2.empty())
   {
     V2.erase(std::remove(V2.begin(),V2.end(),V1[i]),V2.end());
   }
}

My challenge is that the above needs to be O(n) complexity. Currently this is O(n*m), n being V1, m being V2.

N.B. Arrays are not and cannot be sorted as the elements original index values are required.

Questions:

  1. Am I right in saying 'V2.erase' is stopping this function from being O(n)? (Because its a nested iteration within the for loop).

  2. Is there a way around this, by performing the erase operation outside the loop?

Upvotes: 0

Views: 87

Answers (2)

Adrian Colomitchi
Adrian Colomitchi

Reputation: 3992

std::vector<int> V1={6,2,3,4};
std::vector<int> V2={9,4,8,6,7};

// must be a truly pathological case to have lookups of O(N)
std::unordered_set v1_hashed(v1.begin(), v1.end());

for(
  size_t v2ix=v2.size()-1; 
  v2ix<v2.size(); // otherwise underflow past zero
  v2ix--
) {
  // generally, an O(1) is assumed here
  if(v1_hashed.find(v2[v2ix]) != v1_hashed.end()) {
    // removal of element will cost quite significant due to 
    // moving elements down. This is why doing the cycle in reverse
    // (less elements to move down).
    v2.erase(v2ix);
  }
}

// O(N) searches + O(M) hashing of v1

Upvotes: 1

Nik Bougalis
Nik Bougalis

Reputation: 10613

Why not use std::set_difference:

std::vector<int> test(
    std::vector<int> v1,
    std::vector<int>& v2)
{
    // The algorithm we use requires the ranges to be sorted:
    std::sort (v1.begin(), v1.end());
    std::sort (v2.begin(), v2.end());

    // our output vector: reserve space to avoid copying:
    std::vector<int> v3;
    v3.reserve (v2.size());

    // Use std::set_difference to copy the elements from
    // v2 that are not in v1 into v3:
    std::set_difference (
        v2.begin(), v2.end(),
        v1.begin(), v1.end(),
        std::back_inserter(v3));

    return v3;
}

If v1.size() == n and v2.size() == m the runtime of this works out to roughly:

O(NlogN) + O(MlogM) + 2 O(M+N-1)

OK, so then how about this:

void test2(
    std::vector<int> v1,
    std::vector<int> v2)
{
    // We can still sort this without affecting the indices
    // in v2:
    std::sort (v1.begin(), v1.end());

    // Replace all the elements in v1 which appear in v2
    // with -1:
    std::replace_if (v2.begin(), v2.end(),
        [&v1] (int v)
        {
            return std::binary_search(v1.begin(), v1.end(), v);
        }, -1);
}

Not linear; estimating the complexity is left as an exercise for the OP.

A third alternative is this:

void test3(
    std::vector<int> v1,
    std::vector<int>& v2)
{
    // We can still sort this without affecting the indices
    // in v2:
    std::sort (v1.begin(), v1.end());

    auto ret = std::stable_partition (
        v2.begin(), v2.end(),
        [&v1] (int v)
        {
            return !std::binary_search(v1.begin(), v1.end(), v);
        });

    v2.erase (ret, v2.end());
}

Again, not linear, but options...

Upvotes: 2

Related Questions