Заказать вычитания обозначения в куче Фибоначчи

Question

Может заказать обозначение самостоятельно подразумевать:

$ o (d (n)) + o (t (h)) - t (h)= o (d (n)) $

Мое предположение, что вы не можете с момента постоянного в O (t (h)) все равно будет существовать после вычитания, если константу is> 0.

Ну, это на самом деле дело, но есть основные факторы.Это уравнение появляется в анализе кучи фибоначчи в CLR (518).Обоснование этого шага происходит от основной потенциальной функции.По мнению авторов: «Мы можем масштабировать единицы потенциала для доминирования постоянной скрытой в $ O (T (H)) $ ".Я хочу знать, как это происходит, но на самом деле не знают, как задать этот сложный вопрос.

Answer 1

Как вы указываете, ваше первое уравнение не обязательно правильно.

Позвольте мне переписать его, явно добавляя мультипликативные константы: $ \ alpha d (n) + \ beta t (h) - \ gamma t (h)= o (d (n)) $ , где $ \ Gamma= 1 $ . Здесь проблема в том, что $ \ beta $ может быть больше, чем $ \ gamma= 1 $ . .

Что говорят авторы, это то, что вместо того, чтобы думать, что одна единица В стоимости вашей потенциальной функции $ \ phi (h) $ Вносит одну единицу потенциала, вы можете представить, что он фактически представляет $ \ gamma $ единицы потенциала. Это сумма для восстановления анализа с новой потенциальной функцией $ \ phi '(h) $ определяется как $ \ phi' ( H)=gamma \ cdot \ phi (h) $ . Если вы сделаете это, то вы сможете управлять значением $ \ Gamma $ в вышеуказанном уравнении, в то время как $ \ Бета $ остается прежним.

Выбор значения $ \ gamma \ ge \ beta $ гарантирует, что $ \ alpha d (n) + \ beta t (h) - \ gamma t (h)=alpha d (n) - \ underbriace {(\ gamma - \ beta)} _ {\ ge 0} t (h) \ le \ alpha d (n)= o (d (n)) $ , по желанию.