Сложность времени — вставка элемента в середину динамического массива

Я наткнулся на эту статью о временной сложности динамических массивов, которая многое прояснила. Однако у меня есть вопрос, основанный на конкретном случае. Скажем, у меня есть динамический массив, в котором всего 6 элементов, и предположим, что 4-й элемент удален. В этом случае сложность удаления будет O(n-index), которая будет O(6-4) = 2, поскольку последние два элемента нужно будет только переместить вверх. Это верно ? У меня есть статьи, которые дают сложность в худшем случае, говоря, что если удалить самый верхний элемент, то временная сложность будет O(n). Я не смог найти ничего, что говорило бы об удалении/вставке элемента из/в центр.


data-structures dynamic-arrays time-complexity big-o
person James Franco    schedule 03.07.2015    source источник

Ответы (1)


arrow_upward
4
arrow_downward

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

person Oliver Dain    schedule 03.07.2015
comment
Я не уверен, что вы подразумеваете под ‹blockquote› Если у вас есть n элементов в списке и вы удалите что-то из середины, вам придется переместить 0,5 * n элементов ‹/blockquote› Как вы получили 0,5*н? - person James Franco; 04.07.2015
comment
Хорошо, спасибо, что прояснили это. Как бы вы написали временную сложность для 4 элементов, удаленных из 6 элементов, не пренебрегая постоянным членом? Будет ли это O(6 * 4/6) ? Это даст мне 4, что неправильно, я ожидал 2 - person James Franco; 04.07.2015
comment
Говорить о сложности для фиксированного количества элементов не имеет смысла. Big-O - это все о том, как вычисление времени изменяется по мере того, как размер ввода изменяется.. На ваш вопрос (4 удаляется из массива 6), что может означать, что вы всегда удаляете последние 4 элемента, независимо от того, насколько велик массив, и в этом случае он O(1), или это может означать, что вы всегда удаляете последние 2/3 из массив, и в этом случае это O(n), или это может означать, что вы всегда удаляете все, кроме первых двух элементов (O(n)) снова) и т. д. . - person Oliver Dain; 04.07.2015