java - 非动态未排序数组列表的删除不会是 O(n) 吗？

Question

这属于 stackoverflow.com/help/on-topic 中的“软件算法”，在本例中，是一种从未排序的数组列表中删除项目的软件算法

当我们讨论不同数据结构的 big oh runtime 时，这是我类的

我的问题是关于删除未排序的非动态数组的值。根据我们的实现方式，这不应该是 O(n) 吗(见下文)

 public void remove(E value) {
    int index = getIndex(value);
    elementData[index] = elementData[size - 1];
    elementData[size - 1] = null;
    size--;
}
public int getIndex(E value) {
   for (int i = 0; i < size; i++) {
       if (elementData[i].equals(value)) {
           return i;
       }
   }
   return -1;
}

虽然我同意这个代码段这一事实

elementData[index] = elementData[size - 1];
    elementData[size - 1] = null;
    size--;

将在 O(1) 中运行。我从另一个问题中学到了什么 Why is clear an O(n) operation for linked list?是那个 Big Oh “考虑了运行代码必须做的一切”，在这种情况下，它包括由 O(n) 绑定(bind)的 getIndex 函数。 因为 remove 方法由 O(n) 和 O(1) 组成，所以它将在 O(n) 时间内运行。 每个人都同意我的评估还是我错过了什么？

Answer 1

是的，你是对的。您的 getIndex 函数平均运行时间为 O(n)(O(1/2 * n)，但我们通常对常量不感兴趣)。 remove 函数中的其他代码以恒定时间运行，因此总运行时间为 O(n + c)，其中 c 是常数，意味着总运行时间为 O(n)。