Понимание амортизированного времени и почему вставки массива являются O (1)

Я читаю Cracking the Coding Interview, и в главе Big O есть объяснение амортизированного времени. Здесь используется классический пример чего-то вроде ArrayList, нуждающегося в росте. Когда массиву необходимо увеличиться, вставка займет O(N) времени при условии, что в новый массив необходимо скопировать N элементов. Это хорошо.

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


algorithm big-o amortized-analysis
person randombits    schedule 31.08.2017    source источник
comment
Здесь уже есть ответ Постоянное амортизированное время   -  person Dúthomhas    schedule 31.08.2017
comment
Вставляет? Вы уверены, что там не сказано добавление?   -  person user2357112 supports Monica    schedule 31.08.2017
comment
Поскольку емкость массива удваивается, вероятность того, что массиву потребуется увеличиться, уменьшается экспоненциально и приближается к 0.   -  person 4castle    schedule 31.08.2017
comment
@Dúthomhas, мой вопрос более или менее заключается в том, как вставить массив когда-либо O (1). Я думал, что вставка всегда O (N) независимо от обстоятельств.   -  person randombits    schedule 31.08.2017
comment
Соображения времени имеют значение только как ***n***→‹_действительно большое число_›. С точки зрения кода, который на самом деле возится с массивом, да, это O(n) (или хуже). С точки зрения вызова функции, которая возится с массивом в течение всего жизненного цикла вашего приложения, количество времени, которое требуется, приближается к определенному интервалу времени, который вы можете принять за 1.   -  person Dúthomhas    schedule 31.08.2017
comment
Возможный дубликат временной сложности динамического массива размещения элемента   -  person Gene    schedule 31.08.2017
comment
Кстати. удвоение - не единственный способ получить амортизированное время добавления O (1). Подойдет любой постоянный коэффициент, вы можете, например, увеличить его на 10 % всякий раз, когда это необходимо.   -  person Henry    schedule 31.08.2017

Ответы (1)


arrow_upward
8
arrow_downward

Я отвечаю на вопрос, в котором вы, кажется, запутались, а не на вопрос, который вы официально задали.

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

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

Независимо от того, имеет ли значение среднее значение, зависит от вашей задачи. Если вы управляете тяжелой техникой, слишком много времени на отдельную операцию может означать, что вы не вернетесь к вращающемуся лезвию достаточно быстро, что может быть Официально Плохо. Если вы создаете веб-страницу, то все, что имеет значение, — это общее время, затрачиваемое на последовательность операций, и это будет число операций, умноженное на среднее время каждой из них.

Для большинства программистов важно среднее значение.

person btilly    schedule 31.08.2017
comment
Это здорово и действительно помогает. Спасибо. - person randombits; 31.08.2017