Pedido Subtracciones en Fibonacci Montones

Question

Puede ordenar la notación por su propia implicación:

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

Mi conjetura es que ya no puede existir la constante en la O (T (H)) después de la resta si la constante es> 0.

Bueno, este es en realidad el caso, pero hay factores subyacentes.Esta ecuación aparece en el análisis del montón de Fibonacci en CLRS (518).La justificación para este paso proviene de la función potencial subyacente.Según los autores, "podemos ampliar las unidades de potencial para dominar la constante oculta en $ o (t (h)) $ ".Quiero saber cómo sucede esto, pero realmente no sabe cómo hacer esta pregunta complicada.

Answer 1

A medida que señala que su primera ecuación no es necesariamente correcta.

Permítanme reescribirlo agregando explícitamente las constantes multiplicativas: $ \ alfa d (n) + \ beta t (h) - \ gamma t (h)= O (D (n)) $ , donde $ \ gamma= 1 $ . Aquí el problema es que $ \ beta $ puede ser más grande que $ \ gamma= 1 $ .

lo que dicen los autores es que en lugar de pensar que una unidad En el valor de su función potencial $ \ phi (h) $ contribuye a una unidad de potencial, puede imaginar que en realidad está representando $ \ gamma $ unidades de potencial. Esto equivale a rehacer el análisis con una nueva función potencial $ \ phi '(h) $ definido como $ \ phi' ( H)=Gamma \ CDOT \ PHI (H) $ . Si lo hace, entonces puede controlar el valor de $ \ gamma $ en la ecuación anterior, mientras que $ \ beta $ permanece igual.

Elegir un valor de $ \ gamma \ ge \ beta $ garantiza que $ \ alfa d (n) + \ beta t (h) - \ gamma t (h)=alfa d (n) - \ sedrace {(\ gamma - \ beta)} _ {\ ge 0} t (h) \ le \ alfa d (n)= o (d (n)) $ , según lo deseado.