遞推關係：尋找大O

我想找到大O密集型以下遞推關係：遞推關係：尋找大O

T(n) = T(n-1) + n^c, where c >= 1 is a constant

所以我決定通過使用迭代解決這個問題：

T(n) = T(n-1) + n^c 
T(n-1) = T(n-2) + (n-1)^c 
T(n) = T(n-2) + n^c + (n-1)^c 
T(n-2) = T(n-3) + (n-2)^c 
T(n) = T(n-3) + n^c + (n-1)^c + (n-2)^c 
T(n) = T(n-k) + n^c + (n-1)^c + .... + (n-k+1)^c 

Suppose k = n-1, then: 

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

我不確定是否這是正確的，加上我真的很感謝一些關於如何從中得出Big O的指導。非常感謝！

來源

2010-07-11 Parth

T沒有終止定義 - 推測T（0）或T（1）被定義爲一個常量？ – 2010-07-11 23:44:53

似乎並不是一個..我猜想假設T（1）= 1 – Parth 2010-07-11 23:45:50

我意識到有很多網絡資源可以用來解決這個網站上的任何非主觀問題。如果一個網站值得鏈接，您應該將其作爲答案發布。 – 2010-07-13 03:06:31

是，你是正確的：

T（N）= N ^Ç +（N-1）^Ç +（N-2）^ç + ... + 3 ^Ç + 2 ^ç + 1，

和該和

T（n）= 0（n ^{c + 1}）。見例如Faulhaber's formula。事實上，甚至可以確定領先項中的常數（即使它與算法的漸近線不相關）：總和爲您，因爲您可以通過例如使用整合來確定。

來源

2010-07-13 03:23:34 ShreevatsaR

「你是對的」並不完全準確。他用k-1代替n，但只有4個術語（也見編輯問題）。另外，這被標記爲家庭作業。請不要只是放棄答案。並有一個錯字：n ^（c + 1）/（c + 1）+ O（n^c）:-) – 2010-07-13 13:43:21

我認爲省略號（...）作爲一個小小的疏忽失蹤（他將它們添加到一個地方，大概在你的回答後面，而不是在其他人面前），所以我在我的回答中明確地加上了它。作業：我甚至沒有回答這個問題，直到他反覆提問！ :-)如果有人直接提出作業問題，這是他們自己的損失，恕我直言。我甚至不能刪除這個答案，因爲它被標記爲接受。 – ShreevatsaR 2010-07-13 14:45:49

而不是工作你從n的方式，如何從0開始工作（我假設遞歸終止於0，你離開了那一點）。當你開始注意到一個固定點時（例如，在所有情況下重複相同的模式），你就有一個很好的答案。嘗試證明答案，例如通過歸納。

來源

2010-07-11 23:47:01 Carsten

你有什麼不正確的，但你是在正確的軌道上。

的錯誤，你做：

T(n) = T(n-3) + n^c + (n-1)^c + (n-2)^c  
T(n) = T(n-k) + n^c + (n-1)^c + (n-k+1)^c

你不能只從第一行到第二行。

隨着您增加k，右側的項數也增加。

要看到，想到寫這樣說的：

T(n) - T(n-1) = n^c. 

T(n-1) - T(n-2) = (n-1)^c 
.. 

T(n-k) - T(n-k-1) = (n-k)^c. 

.. 
T(2) - T(1) = 2^c

會發生什麼事，如果你添加這些嗎？

一旦你這樣做了，你能看到c = 1和c = 2的答案是什麼嗎？你能從那裏弄出一個最終答案的模式嗎？

來源

2010-07-11 23:47:50

我會首先觀察到n^c雖然受n的值影響，但對於n與n + 1不會更復雜 - 它決定了「運行時間」特定的術語。鑑於此，您可以假設（至少我會）該術語具有恆定的運行時間，並確定遞歸執行多少次以便給定n，並且您將獲得約束。

來源

2010-07-11 23:50:07

我可能誤解了Big-O意味着什麼 - 我在運行時思考 - 不是數學！ – 2010-07-12 00:03:44

爲了計算這些時，填寫幾個術語，並查找模式：

T（1）= 0 + 1^C

T（2）= T（1）+ 2^C = 0 + 1^C + 2^C

T（3）= T（2）+ 3^C = 0 + 1^C + 2^C + 3^C

T（4 ）= ...

現在用n來表達模式，你有你的答案。

來源

2010-07-13 03:03:51

哦，也只有最主要的術語很重要。 – 2010-07-13 03:20:33

不幸的是，「最主要的術語」並不重要，如果有足夠多的術語，占主導地位的術語很重要**。看到我的答案。 – Artelius 2010-07-13 03:39:58

我完全同意這一點，並意識到我最後的陳述是誤導性的。謝謝你的糾正。 – 2010-07-13 11:54:41

這：

T(n) = n^c + (n-1)^c + (n-2)^c + ... + 2^c + 1^c 
    < n^c +  n^c +  n^c + ... + n^c + n^c 
    = n * n^c 
    = n^(c+1)

這是O（n ^{C + 1}）。

爲了顯示這是一個合理的結合，注意，當c = 1，

T(n) = n + (n-1) + (n-2) + ... + 2 + 1 
    = n * (n-1)/2

這顯然是Θ（N ）。

來源

2010-07-13 03:38:48 Artelius

這可能只是我的一個誤解，因爲我不經常在這些類型的問題上工作，而是'O（n^[c + 1]）= O（n^c）'。這很像'O（cn）= O（n）'。它以增長率爲基礎，這個增長率仍然是「持續的」力量。 – 2010-07-13 11:58:27

@尼克：是的，它*是*您的錯誤理解。 O（n^2）不是O（n）。 – ShreevatsaR 2010-07-13 13:14:55

@ShreevatsaR：我看到那個角落的情況，如果你限制c> 1，怎麼辦？ – 2010-07-13 13:31:20

遞推關係：尋找大O

回答

相關問題