空間與時間的方案代碼分析

我正在通過在線麻省理工學院講授經典6.001課程的方式：計算機程序的結構和解釋。空間與時間的方案代碼分析

我想了解分析內存使用情況與執行時間方面的代碼複雜性。在前幾個講座中，他們提出了Fibonacci系列方案的解決方案。

他們在視頻中呈現的解決方案具有在x（線性遞歸性能）方面具有增長的特性，這在Fibonacci系列中存在很大問題。當你試圖找到一個更大的斐波那契數時，遞歸所需的空間變得很大。

他們建議試圖找到一種方法來獲得線性迭代性能，其中所需的內存空間在整個計算過程中保持不變並且不依賴於x。

我的解決方案如下。我的具體問題是，在內存使用情況和執行時間方面，我的Scheme代碼的性能分析如何？

(define (fib x) 

    (define (fib-helper target total current-index i-2 i-1) 
    (if (> current-index target) 
      (if (= target 1) 
       0 
       total) 
      (fib-helper target 
         (+ i-2 i-1) 
         (+ current-index 1) 
         i-1 
         (+ i-2 i-1)))) 

    (fib-helper x 1 3 0 1))

來源

2010-09-25 dvanaria

好，考慮到(fib n)導致n-1呼叫fib-helper，您的解決方案以線性時間運行。 fib-helper只爲每次迭代調用一次，並且每次迭代都是尾調用，因此您的程序在恆定空間中運行。

這意味着對(fib 1000)的調用應占用(fib 100)的CPU時間的約十倍，同時佔用相同數量的內存。

來源

2010-09-26 01:35:13 erjiang

看到您的來電fib-helper是正確的尾調用，這將在不斷的空間中運行。

我不能幫你執行時間雖然:)

來源

2010-09-25 08:45:23 leppie

空間與時間的方案代碼分析

回答

相關問題