Блог

Я начинаю изучать структуры данных и алгоритмы и в настоящее время изучаю временную сложность массива.

Из книги, из которой я учусь, говорится, что для поиска массива требуется N шагов, поскольку в худшем случае вам придется искать элемент данных в каждой ячейке.

Тогда почему удаление из массива также выполняется N шагов?

Насколько я понимаю, компьютер выделяет память для массива и отмечает начало массива через адрес памяти. Для удаления разве вам все равно не придется искать в каждом индексе этого массива элемент данных, который вы хотите удалить, удалить этот элемент данных, а затем переместить оставшиеся элементы данных?

Возможно, я все еще слишком рано вхожу в эту главу, но я довольно смущен тем, что само удаление занимает всего 1 шаг.

Допустим , у вас есть массив размера N , и ваш элемент для удаления находится в нужном положении M M < N , затем вам нужны M шаги, чтобы найти элемент, а затем нужно переместить N-M элементы, таким образом O(M (N-M)) = O(N)

Проблема предполагает, что узел, подлежащий удалению, известен и указатель на этот узел доступен.

Чтобы удалить узел и соединить предыдущий и следующий узлы вместе, вам необходимо знать их указатели. В двусвязном списке оба указателя доступны в узле, который необходимо удалить. Временная сложность в этом случае постоянна, т. Е. O(1).

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

Дан односвязный список со следующим состоянием:

 SinglyLinkedList:
   Node 1 -> Node 2
   Node 2 -> Node 3
   Node 3 -> Node 4
   Node 4 -> None

   Head = Node 1
 

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

Когда мы говорим о сложности вставки и удаления, мы обычно предполагаем, что уже знаем, где это произойдет.

В случаях, когда удаляемый узел известен только по значению, необходимо выполнить поиск по списку, и временная сложность становится O(n) как в односвязных, так и в двусвязных списках.

Я думаю, что это дает представление о теме

Позволяет вам захотеть удалить m из массива размером n. Это зависит от того, отсортирован массив или нет. Возьмите все в худшем случае. Если массив отсортирован, наихудшая временная сложность для поиска m в массиве равна log(n), пусть число m найдено по первому индексу(0), затем вам нужно сдвинуть массив влево с индекса 1 на n-1. Временная сложность для сдвига составляет приблизительно O(n) и O(log(n)) O(n)= O(n), если массив не отсортирован, в худшем случае временная сложность для поиска m в массиве составляет O(n) в. И нужно сместить влево, и это займет O(n) O(n)= O(n)