Алгоритм - временная сложность удаления в несортированном массиве

Question

Предположим, что существует несортированный массив A, и он содержит элемент x (x - указатель элемента), и каждый элемент имеет спутниковую переменную k.Таким образом, мы можем получить следующую временную сложность (для наихудших случаев):

Если мы хотим Поиск для определенного K, то это стоит O (n).

если мы хотим вставить элемент, то это стоит O (1), потому что A просто добавляет элемент в конец.

Что если мы знаем x, то Удалить его из массива A?

Нам нужно Сначала найти для xk и получить индексx, тогда Удалить x через его индекс в A, верно?

Так что для Удалить , это тоже стоит O (n), верно?

спасибо

Answer 1

Поиск элемента с заданным значением является линейным.

Поскольку массив все равно не отсортирован, вы можете выполнить удаление в постоянное время.Сначала поменяйте местами элемент, который вы хотите удалить, до конца массива, затем уменьшите размер массива на один элемент.

Answer 2

Да, все верно. Кроме того, если это массив, удаление одного займет O(n) время, потому что после удаления элемента вам нужно будет сместить все элементы справа от этого элемента на одно место влево. Таким образом, даже если вы знаете x (например, вы удалите только первый элемент), это займет O(n) времени.

Answer 3

Да.Требуется O(n) время, чтобы найти элемент, который вы хотите удалить.Затем, чтобы удалить его, вы должны сдвинуть все элементы справа от него на один пробел влево.Это также O(n), поэтому общая сложность линейна.

Кроме того, если вы говорите о статически размещенных массивах, вставка также занимает O(n).Вы должны изменить размер массива, чтобы вместить дополнительный элемент.Однако есть способы амортизации этого времени выполнения до O(1).