Subtrações de notação de pedidos no heap de Fibonacci

Question

pode encomendar notação por conta própria:

$ O (D (n)) + O (T (H)) - T (H)= O (D (n)) $

Meu palpite é que você não pode desde que a constante no O (T (H)) ainda existia após a subtração se a constante for> 0.

Bem, este é realmente o caso, mas há fatores subjacentes.Esta equação aparece na análise de heap de Fibonacci em CLRS (518).A justificação para este passo vem da função potencial subjacente.De acordo com os autores, "podemos aumentar as unidades de potencial para dominar a constante escondida em $ O (T (T (H)) $ ".Eu quero saber como isso acontece, mas realmente não sabe como fazer essa pergunta complicada.

Answer 1

Como você aponta sua primeira equação não é necessariamente correta.

Deixe-me reescrevê-lo explicitamente adicionando as constantes multiplicativas: $ \ alfa d (n) + \ beta t (h) - \ gamma t (h)= O (D (n)) $ , onde $ \ gamma= 1 $ . Aqui o problema é que $ \ beta $ pode ser maior do que $ \ gamma= 1 $ . .

O que os autores estão dizendo é que, em vez de pensar que uma unidade No valor de sua função potencial $ \ phi (h) $ Contribui uma unidade de potencial, você pode imaginar que está realmente representando o recipiente de matemática $ \ gamma $ unidades de potencial. Isso equivale a refazer a análise com uma nova função potencial $ \ phi '(h) $ definido como $ \ phi' ( H)=gamma \ Cdot \ pHi (h) $ . Se você fizer isso, então você é capaz de controlar o valor de $ \ gamma $ na equação acima, enquanto $ \ beta $ fica o mesmo.

Escolhendo um valor de $ \ gamma \ GE \ beta $ garante que $ \ Alpha D (n) + \ beta T (H) - \ gamma t (h)=alfa d (n) - \ underbrace {(\ gamma - \ beta)} _ {\ GE 0} t (h) \ le \ alfa d (n)= O (D (n)) $ , conforme desejado.