使用数组的有界集的添加/删除操作的最坏情况场景时间复杂度？

Question

我已将其标记为 Java，因为我从“Java Collections”中挑选了这句话——我正在做的课程的推荐文本。因此，对于添加/删除操作，我理解二进制搜索首先是确定集合是否包含特定元素并确定必须添加/删除元素的位置，然后在必要时进行移位。我引用了用于添加操作的书：“搜索阶段是O（logn）。插入阶段是O（n），但如果要添加的值已经是成员，则跳过。因此整个操作通常是O（n）”为什么整体时间复杂度不是 O(nx logn)？此外，如果您有任何其他建议的文本可能对您推荐的外行来说更容易，那将不胜感激。

Answer 1

因为二分查找是 O(logn)，而插入阶段是 O(n)，所以时间复杂度在技术上是 O(n + logn)。因为 logn 与 n 相比微不足道，所以您可以删除 logn 给出答案 O(n)。