请问sicp 2.63题

tomato · #1 (**permalink**) 2006-05-01

Exercise 2.63. Each of the following two procedures converts a binary tree to a list.

lisp 代码:

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))

b. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?

第一种方法是T(n) = 2 * T(n/2) + 1
由master theorem得到时间复杂度是O(n)
但第二种方法是T(n, m) = T(n/2, T(n/2, m)) + 1
这个我就不知道怎么算时间复杂度

tomato · #2 (**permalink**) 2006-05-01

晕，1算错了，append是O(n)，所以1是O(nlog(n))
那么2该怎么算？

colinzhengj · #3 (**permalink**) 2006-05-02

Should be
T(n, m) = T(n/2, Length(n/2, m)) + T(n/2, m) + c1
T(1, m) = c2
=>T(n, m) = theta(n)

tomato · #4 (**permalink**) 2006-05-03

谢谢
明白了，呵呵

主题工具
显示可打印版本邮寄本页给好友
显示模式
平板模式切换到混合模式切换到树形模式