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

这属于stackoverflow.com/help/on-topic中的“软件算法”，在本例中是一种从未排序数组列表中删除项的软件算法
这是我们讨论不同数据结构的big-oh运行时时的课程
我的问题是关于删除未排序的非动态数组的值这不应该是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）绑定的getIndex函数。
因为remove方法由o（n）和o（1）组成，所以它将在o（n）时间内运行。
大家同意我的评价吗？还是我漏掉了什么？

最佳答案

是的，你是对的。你的getIndex函数平均运行在O（n）（O（1/2*n），但我们通常对常数不感兴趣remove函数中的另一个代码以恒定时间运行，因此总运行时间是O（n+c），其中c是一个常量，这意味着总运行时间是O（n）。

关于java - 对于非动态未排序数组列表，不会删除O(n)吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28377170/