includedlibrary
@includedlibrary

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

В книге Криса Окасаки "Чисто функциональные структуры данных" дано задание: доказать, что амортизированная стоимость операции 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'))
  • Вопрос задан
  • 61 просмотр
Пригласить эксперта
Ответы на вопрос 1
@dmshar
Книгу не читал, но верю, что там есть такое задание. Наверное, предполагается, что матерал, который изложен ранее позволяет ученику самостоятельно доказать указанный тезис. Что от нас-то вы хотите? Что-бы мы прочитали эту книгу, попутно изучив вообще-то мало кому нужный Standard ML и доказали что-то за вас?
P.S. Подсказка. Сложность алгоритма вставки элемента в двоичную кучу не превышает О(logN). Элементарное объяснение см. например, здесь - https://habr.com/ru/post/112222/
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы