樹遞歸/時間複雜度計劃分配

如果你能幫助我這個問題的任何部分，我將不勝感激。謝謝。樹遞歸/時間複雜度計劃分配

2^0 = 1 
2^N = 2^(N-1) + 2^(N-1)

轉換這個定義爲所謂的兩到最電源的完全等同樹遞歸函數。描述其漸近時間複雜性並解釋爲什麼它具有這種時間複雜性。
現在編寫一個名爲tttpo_rec的函數，它計算完全相同的東西，但它使用具有O（n）時間複雜度的線性遞歸過程，並且還爲其掛起的操作使用O（n）空間。
現在編寫一個稱爲tttpo_iter的函數，它計算完全相同的東西，但它使用具有O（n）時間複雜度並且也使用恆定空間的線性迭代過程。
現在讓我們假設你想概括一個前面的定義，以便它可以處理任意的整數冪，這樣你就可以計算2^N，3^N等等。編寫一個函數叫做to-the-power-這需要兩個論點，並且提出另一個論點的力量。

這裏是模板：

;; to-the-power-of: integer integer -> integer 
;; This function raises m to the power of n, returning the result. 
;; m must be > 0 and n >= 0. 
(define (to-the-power-of m n) 
    ...) 

(check-expect (to-the-power-of 1 0) 1) ; base case 
(check-expect (to-the-power-of 2 3) 8) ; recursive case 
(check-expect (to-the-power-of 3 2) 9) ; recursive case

我們將增加一個限制：不能使用*運算符;你只能使用下面的遞歸函數做乘法：

;;; multiply: integer integer -> integer 
;; This function multiplies two non-negative integers, returning the result. 
;; Its time complexity is O(a). 
(define (multiply a b) 
    ...)

寫的功能，並介紹它的時間複雜度和原因。

來源

2008-10-23 dave

哈哈哈哈。我不應該爲人們做家庭作業問題，但這太有趣了。 :-P

這只是幼稚的實現。我可以回答這個問題，而不必提出其他問題。
```
(define (tttpo n) 
    (if (zero? n) 1 
       (+ (tttpo (- n 1)) (tttpo (- n 1))))) 
```
顯然這是一個非常愚蠢的實現，但是你被要求給它的漸近複雜性。
如何避免調用tttpo每次迭代三思。既然你問到避免使用*，您可能需要藏匿的tttpo結果。
閱讀上尾遞歸。具體而言，你需要知道如何將一般的遞歸算法轉換爲其對應的迭代（或尾遞歸，因爲這是計劃）的版本。
明顯，一旦你寫的代碼爲3（或者，讓我看看你的答案3，我們會進一步幫助你的。）

祝你好運！

來源

2008-10-23 03:33:31

第一種算法是O（2^n），並且可被寫爲如下：如下

(define (2pow x) 
    (if (= x 0) 1 
     (+ (2pow (- x 1)) 
     (2pow (- x 1)))))

這可以在O（n）的被重寫：

(define (2pow x) 
    (if (= x 0) 1 
    (* 2 (2pow (- x 1)))))

由於計劃使用尾部呼叫優化，我們可以將其寫成尾部遞歸函數，它佔用了常量堆棧：

(define (2pow x) 
    (define (internal x accum) 
    (if (= x 0) accum 
     (internal (- x 1) (* accum 2)))) 
    (internal x 1))

Generaliz編輯：

(define (to-the-power-of a b) 
    (define (internal x accum) 
    (if (= x 0) accum 
     (internal (- x 1) (* accum a)))) 
    (internal b 1))

編輯：，因爲我看你不能使用*，你可以寫你自己的整數乘法：

(define (mult a b) 
    (define (internal a accum) 
    (if (= a 1) accum 
     (internal (- a 1) (+ accum b)))) 
    (internal a b))

這是尾遞歸，所以它在不斷地運行堆棧空間。只需在上述任何算法中將*替換爲mult即可。

我還應該注意，所有這些函數都是直接寫入編輯器而不經過測試。使用需要您自擔風險

來源

2008-10-23 03:35:31

樹遞歸/時間複雜度計劃分配

回答

相關問題