嵌套循环导致复杂性效率降低？

Question

我编写了一个简单的函数，它根据另一个向量 (V1) 的值从一个向量 (V2) 中删除元素：

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

我的挑战是以上需要复杂度为 O(n)。目前这是 O(n*m)，n 是 V1，m 是 V2。

N.B。数组不是也不能排序，因为需要元素原始索引值。

问题：

我说 'V2.erase' 阻止这个函数成为 O(n) 是对的吗？（因为它是 for 循环中的嵌套迭代）。
有没有办法通过在循环外执行擦除操作来解决这个问题？

Answer 1

为什么不用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;
}

如果 v1.size() == n 和 v2.size() == m 运行时间大致为：

好的，那么这个怎么样：

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

非线性；估计复杂性留作 OP 的练习。

第三种选择是：

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

同样，不是线性的，而是选项...

Answer 2

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

嵌套循环导致复杂性效率降低？

Nested loops causing reduced complexity efficency?

c++

big-o

loops

time-complexity