arrays - 在排序数组中插入的摊销时间是 O(n)，删除是 O(1)？

Question

我正在学习如何分析算法，我发现了“摊销时间”的符号。我发现了一些预定义的估计，例如：

- 在排序数组中的平均插入时间为：O(n)

从排序数组中删除的摊销时间为：O(1)

谁能给我详细解释一下，拜托！

Answer 1

这个想法是为数组中的每个条目关联一个名为 的布尔值deleted。删除项目包括设置deleted为 true。当删除的项目太多时，将它们压缩。如果您将压缩阈值设置为总大小的一小部分，则可以从达到压缩点所需的所有删除中支付压缩费用。

这是一个草图。它不完整，但演示了插入和删除算法。

class sorted_array
{
public:
    typedef std::vector<std::pair<int, bool>>::iterator iterator;

    iterator insert(int value)
    {
        auto item = std::make_pair(value, false);
        return vec.insert(std::lower_bound(vec.begin(), vec.end(), item), item);
    }

    void erase(iterator pos)
    {
        pos->second = true; // deleted = true
        deleted_count++;
        if (deleted_count * 2 > vec.size())
        {
           vec.erase(std::remove_if(vec.begin(), vec.end(),
                                    std::get<1, int, bool>), vec.end());
           deleted_count = 0;
        }
    }

private:
    size_t deleted_count = 0;
    std::vector<std::pair<int, bool>> vec;
}

像往常一样插入是 O(n) 。当我们插入元素时，我们也将其标记为未删除。

要删除一个元素，我们只需将其标记为已删除并存入两个信用。

当向量中超过一半的元素被删除时，这意味着我们至少拥有与向量中元素一样多的学分。这意味着我们有能力运行 O(n) 压缩。

要查找元素，您需要运行传统的二进制搜索，然后跳过已删除的元素。由于最多删除了一半的元素，因此二进制搜索最多对 2n 个元素进行操作，这意味着它以 O(log 2n) = O(log n) 的步骤运行。在二分查找完成后，跳过已删除的项目会产生一些额外的成本，但数据结构中的一些更聪明的做法可以将其减少到一个常数。（留作练习。）

同样，迭代集合最多需要 2n 步（因为最多删除一半的元素），仍然是 O(n)。