树递归/时间复杂度计划分配

如果你能帮助我这个问题的任何部分，我将不胜感激。谢谢。树递归/时间复杂度计划分配

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

树递归/时间复杂度计划分配

回答

相关问题