Временная сложность метода удаления с заданным значением элемента в массиве Dynami c

Question

Когда я изучаю структуры данных, я пытаюсь реализовать динамический массив c в Java, используя массив stati c, и пытаюсь вычислить временные сложности для каждого метода.

Для метода удаления, который принимает элемент в качестве параметра, мой код содержит инструкцию 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) времени, даже если нам дан индекс удаляемого элемента. Временная сложность остается O (n) и для отсортированных массивов. В связанном списке, если мы знаем указатель на предыдущий узел удаляемого узла, мы можем выполнить удаление за O (1) раз.

Answer 2

Сложность кажется O (N), с N для итерации по массиву и N для выполнения операции сдвига один раз. Один раз, когда элемент удаляется, 'if' выполняет итерацию по остальным элементам, чтобы выполнить сдвиг, выполняя 'i' итерации, чтобы найти элементы, и 'n - i', чтобы сдвинуть его. В конце 'if' внешний 'for' прерывается, потому что возвращаемое значение и операция завершаются sh.

. Я думаю, вам нужно выполнить итерацию до 'numberOfElements', а не работать с 'массивом. длина 'напрямую.