Почему удаление элемента в конце динамического массива O (n) сложность по времени?

Question

Я сейчас читаю свой учебник, и я совершенно сбит с толку, почему динамическому массиву потребовалось бы O (n) время, чтобы удалить элемент в конце.Я понимаю, что удаление элемента из любого другого индекса - это O (n), потому что вы должны скопировать все данные и переместить их, чтобы заполнить пробел, но если это в конце, мы просто не уменьшаем счет и устанавливаемИндекс, как 0 или ноль?Я включил картинку из моей книги.Это странно, потому что он говорит, что индексирование - это O (1), поэтому мы должны знать, где находится элемент, чтобы нам не приходилось проходить по массиву, как связанному списку.

Answer 1

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

Например, если интервал равен 4, когда вы добавляете 1-й, 2-й, 3-й, 4-й элемент, все будет хорошо, но когда вы добавляете 5-й элементДинамический массив вырастет в массив из 8 элементов и скопирует все элементы в новый массив.

То же самое при уменьшении.Если вы удалите один элемент из массива из 5 элементов с интервалом 4, динамический массив создаст новый массив из 4 элементов и скопирует элементы.

Вот хорошее представление видео учебник ,

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

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

Answer 2

Во-первых, давайте посмотрим, что означают книги с «Динамическим массивом»:

Динамический массив (также называемый растущий массив , изменяемый размер массива , динамическая таблица или список массивов ) - это структура данных списка произвольного доступа с переменным размером, позволяющая добавлять или удалять элементы.[...]
Примечание: Мы увидим реализацию динамического массива в главах Stacks, Queues и Hashing.

Из этогомы узнаем, что списки массивов являются примерами «Динамического массива», как его определяет автор книги.

Но, если посмотреть дальше, в книге упоминается, что:

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

(выделено мной)

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

Заключение:

Хотя это не так для реализаций Java ArrayList, когда автор этой книги говорит о «динамических массивах», которые «уменьшают размер массива» при удалении при необходимости, , а затем сложность наихудшего случаяудаление в конце массива действительно O(n).

Answer 3

Эта запись выглядит так:

1. неверно или
2. верно, но вводит в заблуждение.

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

Я бы сказал, что вы, скорее всего, смотрите на опечатку в материалах.Глядя на их запись для добавления в конец, которая различает неполные и полные случаи, я думаю, что это скорее всего ошибка копирования / вставки.Следуя примеру таблицы, это должно сказать что-то вроде «O (1), если массив не« слишком пустой », O (n) в противном случае».Но опять же, имейте в виду, что амортизированная эффективность каждой операции равна O (1), а это означает, что эти страшные O (n) термины на самом деле вряд ли могут вас сжечь на практике, если вы не находитесь в специализированномсреда, в которой каждая операция должна работать очень быстро.

Answer 4

Вставка и удаление - это операции, которые мы обычно не выполняем над массивами, поскольку они имеют фиксированную длину по своей природе.Вы не можете увеличивать или уменьшать длину чего-либо, что является фиксированным по своей природе.

Когда люди говорят о «динамических массивах» в Java, они имеют в виду использование class ArrayList, которое поддерживается массивом, и этообеспечивает иллюзию способности вставлять и удалять элементы.

Но для того, чтобы какое-то программное обеспечение создавало иллюзию выполнения вставок и удалений в массиве, каждый раз (или почти каждый раз, есть оптимизациивозможно) он должен выделить новый массив новой желаемой длины и скопировать в него старый массив, пропустив удаленный элемент или добавив вставленный элемент, в зависимости от обстоятельств.Эта копия массива является источником O (N).

И из-за оптимизаций, выполненных ArrayList, таблица, которую вы разместили, не является точной: она должна скорее сказать 'O (1), еслимассив не сильно сократился, O (N), если массив уменьшился настолько, что перераспределение считается необходимым ».Но я думаю, это было бы слишком долго, чтобы поместиться в ячейку таблицы.

Answer 5

Для удаления элемента из динамического массива (ArrayList в java) требуется Поиск для элемента и затем Удаление .

Если элемент находится в конце списка, то сам поиск приведет к n времени вычисления.Я надеюсь, что это имеет смысл для вас.

Вы можете просмотреть источник на http://www.docjar.com/html/api/java/util/ArrayList.java.html

Answer 6

В java для динамического массива (ArrayList) временная сложность удаления последнего элемента равна o (1) в java он не копирует массив в java, они проверят, закончится ли индекс массива.

  int numMoved = size - index - 1;
        if (numMoved > 0)
         //copy array element 

Answer 7

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