Как провести амортизированный анализ биномиальной кучи?

Question

[Василий Дёмин]

В книге Криса Окасаки "Чисто функциональные структуры данных" дано задание: доказать, что амортизированная стоимость операции merge для биномиальной кучи равна O(log n).

Дан код на Standard ML

datatype Tree = Node of int * Elem.T * Tree list
type Heap = Tree list

fun rank (Node (r,x,c)) = r

fun link (t1 as Node (r1, x1, c1), t2 as Node (r2, x2, c2)) =
  if Elem.leq (x1, x2) then Node (r+1, x1, t2::c1)
  else Node (r+1, x2, t1::c2)

fun insTree (t, []) = [t]
  | insTree (t, ts as t'::ts') =
     if rank t < rank t' then t::ts else insTree (link (t, t'), ts')

fun merge (ts1, []) = ts1
  | merge ([], ts2) = ts2
  | merge (ts1 as t1::ts1', ts2 as t2::ts2') =
     if rank t1 < rank t2 then t1::merge (ts1', ts2)
     else if rank t2 < rank t1 then t2::merge (ts1, ts2')
     else insTree (link (t1, t2), merge (ts1', ts2'))

Answer 1

[dmshar]

Книгу не читал, но верю, что там есть такое задание. Наверное, предполагается, что матерал, который изложен ранее позволяет ученику самостоятельно доказать указанный тезис. Что от нас-то вы хотите? Что-бы мы прочитали эту книгу, попутно изучив вообще-то мало кому нужный Standard ML и доказали что-то за вас?
P.S. Подсказка. Сложность алгоритма вставки элемента в двоичную кучу не превышает О(logN). Элементарное объяснение см. например, здесь - https://habr.com/ru/post/112222/

Comments

[Василий Дёмин]

Вы правы насчёт наличия материала. В книге даётся пример с анализом операции insTree методом физика:

a = t + h(j) - h(0),
где a - амортизированная стоимость
t - количество шагов
h(j) - потенциал конечного состояния
h(0) - потенциал начального состояния

за t берётся количество операций link плюс одна текущая(k+1), за h(0) - количество деревьев до вставки(n), h(j) - количество деревьев после вставки(n - k + 1). Тогда a = k+1+n-k+1-n = 2, то есть O(1).

Есть 3 варианта действий merge, два из которых O(1), следовательно нужно анализировать третий случай с insTree. Не понятно, что брать за t,h(j),h(0). Если взять t = k+1, где k - количество операций link, за h(0) - количество деревьев до слияния в обеих кучах, то не понятно, как выразить h(j). В этоим и состоит вопрос.