#algorithm #data-structures #merge #skip-lists
#алгоритм #структуры данных #слияние #списки пропусков
Вопрос:
Как я могу объединить 2 заданных Skip lists
(каждый с n ключами) в один Skip List
по O(n)
временной сложности (наихудший случай)?
Просто ищу алгоритм — никакой конкретной реализации / языка.
Ответ №1:
store the two skip lists in two arrays: A,B
merge the arrays.
repeat until getting into root ('top' is a linked list containing only one element):
for each second entry in the skip list 'top' add a 'tag' (link 'upstairs' of the previous level)
это действительно O (n), потому что сохранение и слияние равны O (n), и в цикле вам нужно повторить:
n n/2 n/4 n/8 ... = sigma(n/2^k) where k in (0,infinity) = 2n
Комментарии:
1. Я не уверен, что правильно использовал термины списка пропусков (в цикле) Однако я уверен, что это решение правильное. дайте мне знать, если вы чего-то не понимаете.