c++ - std::remove_if 的渐近复杂度

Question

我正在为具有硬编码的最大元素数 N 的数据结构开发一种擦除方法，该方法依赖于std::array避免堆内存。尽管std::array仅包含 N 个元素，但其中的某个数量 M 是“相关”元素，其中 M 小于或等于 N。例如，如果 N 为 10，则数组如下所示：

std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 };

...如果 M 为 7，则只有前 7 个元素是“相关的”，而其他元素被认为是垃圾（结尾{ -1, -1, -9 }是垃圾）。我在int这里使用了一个 SO 示例，但真正的程序存储了实现operator==. 下面是一个删除所有-1并更新 M 的工作示例：

#include <algorithm>
#include <array>
#include <iostream>

constexpr unsigned N = 10;
unsigned           M = 7;
std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 };

int main() {
        for (unsigned i = 0; i < M; ++i)
                std::cout << elements[i] << ' ';
        std::cout << '\n';

        auto newEnd = std::remove_if(
                std::begin(elements), std::begin(elements) + M,
                [](const auto& element) {
                        return -1 == element;
                }
        );

        unsigned numDeleted = M - std::distance(std::begin(elements), newEnd);
        M -= numDeleted;
        std::cout << "Num deleted: " << numDeleted << '\n';

        for (unsigned i = 0; i < M; ++i)
                std::cout << elements[i] << ' ';
        std::cout << '\n';

        return 0;
}

我的问题是什么是渐近复杂度std::remove_if？我想在std::remove_if和之间std::distance是总体 O(2M) 或 O(M) ，其中std::remove_if是更昂贵的操作。但是我不确定是否std::remove_if是 O(N * M)，因为每次删除都会移动元素

编辑：为清楚起见，我知道这应该应用谓词 M 次，但我想知道每次谓词为真时是否应用 N 班次

score 4 · Accepted Answer

通过cppreference：

复杂性：谓词的确切std::distance(first, last)应用。

移除的元素没有移位操作，因为它们在调用后可能具有未指定的值std::remove_if

score 2 · Accepted Answer

编辑

回想起来，这个答案解决了一个比所问问题更复杂的问题——如何在线性时间内实现“推回端”功能。关于提出的具体问题 - 与remove_if- @millenimumbug 的回答有关。

我明白为什么你会认为复杂性是Θ(mn)，因为m删除的每个项目可能需要移动Θ(n)距离。

实际上可以在时间Θ(n)和额外的O(1)空间（只需几个额外的迭代器）中做到这一点。

考虑下图，它显示了算法可能实现的迭代。

红色项目是一组连续的识别项目，此时要删除到最后（您只需要两个点来记录）。绿色项目是现在正在考虑的项目（另一个指针）。

如果要删除绿色项目，则通过包含它，红色组会变得更大。这在下图中显示，红色组在其中展开。在下一次迭代中，绿色项目将是它右侧的项目。

如果不是，则所有红色组都需要移过它。一些想法可以说服您，这可以在红色组中以线性时间完成（即使迭代器被保证只是前向迭代器）。

为什么复杂度是线性的？因为你可以想象这相当于绿色元素相对于左组向左移动。原理类似于摊销分析。

下图显示了第二种情况。在下一次迭代中，绿色元素（正在考虑）将再次位于红色组的右侧。

c++ - std::remove_if 的渐近复杂度

2 回答 2

Related

Reference