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

Question

这属于来自 Whosebug 的 "a software algorithm"。com/help/on-topic，在本例中，是一种从未排序的数组列表中删除项目的软件算法

这是我 class 在我们讨论不同数据结构的 big oh 运行time 时得到的

我的问题是关于删除未排序的非动态数组的值。根据我们的实现方式，这不应该是 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) 中运行。我从另一个问题中学到的是 Big Oh "conciders everything that has to be done to run the code"，在这种情况下，它包括受 O(n) 约束的 getIndex 函数。因为 remove 方法由 O(n) 和 O(1) 组成，所以它会在 O(n) 时间内运行。每个人都同意我的评估还是我错过了什么？

Answer 1

是的，你是对的。您的 getIndex 函数运行s 平均 O(n)（O(1/2 * n)，但我们通常对常量不感兴趣）。 remove 函数中的其他代码运行s 在常数时间内，因此总运行时间为 O(n + c)，其中 c 是常数，意味着总 [=14] =] 时间是 O(n).

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

Wouldn't remove for a non dynamic unsorted array list be O(n)?

java

arrays

algorithm

arraylist

time-complexity