Как оценить временную сложность операции удаления элемента из массива?

Временная сложность удаления элемента из массива зависит от типа массива и способа удаления:

• В стандартном массиве (например, Array в Swift) удаление элемента по индексу требует сдвига всех последующих элементов влево, чтобы заполнить «дырку». Это приводит к O(n), где n — количество элементов после удаляемого.

• Если удаляется последний элемент, операция обычно выполняется за O(1), так как сдвиг не требуется.

• В случае с динамическими массивами (например, ArrayList в Java или NSMutableArray в Objective-C) ситуация аналогична — удаление из середины требует сдвига элементов.

Пример:

var array = [1, 2, 3, 4, 5]
array.remove(at: 2) // удаляет элемент с индексом 2 (число 3)
// После удаления элементы 4 и 5 сдвигаются на одну позицию влево

Таким образом, в общем случае удаление элемента из массива — операция с временной сложностью O(n).