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

Question

这是 SICP(计算机程序的结构和解释)的练习:

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

(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 '()))

... 2. 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?

观察这两个过程，在不对增长顺序进行任何计算的情况下，tree->list-2 的所有基本操作都是恒定的，而 tree->list-1 中的追加操作之一则不是。所以很明显tree->list-2比tree->list-1增长得更慢。

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

附加过程是:

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

根据定义，步数的增长顺序为 theta(l1)，其中 l1 是第一个列表中的元素数量。如果两个列表具有相同的长度，则增长顺序按 theta(n/2) 增长，其中 n 是两个列表的元素数量之和。基于这些，我尝试计算 tree->list-1 的增长顺序，如下所示:

假设追加时间为常数(仅初始)，那么我们会发现tree->list-1的增长顺序为theta(n)。由于追加是唯一不恒定的过程，因此我相信我可以安全地忽略其他基本操作。通过append的真实运行时间，我得到了以下观察结果。

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

0 个节点 - 常量
1 个节点 - 常量
3 个节点 - 1 次递归调用追加
7 个节点 - 5 次递归调用追加(前 2 个来自子树(上图)，3 个来自左分支)
15 个节点 - 17 次递归调用追加(10 个来自子树(上图)，7 个来自左分支)
31 个节点 - 49 次递归调用追加(34 个来自子树(上图)，17 个来自左分支)
63 个节点 - 129 次递归调用追加(98 个来自子树(上图)，31 个来自左分支) ...
n 个节点 - 2t+(n/2)，其中 t 是子树的步数，n 是树中的节点数

我的额外观察是:在完全不平衡的二叉树中:如果所有节点都在右分支中，则步数随着 theta(n) 的增长而增长。如果所有节点都在左分支中，则步骤数会像 (1+2+3+4+...+n-1) 一样增长，可能像 n(n-1)/2 (我在某处找到了这个公式)。根据我的数据，平衡二叉树的步数介于两者之间。

现在，随着节点数量加倍，步数的顺序为:(1, 5, 17, 49, 129)。它们的增长为 (4, 12, 32, 80)。

看来，我们可以通过以下方式得到具有 n 个元素的平衡二叉树的步数:2t+(n/2)，其中 t 是两个子树的步数，n 是节点数。

现在，在我的一生中，我找不到这个增长顺序所属的分类(例如线性、对数、二次、指数)，尽管我已经确认这个增长顺序比线性增长得快，比二次增长慢。

我的数据正确吗？尽管我无法对它进行分类，但我是否发现随着 n 的增加，tree->list-1 的增长顺序？

Answer 1

如果您使用书中的定义 ( 1.2.3 )，则不会，两个函数都没有相同的增长顺序。本书需要一个具有正确缩放因子的单一函数，该函数可以充当该过程的上限和下限(对于足够大的 n 值)。

我相信tree->list-1的增长顺序是n*log(n)。

如果我们将您的 t 视为函数，给出您的公式的附加步骤数 变成

t(n) = (n-1)/2 + 2*t((n-1)/2)

为了简单起见，使用 n/2 而不是 (n-1)/2，您的公式近似为:

t(n) = n/2 + 2*t(n/2)

使用这个简化的公式计算 t(n/2)，我们得到:

t(n/2) = (n/2)/2 + 2*t((n/2)/2)
       = n/4 + 2*t(n/4)

将其代入我们的 t(n) 计算中:

t(n) = n/2 + 2*t(n/2)
     = n/2 + 2*(n/4 + 2*t(n/4))
     = n/2 + n/2 + 4*t(n/4)

重复我们得到:

t(n) = n/2 + 2*t(n/2)
     = n/2 + n/2 + 4*t(n/4)
     = n/2 + n/2 + n/2 + 8*t(n/8)
     = n/2 + n/2 + n/2 + n/2 + 16*t(n/16)

即，我们得到一个包含 n/2 的序列，重复大约 log2(n) 次(树的深度)。即 n/2*log2(n)，其阶数与 n*log(n) 相同。

当 n 很小时，这不是一个很好的估计，但它确实看起来像 n 增长。最后一列显示了误差，作为实际值的比例，收敛到零(我认为这是一个等效的定义)。

depth   items           steps           n/2*log2(n)     |act-est|/act
1       1               0   
2       3               1               2               1.377
3       7               5               10              0.965
4       15              17              29              0.724
5       31              49              77              0.567
6       63              129             188             0.460
7       127             321             444             0.382
8       255             769             1,019           0.325
9       511             1,793           2,299           0.282
10      1,023           4,097           5,114           0.248
11      2,047           9,217           11,258          0.221
12      4,095           20,481          24,569          0.200
13      8,191           45,057          53,241          0.182
14      16,383          98,305          114,680         0.167
15      32,767          212,993         245,752         0.154
16      65,535          458,753         524,279         0.143
17      131,071         983,041         1,114,103       0.133
18      262,143         2,097,153       2,359,286       0.125
19      524,287         4,456,449       4,980,726       0.118
20      1,048,575       9,437,185       10,485,749      0.111
21      2,097,151       19,922,945      22,020,085      0.105
22      4,194,303       41,943,041      46,137,332      0.100
23      8,388,607       88,080,385      96,468,980      0.095
24      16,777,215      184,549,377     201,326,579     0.091
25      33,554,431      385,875,969     419,430,387     0.087
26      67,108,863      805,306,369     872,415,218     0.083
27      134,217,727     1,677,721,601   1,811,939,314   0.080
28      268,435,455     3,489,660,929   3,758,096,369   0.077
29      536,870,911     7,247,757,313   7,784,628,209   0.074
30      1,073,741,823   15,032,385,537  16,106,127,344  0.071
31      2,147,483,647   31,138,512,897  33,285,996,528  0.069
32      4,294,967,295   64,424,509,441  68,719,476,719  0.067