Subtractions de notation de commande dans le tas de fibonacci

Question

peut commander la notation à son propre impliqué:

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

Je suppose que vous ne pouvez pas car la constante dans le O (t h)) existerait encore après la soustraction si la constante est> 0.

Eh bien, c'est en fait le cas, mais il y a des facteurs sous-jacents.Cette équation apparaît dans l'analyse du tas de Fibonacci dans les CLRS (518).La justification de cette étape provient de la fonction potentielle sous-jacente.Selon les auteurs, "nous pouvons augmenter les unités de potentiel pour dominer la constante cachée dans $ o (t h) $) $ ".Je veux savoir comment cela se produit, mais ne savez pas vraiment comment poser cette question compliquée.

Answer 1

Comme vous soulignez que votre première équation n'est pas nécessairement correcte.

Permettez-moi de le réécrire en ajoutant explicitement les constantes multiplicatives: $ \ alpha d (n) + \ bêta t (h) - \ gamma t (h)= O (d (n)) $ , où $ \ gamma= 1 $ . Ici, le problème est que $ \ beta $ peut être plus grand que $ \ gamma= 1 $ .

Ce que disent les auteurs, c'est qu'au lieu de penser qu'une unité dans la valeur de votre fonction potentielle $ \ phi (h) $ contribue à une unité de potentiel, vous pouvez imaginer qu'il représente réellement $ \ gamma $ unités de potentiel. Cela revient à redonner à l'analyse avec une nouvelle fonction potentielle $ \ phi '(h) $ définie comme $ \ phi' ( H)=gamma \ cdot \ phi (h) $ . Si vous le faites, alors vous êtes capable de contrôler la valeur de $ \ gamma $ dans l'équation ci-dessus, tandis que $ \ beta $ reste la même chose.

cueillette une valeur de $ \ gamma \ ge \ beta $ garantit que $ \ alpha d (n) + \ beta t (h) - \ gamma t (h)=alpha d (n) - \ sous-graine {(\ gamma - \ beta)} _ {\ ge 0} t (h) \ le \ alpha d (n)= O (d (n)) $ , comme vous le souhaitez.