Я изучаю анализ алгоритма, и я столкнулся с проблемой.
Что я сделал
Я написал программу, которая генерирует 30 двоичных деревьев случайного размера, где каждый узел каждого дерева имеет случайное значение. Теперь, чтобы использовать амортизированный анализ, я присвоил (при необходимости) ранг каждому узлу дерева следующим образом
«Если ранг узла равен r, то ранг его левого потомка равен r − 1, а ранг его правого потомка равен r + 1».
Теперь, чтобы определить амортизируемую сложность каждого узла, я преобразовал следующее уравнение в код C ++
«ai = ti + Φ (Si) — Φ (Si − 1)», где Si − 1 — состояние D непосредственно перед началом i-го вызова, а Si — состояние D сразу после его завершения.
Что осталось
Я должен сравнить экспериментальные результаты с оценкой амортизированного анализа.
Я слеп в этой части и не знаю, что делать. Кто-нибудь хорош в этом или просто подтолкнуть меня в правильном направлении. Я не могу найти помощь нигде.
Задача ещё не решена.
Других решений пока нет …