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

Question

我正在学习如何分析算法，我发现了 "Amortized time" 的符号。我发现了一些预定义的估计值，例如：

-插入排序数组的摊销时间为：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 个元素进行操作，这意味着它运行s 在 O(log 2n) = O(log n) 步。在二进制搜索完成后，跳过已删除的项目会产生一些额外的成本，但数据结构中的一些更聪明的地方可以将其减少到一个常量。（留作练习。）

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

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

Amortized time of insertion in sorted array is O(n) and deletion is O(1)?

arrays

sorting

algorithm

amortized-analysis