SICP - 练习 2.63 - 确定增长顺序
SICP - exercise 2.63 - determining order of growth
这是 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 中的一个操作 append 不是.所以很明显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 的增长顺序：
假设append花费常数时间（只是初始），那么我们会发现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是节点数。
现在对于我的生活，我找不到这个增长顺序所属的分类（例如线性，对数，二次，指数）虽然我已经确认这个增长顺序比线性增长快并且比线性增长慢二次方。
我的数据正确吗？树->列表-1 的增长顺序是不是随着 n 的增加而无法分类？
如果您使用书中的定义 (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
我的猜测是第一个代码的二次时间最坏情况（1）/线性时间最佳情况（2）；线性时间永远是第二个。
(1) = left-degenerate tree (with all right branches of some bounded depth, like, no more than 1, or 2, say, 所以树向左倾斜，所有追加都被重新追踪以 "triangular" 的方式结束）；
(2) = 右退化树（如列表；所有左分支的深度都有限，因此所有追加都需要常数时间）。
第二个代码对于 (1) 最快，对于 (2) 慢两倍左右，因为它需要先增加堆栈然后展开它，而在 (1) 的情况下，堆栈将是深度不变。
所以您的分析是正确的（除了它不是平衡树上第一个代码的 theta(n)，而是另一个答案显示的 n log n；也称为 "linearithmic" 时间）。而 n(n-1)/2 仍然被认为是二次方的，因为常数和低阶项可以忽略。
这是 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 中的一个操作 append 不是.所以很明显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 的增长顺序：
假设append花费常数时间（只是初始），那么我们会发现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是节点数。
现在对于我的生活，我找不到这个增长顺序所属的分类（例如线性，对数，二次，指数）虽然我已经确认这个增长顺序比线性增长快并且比线性增长慢二次方。
我的数据正确吗？树->列表-1 的增长顺序是不是随着 n 的增加而无法分类？
如果您使用书中的定义 (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
我的猜测是第一个代码的二次时间最坏情况（1）/线性时间最佳情况（2）；线性时间永远是第二个。
(1) = left-degenerate tree (with all right branches of some bounded depth, like, no more than 1, or 2, say, 所以树向左倾斜，所有追加都被重新追踪以 "triangular" 的方式结束）；
(2) = 右退化树（如列表；所有左分支的深度都有限，因此所有追加都需要常数时间）。
第二个代码对于 (1) 最快，对于 (2) 慢两倍左右，因为它需要先增加堆栈然后展开它，而在 (1) 的情况下，堆栈将是深度不变。
所以您的分析是正确的（除了它不是平衡树上第一个代码的 theta(n)，而是另一个答案显示的 n log n；也称为 "linearithmic" 时间）。而 n(n-1)/2 仍然被认为是二次方的，因为常数和低阶项可以忽略。