Вопрос

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

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

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

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

Это было полезно?

Решение

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

Позвольте мне переписать его, явно добавляя мультипликативные константы: $ \ 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)) $ , по желанию.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top