新算法的遞推方程

我正在尋找一種遞歸算法來評估我所稱的因子（m，n）= m * m + 1 * ... * n，幫幫我。新算法的遞推方程

這個算法的複雜性是什麼？

來源

2014-02-16 Hassnain

讓T(n, m)是Factorial(n, m)時間複雜度。

讓g(n) = Factorial(n, 1)和T"(n)是g(n)的時間複雜度，則：

T(n, m) <= T"(n) + T"(m - 1)任何n, m

和T"(n) = T"(n - 1) + O(1)這是O(n)。

綜上所述，T(n, m) = O(n) + O(m - 1) = O(n + m)

來源

2014-02-17 02:06:49 pkacprzak

您的解決方案對我來說似乎很奇怪！請注意，乘法的數量是n-m。那麼，爲什麼O（n + m）？ – DanielTheRocketMan

@DanielTheRocketMan你刪除了OP發佈的代碼。我的回答是對該代碼的分析 – pkacprzak

對不起@pkacprzak，我沒有刪除任何東西。我覺得我甚至沒有聲望做這種版本（我猜）。我只是在問題中加入了一些詞語來說明問題。但是，我不明白原因，他們也消失了。當我再次嘗試編輯時，我寫的字就在那裏。然後我取消它，我再也看不到任何東西。也許你可以解決製作第二版的問題。我沒有聲望。有一些關於將n-m分成兩半......現在我寫的算法沒有任何意義。有可能爲此寫一個更簡單的解決方案。 – DanielTheRocketMan

其將具有遞推方程T（N）= T（N-1）+ 2，在階乘的函數呼叫的情況下（N，1）

來源

2014-02-17 01:31:08 Hassnain

新算法的遞推方程

回答

相關問題