如何計算遞歸函數的值？

我有遞歸函數：T（n）= 2T（n/2）+ n。我想通過向函數傳遞不同的參數並獲取函數的值來找到函數的複雜性。然後我會猜測函數的公式（例如n，n * log（n））。如何計算遞歸函數的值？

我寫了下面的代碼：

public static void main(String[] args) { 
    System.out.println(findValueOfTheFunction(2)); 
    System.out.println(findValueOfTheFunction(4)); 
    System.out.println(findValueOfTheFunction(8)); 
} 

static double findValueOfTheFunction(double n) { 
    if(n > eps) { 
     return 2*findValueOfTheFunction(n/2) + n; 
    } 
    else return 0; 
}}

我從代碼三點。 p1（2,10）和p2（4,24）和p3（8,56）。

作爲理解，所述的遞歸函數的複雜性爲O（n）= N *的log（n）。但是我的觀點不符合公式。

我已經在這裏做了一些研究，但似乎沒有人有類似的問題。

來源

2016-11-25 Artmal

你說的'O（N）= N *的log（n）'是什麼意思？大哦表示法不是公式，它是上限 –

算法的複雜性與輸出無關。這是關於獲得輸出需要多少時間。 – 4castle

這個任務聽起來像這樣：「遞歸函數T（n）= 2T（n/2）+ n描述了一些算法，通過找到不同n的函數值，然後猜測公式，找出算法的複雜性。 – Artmal

你的第一個問題是在這裏：

else return 0;

在某一點;你的遞歸結束;並達到如果。

，然後你開始乘以最後一次調用的結果......你猜怎麼X * Y * Z * ...... * 0可能計算到？！

因此，所有你的方法做的是將一些m * n個值（其中n是你的輸入;以及M取決於你遞歸如何常稱自己的方法，你的代碼轉換爲：

if (n>eps) { 
    return n + findValueOfTheFunction(n/2)

。長話短說：！？你的計算失去其結果的「有趣」的一部分，所以 - 而不是返回0 ...返回1

來源

2016-11-25 19:58:16 GhostCat

在這種情況下，我應該停止遞歸？ – Artmal

看到我更新的答案：關鍵是你不應該返回一個值「丟棄」遞歸**乘法**！記錄：我不確認你對n * log（n）的假設是真/假。我所說的是：你的**代碼**不符合所需函數T（n）= 2T（n/2）+ n。 – GhostCat

你有沒有爲此編寫代碼，您可以通過在給予值做一些數學n和然後取代：

t(1) = 2t(1/2) + 1 
t(2) = 2t(1) + 1 = 2(2t(1/2)+1) = 2*2t(1/2) 
t(4) = 2t(2) + 1 = 2*2*2*t(1/2) 
t(8) = 2t(4) + 1 = 2*2*2*2*t(1/2)

其餘的2 * 1不是那麼重要，你可以繼續留在t（1/2）部分。我猜測已經有些事了。

來源

2016-11-25 20:23:00 selimssevgi

如何計算遞歸函數的值？

回答

相關問題