SICP -练习2.63 -确定增长顺序

Question

以下是SICP (计算机程序的结构和解释)的一个练习：

练习2.63:以下两个过程中的每一个都将二叉树转换为列表。 (定义(树->列表-1树)(如果为空？(树) '() (追加(树->列表-1(左枝树))(反(条目树)(树->列表-1(右枝树)(定义(树->列表-2树)(定义(复制到列表树结果列表)(如果(空？)结果列表(复制到列表(左枝树)(反(条目树)(复制到列表(右枝树)结果列表)(复制到列表树‘() . 2.这两个程序在将n个元素的平衡树转换为列表所需的步骤数目上是否具有相同的增长顺序？如果没有，哪一个长得更慢？

从这两个过程来看，没有对增长顺序进行任何计算，树->列表-2的所有基本操作都是恒定的，而树->列表-1中的一个操作则不是。所以很明显，树->列表-2比树->列表-1增长得慢。

现在，虽然这个练习并没有具体要求我们这样做，但我想找出树->列表-1的步骤数的增长顺序。以下是我的尝试。

所附程序如下：

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) 
            (append (cdr list1) 
                    list2))))

从定义中，步骤数的增长顺序增长为θ( l1 )，其中l1是第一个列表中的元素数。如果两个列表具有相同的长度，则增长的顺序为θ(n/2)，其中n是两个列表的元素数之和。在此基础上，我尝试计算树->列表-1的生长顺序，如下所示：

假设追加的时间是恒定的(只是初始时间)，那么我们会发现树->list-1的增长顺序随着θ(N)的增加而增长。由于追加是唯一不是常量的过程，我相信我可以安全地忽略其他基本操作。通过附加的实际运行时间，我得到了以下观察结果。

注:我观察到的树木是平衡的。因此，我通过将节点数量增加一倍(或增加树的高度)来试验运行时间。

0节点-常数

1节点-常数

3个节点-一个要追加的递归调用

7个节点-5个递归的追加调用(前2个来自子树(上面)，3个来自左分支)

15个节点-17个对追加的递归调用(10个来自子树(上面)，7个来自左分支)

31个节点-49个递归追加调用(34个来自子树(上面)，17个来自左侧分支)

63个节点-129个递归追加调用(98个来自子树(上面)，31个来自左分支).

N节点- 2t+(n/2)，其中t是子树的步数，n是树中的节点数。

我的额外观察是:在一个完全不平衡的二叉树中:如果所有节点都在正确的分支中，那么步骤的数量就会随着θ(N)的增加而增加。如果所有节点都在左分支中，那么步骤的数量就会增长为(1+2+3+4+.+n-1)，可能类似于n(n-1)/2 (我在某个地方找到了这个公式)。根据我的数据，平衡二叉树中的步骤数在两者之间增加。

现在，当节点数加倍时，步骤数的顺序是：(1，5，17，49,129)。它们以(4，12，32，80)的形式生长。

我们似乎通过: 2t+(n/2)得到了具有n个元素的平衡二叉树的步数，其中t是两个子树的步数，n是节点的个数。

就我的生活而言，我找不到这个增长顺序属于(例如线性、对数、二次、指数)的分类，尽管我已经证实了这个增长顺序比线性增长快，增长比二次增长慢。

我的数据正确吗？我是否发现了树->列表-1随n的增加而增长的顺序，即使我不能将它分类？

Answer 1

对于第一个代码，我的猜测是二次时间最坏情况(1)/线性时间最佳情况(2)；对于第二个代码，线性时间总是最坏的。

( 1 ) =左退化树(所有右枝都有一定的有界深度，例如，不超过1或2，因此树向左倾斜，所有附加物都以“三角形”的方式重新追踪)；

(2) =右退化树(类似列表；所有左分支都具有一定的有界深度，因此所有附加都需要恒定的时间)。

第二段代码对于(1)最快，对于(2)大约慢两倍，因为它需要先增长堆栈，然后展开它，而在(1)情况下，堆栈将具有恒定的深度。

因此，您的分析是正确的(只不过对于平衡树上的第一个代码，它不是θ(N)，而是另一个答案显示的n个log；也称为“线性化”时间)。n(n-1)/2仍然是二次型的，因为常数和低阶项是可以忽略的.