Subtrazioni di notazione ordine in fibonacci heap

Question

può ordinare la notazione da solo implica:

$ o (d (n)) + o (t (h)) - t (h)= o (d (n)) $ La mia ipotesi è che non puoi poiché la costante in O (t (h)) esistesse ancora dopo la sottrazione se la costante è> 0.

Bene, questo è in realtà il caso, ma ci sono fattori sottostanti.Questa equazione appare nell'analisi del mucchio di Fibonacci in CLRS (518).La giustificazione per questo passo proviene dalla funzione potenziale sottostante.Secondo gli autori, "possiamo ridimensionare le unità di potenziale per dominare la costante nascosta in $ o (t (h)) $ ".Voglio sapere come succede, ma non so davvero come porre questa domanda complicata.

Answer 1

Mentre sottolinea la tua prima equazione non è necessariamente corretta.

Lasciami riscriverlo aggiungendo esplicitamente le costanti moltiplicative: $ \ alfa d (n) + \ beta t (h) - \ gamma t (h)= o (d (n)) $ , dove $ \ gamma= 1 $ . Qui il problema è che $ \ beta $ potrebbe essere più grande di $ \ gamma= 1 $ . .

Cosa dicono gli autori è che invece di pensare che un'unità Nel valore della tua funzione potenziale $ \ phi (h) $ contribuisce un'unità di potenziale, puoi immaginare che in realtà stia rappresentando $ \ gamma $ unità di potenziale. Questo importi per la rifinitura dell'analisi con una nuova funzione potenziale $ \ phi '(h) $ definito come $ \ phi' ( H)=gamma \ cdot \ phi (h) $ . Se lo fai, allora puoi controllare il valore di $ \ gamma $ nell'equazione sopra, mentre $ \ Beta $ rimane lo stesso.

Raccogliere un valore di $ \ gamma \ ge \ beta $ assicurati che $ \ alfa d (n) + \ beta t (h) - \ gamma t (h)=gamma d (n) - \ unbreace {(\ gamma - \ beta)} _ {\ ge 0} t (h) \ le \ alfa d (n)= o (d (n)) $ , come desiderato.