數據結構 - 運行時間和漸近邊界

Question

如果a> 0是固定變量，然後證明：LG（N + A）=Θ（LG n）的

請建議。

Answer 1

爲了證明F（N）= Θ（G（N）），需要證明有非零K，使得

LIM（正→ ∞）F（N）/克（N）= K

在你的情況，我們要證明

LIM（N → ∞）LG（N + A）/（LG N）

這是類型∞/∞的一個不確定的形式，所以我們可以應用l'Hôpital's rule並採取分子和分母的衍生物得到

LIM（正→ ∞）LG（N + A ）/（LG N）=

LIM（正→ ∞）（1/N + A）/（1/N）=

LIM（N → ∞）N /（N + A）

這又是一個不確定的形式，因此應用洛必達法則給出

LIM（正→ ∞）N /（N +α）

= LIM（N → ∞）1/1

= 1

因此，存在一個非零常數（即1），使得lg（n + a）/ lg n的極限值趨於無窮大等於該常數，因此lg（n + a）= Θ（lg N）。

希望這會有所幫助！