2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Структура данных с индексированием и конкатенацией за O(1)
Сообщение26.06.2015, 11:34 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение26.06.2015, 15:04 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение26.06.2015, 16:37 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение26.06.2015, 17:05 
Заслуженный участник


04/05/09
4582
Munin в сообщении #1031262 писал(а):
Вроде бы, если к массиву дополнительно выделять память, округлённую до степени двойки (как и делают, если массив должен часто "расти"), то конкатенация будет $\mathcal{O}(\log n)$ средневзвешенно.
Конкатенация в массиве как минимум $O(n)$ - надо же скопировать добавляемые элементы.
А то, что вы имеете в виду - это добавление одного элемента в массив, тут как раз и получается амортизационное $O(1)$.

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

iifat в сообщении #1031210 писал(а):
А что, такие бывают? Вроде б, либо индексирование $O(1)$ конкатенация $O(n)$, либо индексирование логарифмическое, конкатенация фиксированная.
Можно довольно легко сделать обе операции $O(\log n)$ - бинарное дерево с хранением количества элементов.

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение26.06.2015, 17:17 
Заслуженный участник
Аватара пользователя


30/01/06
72407
venco в сообщении #1031273 писал(а):
Конкатенация в массиве как минимум $O(n)$ - надо же скопировать добавляемые элементы.

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

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

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

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение26.06.2015, 17:18 
Заслуженный участник


16/02/13
4105
Владивосток
venco в сообщении #1031273 писал(а):
Можно довольно легко сделать обе операции
А, балансировать при конкатенации?

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение26.06.2015, 17:37 
Заслуженный участник


04/05/09
4582
Munin в сообщении #1031278 писал(а):
venco в сообщении #1031273 писал(а):
А то, что вы имеете в виду - это добавление одного элемента в массив, тут как раз и получается амортизационное $O(1)$.

Простите, логарифм.
Всё-таки константа.

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

iifat в сообщении #1031280 писал(а):
venco в сообщении #1031273 писал(а):
Можно довольно легко сделать обе операции
А, балансировать при конкатенации?
Балансировка - это $O(\log n)$. Хотя, я не уверен, надо подумать.

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение26.06.2015, 17:44 


11/12/14
893
venco в сообщении #1031288 писал(а):
Всё-таки константа.


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

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

P.S.

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

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение26.06.2015, 19:04 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Покажите, а?

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение26.06.2015, 19:30 
Заслуженный участник


04/05/09
4582
Добавление элемента не требующее увеличения массива - $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$, тогда не образуются дырки в памяти. (спорно)

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение27.06.2015, 00:48 
Заслуженный участник
Аватара пользователя


09/02/14

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

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

 Профиль  
                  
 
 Re: Структура данных с индексированием и конкатенацией за O(1)
Сообщение27.06.2015, 02:58 
Заслуженный участник
Аватара пользователя


30/01/06
72407
venco
Спасибо, красиво.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group