如何獲得斐波那契遞歸的時間

我有一個任務，他們給我一個遞歸斐波那契算法，並要求返回一個時間。我用.SystemCurrentMilis完成了，我在下面發佈了我的代碼，但測試人員說需要很長的時間來計算時間，所以我認爲我必須給他們一些時間，因爲執行功能和時間太長。希望你的幫助球員。如何使函數timetocompute在任何即將到來的工作中更快地工作。如何獲得斐波那契遞歸的時間

import java.math.BigInteger; 
import java.math.BigDecimal; 

public class Fibonacci { 

public BigDecimal timeToComputeRecursiveFibonacci(int n) { 
    long startTime = System.currentTimeMillis(); 
    recursive(n); 
    long finishTime = System.currentTimeMillis(); 
    long tempTime = finishTime - startTime; 
    BigDecimal usedTime = BigDecimal.valueOf(tempTime); 
    return usedTime; 
} 


public BigInteger recursive(int n) { 
    if (n <= 1) 
     return BigInteger.valueOf(n); 
    return recursive(n - 1).add(recursive(n - 2)); 
}

}

來源

2017-09-17 DwaydeWade

動態規劃是前進的道路！想想當n = 3和n = 4時會發生什麼，你調用recursiveF方法多少次？ – SMA

我在想這個話題，我認爲如果有n = 3次方法調用比n多1次。我希望我的權利，但我不明白它如何幫助我。我在網上發現它的O（2^n），但是它的返回時間我怎麼不明白。 – DwaydeWade

我應該警告你，如果你的老師發現這個問題，你可能會面臨剽竊的指責。您應該創建一個[** Minimal **，完整且可驗證的示例]（http://stackoverflow.com/help/mcve），它可以演示您的問題，而不會泄露太多的分配解決方案。 –

-1

我已經創建了一個遞歸函數的一些測量。如果你仔細想想，如果你能測量recursive(n)那麼recursive(n+1)會慢幾倍，因爲它需要計算n和n-1的函數。

第n - 毫秒
30 - 25
31 - 43
32 - 70
33 - 113
34 - 196
35 - 301
36 - 513
37 - 926
38 - 1266
39 - 2210
40 - 3652

所以，你可以用1.65^10 * 25，這是1.65^m*time(n)從30時40估計數。這可以轉換爲幾年。我會嘗試做這樣的事情。

來源

2017-09-17 11:08:39

如何獲得斐波那契遞歸的時間

回答

相關問題