Изменения

Перейти к: навигация, поиск

Rope

123 байта добавлено, 18:56, 4 июня 2014
Нет описания правки
merge('''Node''' T1, '''Node''' T2) = '''Node'''(T1, T2, T1.w + T2.w)
===Время работы===
Асимптотика выполнения операции конкатенации двух строк очевидно <tex>O(1)</tex>.
'''else''':
'''return''' node.s[i]
 
===Время работы===
Асимптотика выполнения одного такого запроса очевидно <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
t2.s = node.s.substr(i, s.len)
'''return''' pair(t1, t2)
 
===Время работы===
Нетрудно заметить что асимптотическая сложность выполнения данной операции <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
t1 = merge(t1, t3)
'''return''' merge(t1, t2)
 
===Время работы===
Так как данные операции используют только <tex>split</tex> и <tex>merge</tex> то асимптотика времени их работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
91
правка

Навигация