3622
правки
Изменения
Нет описания правки
// O - сверху, Omega - снизу, Theta - и сверху и снизу - памятка для тебя, чтобы не запутаться
Применим амортизационный анализ, используя метод предоплаты. Копим деньги на дешевых операциях. Слиянием массивов осуществляется за O(w), как и разделение. Поэтому, если мы накопим Omega(w) дополнительных денег на дешёвых операциях, то сумеем расплатиться за все остальные, просто кладя константное число дополнительных монет во время каждой операции. Худший случай для разделения, если мы дальше будем только добавлять элементы - было w/2 - 1 и 2 * w, слили, стало больше 2 * w, разделели, таким образом получили два дерева с 5/4 * w элементами. Худший случай для слияния, когда у нас w элементов (просиходит после разделения 2 * w + 1 дерева). Заметил, что в каждом случае дерево находится на расстоянии Theta(w) от границ. Следовательно, если мы будем класть определённое константное число монет, то скопим их достаточно, чтобы расплатиться за преобразование верхнего дерева. Получаем амортизированную оценку O(log(w)) и истинную - O(w).
Здесь не имеет смысла использовать сливаемые деревья поиска, так как после слияния/разделения все равно нужно модифицировать верхний бор.
Получилась та же оценка на операции, что и у Ван Эмде Боаса, но структура данных занимает O(n) памяти.