java - 有序数组删除操作——大O分析

Question

我找到了这个 link关于有序数组操作的大 O 分析。删除操作在链接中被归类为线性时间。

实际代码对每个输入执行 2 个操作。在一般情况下，对二分查找执行一个操作以找到要删除的值，然后执行第二个操作在删除后向上移动其余值。二进制搜索故事的对数时间和向上移动值是线性时间，所以我认为运行时分析的平均情况至少是 O(n logn)，其中对数线性时间不是线性时间。

我错过了什么？

Answer 1

搜索操作和删除操作是单独的操作，每个操作执行一次。

因此，您应该将它们的运行时间相加，而不是相乘。

因此你得到:

O(logN) + O(N) = O(N)