动态数组中给定元素值的remove方法的时间复杂度

Question

在学习数据结构时，我尝试使用静态数组在 Java 中实现动态数组，并尝试计算每种方法的时间复杂度。

对于以元素作为参数的remove 方法，我的代码包含一个if 语句来检查是否在数组中找到了给定的元素。只有当元素存在时，它才会执行删除操作。我正在努力寻找这种方法的时间复杂度。是 O(n) 吗？有人可以解释一下吗？

    public boolean remove(int ele) {
        for (int i = 0; i < numberOfElements; i++) {
            if (arr[i] == ele) {
                removeAt(i);
                return true;
            }
        }
        return false;
    }

    public void removeAt(int index) {
        if (index > numberOfElements) {
            throw new IllegalArgumentException();
        } else {
            for (int i = index; i < numberOfElements - 1; i++) {
                arr[i] = arr[i + 1];
            }
            numberOfElements--;
        }
    }

Answer 1

复杂度好像是O(N)，N次遍历数组，N次移位一次。一旦删除元素，'if' 遍历其余元素以进行移位，进行 'i' 次迭代以查找元素并进行 'n - i' 次迭代以进行移位。在'if'的末尾，由于return和操作完成，外部'for'被破坏。

我认为您需要迭代到 'numberOfElements'，而不是直接使用 'array.length'。

Answer 2

从数组中删除一个元素需要 O(n) 的时间，即使我们给出了要删除的元素的索引。排序数组的时间复杂度也保持为 O(n)。在链表中，如果我们知道要删除的节点指向前一个节点的指针，我们就可以在O(1)时间内进行删除。

动态数组中给定元素值的remove方法的时间复杂度

Time complexity of remove method with a given element value in dynamic array

time-complexity

dynamic-arrays

data-structures

array-algorithms