2017-07-18 113 views
1

我學習的分而治之在Coursera的算法,我也遇到過這樣的復發關係:解決一個復發的關係T(N)= T(N-√N)+1

T(n) = T(n-√n)+1

答案給出的是:

O(√n)

我已經學會了掌握方法和復發樹分析,但我不知道如何分析這種復發的關係。
感謝您的幫助。

+0

你嘗試過這麼遠嗎? –

回答

2

enter image description here

我們可以通過使用二項展開式獲得在此階段的上界:

enter image description here

注意,RHS比LHS爲大n越小,這意味着每個時間我們應用近似值,我們從參數中減去一個較小的值到T,因此結果將是一個上限。

繼續m迭代:

enter image description here

假設T(n)終止於n = 0(或一些常數,無所謂)

enter image description here

,因此複雜性是O(m) = O(√n)


編輯:= 4√n上述錯了,對不起 - 本來應該是(2+5/√2)√n

相關問題