2017-11-18 216 views
0

你如何找到這樣的遞推關係的嚴格界限?這是一個重要的問題,我們期望證明m/log(m)是嚴格的漸近界。我嘗試使用感應,但它似乎無處可去。這是要麼我缺少對數規則或有更多的東西。復發T(n)= T(n - log(n))+ 1

+0

告訴我們你如何開始歸納,也許有人可以從那裏幫助你。 – ShadowMitia

回答

1

感應。假設所有k < nT(k) <= C k/log k對於某些C

展開復發(n/2)/log(n/2)次,更換log(.)log(n/2)(我們利用的事實,即T(n)log(n)是單調函數)。也就是說,

T(n) <= T(n - log(n/2) * (n/2)/log(n/2)) + (n/2)/log(n/2)

T(n) <= T(n/2) + (n/2)/log(n/2)

T(n) <= C (n/2)/log(n/2) + (n/2)/log(n/2)

現在你要證明右邊的表達被C n/log n界。算術和找到這樣的C是作爲一個練習。

+0

我不同意。我認爲解決方案的形式應該是: '(n-log(n))/(log(n-log(n)))' – ugar

+0

@nomadov它取決於你需要的近似程度。 –

+0

如何展開次數?(n/2)/ log(n/2)次?我不明白你是如何得到T(n)<= T(n-log(n/2)*(n/2)/ log(n/2))+(n/2)/ log(n/2 )' – ugar

相關問題