Как сделать так, чтобы при добавлении ссылки в двусвязный список выполнялись N / 2, а не O (N) (int index, element a) в качестве параметров

Question

Кажется, что единственно возможным поведением Big-Oh для добавления чего-либо в связанный список будет O (N), так как вы должны пройти весь список.Однако из того, что я слышал, общее количество операций должно быть не более N / 2.Может кто-нибудь объяснить, как это возможно, как я вижу, если вы пересекаете связанный конец списка, общее поведение все равно будет O (N).Чего мне не хватает?

Answer 1

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

Например, скажем, у вас есть список [B, C, D, E, F, G, H], еслиу вас есть указатель на элемент E, и вы знаете, что в вашем списке 7 элементов.Если вы позвоните insert(0, A), чтобы вставить элемент A в положение 0, то вы будете знать, что если вы переместитесь на 3 ссылки назад, вы перейдете из положения 3 в положение 0 (помните, что нулевой индекс является первым, поэтому выперейти от E @ 3 -> D @ 2 -> C @ 1 -> B @ 0).Оттуда вы можете вставить элемент A перед вашим «текущим» элементом (B).

Обратите внимание, что люди обычно оставляют постоянные выражения вне анализа big-O;O (n / 2) и O (n) имеют те же характеристики, что и увеличение n.

Answer 2

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

По предположению, N / 2 основано на предположении, что список отсортирован, поэтому в среднем вы пересекаете только половину списка, чтобы найти правильную точку вставки.

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