Структура данных с индексированием и конкатенацией за O(1)

[arseniiv]

Подскажите, где посмотреть, если известно, какое-нибудь представление последовательности элементов с индексированием и конкатенацией желательно за $O(1)$, ну или хотя бы за $O(\log n)$, где $n$ — длина последовательности или сумма длин сцепляемых. Лучше индексирование константное.

[iifat]

А что, такие бывают? Вроде б, либо индексирование $O(1)$ конкатенация $O(n)$, либо индексирование логарифмическое, конкатенация фиксированная.

[Munin]

Вроде бы, если к массиву дополнительно выделять память, округлённую до степени двойки (как и делают, если массив должен часто "расти"), то конкатенация будет $\mathcal{O}(\log n)$ средневзвешенно.

[venco]

Munin в сообщении #1031262 писал(а):

Вроде бы, если к массиву дополнительно выделять память, округлённую до степени двойки (как и делают, если массив должен часто "расти"), то конкатенация будет $\mathcal{O}(\log n)$ средневзвешенно.

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

-- Пт июн 26, 2015 10:12:33 --

iifat в сообщении #1031210 писал(а):

А что, такие бывают? Вроде б, либо индексирование $O(1)$ конкатенация $O(n)$, либо индексирование логарифмическое, конкатенация фиксированная.

Можно довольно легко сделать обе операции $O(\log n)$ - бинарное дерево с хранением количества элементов.

[Munin]

venco в сообщении #1031273 писал(а):

Конкатенация в массиве как минимум $O(n)$ - надо же скопировать добавляемые элементы.

А, ну да, точно.

venco в сообщении #1031273 писал(а):

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

Простите, логарифм.

[iifat]

venco в сообщении #1031273 писал(а):

Можно довольно легко сделать обе операции

А, балансировать при конкатенации?

[venco]

Munin в сообщении #1031278 писал(а):

venco в сообщении #1031273 писал(а):

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

Простите, логарифм.

Всё-таки константа.

-- Пт июн 26, 2015 10:38:13 --

iifat в сообщении #1031280 писал(а):

venco в сообщении #1031273 писал(а):

Можно довольно легко сделать обе операции

А, балансировать при конкатенации?

Балансировка - это $O(\log n)$. Хотя, я не уверен, надо подумать.

[aa_dav]

venco в сообщении #1031288 писал(а):

Всё-таки константа.

Теперь уже Munin имеет ввиду что под "амортизированным O(1)" в среднем кроется логарифм.

А, стоп... действительно.... не всё так просто...

P.S.

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

[Munin]

Покажите, а?

[venco]

Добавление элемента не требующее увеличения массива - $O(1)$, иначе - $O(e^k)$, где $e$ - коэффициент увеличения размера массива, $k$ - номер увеличения.
Суммарное время $k$-го этапа, на котором добавляются $e^k-e^{k-1}$ элементов состоит из увеличения массива и заполнения выделенной памяти - $O(e^k)+(e^k-e^{k-1})O(1)=O(e^k)$. Соответственно суммарное время всех этапов до $k$ тоже $O(e^k)$, при этом суммарное количество добавленных элементов - $e^k$. Амортизированное время - $O(1)$.
Кстати, коэффициент $e$ лучше брать меньше $\frac{\sqrt 5 +1}2$, тогда не образуются дырки в памяти. (спорно)

[kp9r4d]

venco в сообщении #1031273 писал(а):

Можно довольно легко сделать обе операции $O(\log n)$ - бинарное дерево с хранением количества элементов.

Таки не обычное, а link-cut tree (сплей или декартово, например), обычные не обязательно поддерживают слияние за логарифм.

[Munin]

venco
Спасибо, красиво.