遞推關係：解決的T大O（N-1）

我解出大O一定的復發關係的問題，到目前爲止，截止到這一點只是遇到了參與這種形式的遞推關係：遞推關係：解決的T大O（N-1）

T(n) = a*T(n/b) + f(n)

對於上述情況，我很容易找到Big O符號。但我最近拋出一個弧線球以下公式：

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

我真的不知道怎麼去解決解決這個大的O.其實我已經嘗試過的方程式什麼如下堵漏：

T(n) = T(n-1) + 2 
T(n-1) = T(n-2) 
T(n-2) = T(n-3)

我不完全確定這是否正確，但我卡住了，需要一些幫助。謝謝！

來源

2010-07-11 Parth

假設T（1）= 0

T(n) = T(n-1) + 2 
= (T(n-2) + 2) + 2 
= T(n-2) + 4 
= (T(n-3) + 2) + 4 
= T(n-3) + 6 
= T(n-k) + 2k

集合K到N-1和你有

T(n) = 2n - 2

因此，它是O（N）

來源

2010-07-11 18:55:24

你在最後一行有錯誤，我編輯了它 – luke 2010-07-11 18:57:41

哦，是的，我做到了！謝謝！ – 2010-07-11 19:00:50

@AndreasJansson我不會在前兩步跟隨你的代數。你聲稱$ T（n-1）+ 2 =（T（n-2）+ 2）+ 2 $，但我不明白你是如何得出這個結論的。問題中沒有任何提示，因此如何做出這個假設？如果$ T（2）= 10000000000000000 $，我們不知道，那你怎麼能假定它不是？ – 2015-02-21 18:54:35

T（N）= 2 * n = 2 *（n-1）+2 = T（n-1）+2

因此T（n）= 2 * n這意味着O（n）

來源

2010-07-11 18:56:36 Chaos

由於問題已經得到解答，讓我在如何找到復發的複雜性的基礎上增加一些直覺。

主定理只適用於分而治之型復發，像T(n) = a*T(n/b) + f(n)其中a是子問題的數量和每個子問題的規模是原問題的1/b。但是再發生T(n) = T(n-1) + 2在技術上並沒有將問題「分」爲子問題。所以掌握定理在這裏不適用。
如果我們仔細觀察再發現，很明顯它會超過n步驟，並且每個步驟都需要一個固定的時間，在這種情況下爲2。所以複雜性將是O(n)。

我特別發現第二個直覺對於大多數重複（可能不是全部）非常有幫助。作爲一個例子，你可以嘗試類似的重複T(n) = T(n-1) + n，其複雜性當然是O(n^2)。

來源

2016-08-18 05:22:23 Nasir

遞推關係：解決的T大O（N-1）

回答

相關問題