混合函数的增长顺序
Order of growth in mixed functions
SICP 1.3.1节的求和过程产生了一个N阶space和时间复杂度的线性递归过程。此过程的代码是：
(define (sum-integers a b)
(if (< a b)
0
(+ a (sum-integers (+ a 1) b))))
我想知道的是，如果我决定要使用类似的过程对一系列斐波那契数求和：
(define (sum-fib a b)
(if (< a b)
0
(+ (fib a) (sum-fib (+ a 1) b))))
fib 定义为：
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
如何分析 sum-fib 的 space 和时间复杂度？我会忽略整个过程的线性递归风格，并将其中 fib 的树递归优先考虑为最坏的情况吗？我是否必须以某种方式结合 fib 和 sum-fib 的 space/time 复杂性，如果是这样，怎么做？另外，假设我从另一个程序员那里得到了 sum-fib，并且我将它用作更大系统中的一个组件。如果我的程序因为 fib 的实施方式而变慢，我怎么知道？
这是我在这个平台上的第一个问题，所以也请指教如何更好地 post 并找到问题的答案。感谢您的贡献。
您的代码中存在 轻微 错误。检查 SICP 后，我假设您打算在 sum-integers 和 sum-fib 中使用 > 而不是 <。仅此修改，如有错误请指正
注意：我没有正式的背景，但这个问题已经有一段时间没有答案了，所以我想我会与遇到这个问题的其他人分享我的想法。
时间
在处理时间复杂度时，我们关心的是随着n变大，执行了多少次迭代。这里，我们可以假设n为sum-fib中a和b（含）之间的距离。在这种情况下，函数 sum-fib 本身只会递归 n 次。如果 a 为 0 且 b 为 9，则该函数将 运行 10 次。这是完全线性的，或 O(n)，但它不是那么简单：下一个要问的问题是每次迭代会发生什么？
我们知道求和部分是线性的，所以剩下的就是斐波纳契函数了。在内部，您会看到它要么立即终止（ O(1) ），要么分支成两个对自身的递归调用。大 O 表示法关注最坏情况，即分支。我们将 1 次通话转为 2 次，转为 4 次，转为 8 次，等等，n 次。这种行为是 O(2^n).
不要忘记，作为总体 O(n) 求和循环的一部分，这被调用了 n 次，因此总函数将为 O(n(2^n))。
Space
函数的space要求有点不同。通过手写出发生了什么，你可以开始看到函数形式的形状。这是 SICP 早期显示的内容，其中 "pyramid" 函数与线性函数进行比较。
要记住的一件事是，Scheme 是尾调用优化的。这意味着，如果递归调用在函数的末尾（意味着在递归调用之后没有指令发生），则可以重用该帧，并且不需要额外的 space 。例如：
(define (loop n)
(if (> n 2)
0
(loop (+ n 1))))
提取 (loop 0) 将是：
(loop 0)
(loop 1)
(loop 2)
0
可以看到要求的space是线性的。将其与：
(define (loop n)
(if (> n 2)
0
(+ n (loop (+ n 1)))))
与(loop 0):
(loop 0)
(1 + (loop 1))
(1 + (2 + (loop 2)))
(1 + (2 + 0))
(1 + 2)
3
您可以看到，在这种情况下，所需的 space 随着所需迭代次数的增加而增加。
在您的情况下，所需的 space 将随着 n 的增加而急剧增加，因为 fib 为每个数字生成一棵完整的树，并且不是尾递归的， sum-fib.
也不是
我怀疑所需的 space 也将是 O(n(2^n))。 sum-fib 函数（忽略 fib 调用）似乎在 space 或 O(n) 中是线性的。它每次迭代调用 2 fibs。每个 fib 又分支成 2 个，并且不是尾递归的，因此所需的 space 是 O(2^n)。结合它们，我们得到 O(n(2^n))。是否永远如此，我不确定。
如何测试慢速函数
您正在寻找的是 探查器。它会在 运行 时监视你的代码，并向你报告哪些函数花费了最多时间，哪些函数被调用最频繁等信息。对于 Scheme，Dr. Racket 是一个 IDE 它有一个内置的分析器。
忠告：先让您的软件运行，然后再考虑性能分析和优化。许多程序员陷入过度优化他们的代码，而没有先完成以查看真正的瓶颈所在。当事实证明，5 分钟的调整可以使您获得 50% 的提升时，您可以花费数周的时间利用神秘的算法获得 1% 的性能提升。
SICP 1.3.1节的求和过程产生了一个N阶space和时间复杂度的线性递归过程。此过程的代码是：
(define (sum-integers a b)
(if (< a b)
0
(+ a (sum-integers (+ a 1) b))))
我想知道的是，如果我决定要使用类似的过程对一系列斐波那契数求和：
(define (sum-fib a b)
(if (< a b)
0
(+ (fib a) (sum-fib (+ a 1) b))))
fib 定义为：
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
如何分析 sum-fib 的 space 和时间复杂度？我会忽略整个过程的线性递归风格，并将其中 fib 的树递归优先考虑为最坏的情况吗？我是否必须以某种方式结合 fib 和 sum-fib 的 space/time 复杂性，如果是这样，怎么做？另外，假设我从另一个程序员那里得到了 sum-fib，并且我将它用作更大系统中的一个组件。如果我的程序因为 fib 的实施方式而变慢，我怎么知道？
这是我在这个平台上的第一个问题，所以也请指教如何更好地 post 并找到问题的答案。感谢您的贡献。
您的代码中存在 轻微 错误。检查 SICP 后，我假设您打算在 sum-integers 和 sum-fib 中使用 > 而不是 <。仅此修改，如有错误请指正
注意：我没有正式的背景，但这个问题已经有一段时间没有答案了，所以我想我会与遇到这个问题的其他人分享我的想法。
时间
在处理时间复杂度时，我们关心的是随着n变大，执行了多少次迭代。这里，我们可以假设n为sum-fib中a和b（含）之间的距离。在这种情况下，函数 sum-fib 本身只会递归 n 次。如果 a 为 0 且 b 为 9，则该函数将 运行 10 次。这是完全线性的，或 O(n)，但它不是那么简单：下一个要问的问题是每次迭代会发生什么？
我们知道求和部分是线性的，所以剩下的就是斐波纳契函数了。在内部，您会看到它要么立即终止（ O(1) ），要么分支成两个对自身的递归调用。大 O 表示法关注最坏情况，即分支。我们将 1 次通话转为 2 次，转为 4 次，转为 8 次，等等，n 次。这种行为是 O(2^n).
不要忘记，作为总体 O(n) 求和循环的一部分，这被调用了 n 次，因此总函数将为 O(n(2^n))。
Space
函数的space要求有点不同。通过手写出发生了什么，你可以开始看到函数形式的形状。这是 SICP 早期显示的内容，其中 "pyramid" 函数与线性函数进行比较。
要记住的一件事是，Scheme 是尾调用优化的。这意味着，如果递归调用在函数的末尾（意味着在递归调用之后没有指令发生），则可以重用该帧，并且不需要额外的 space 。例如：
(define (loop n)
(if (> n 2)
0
(loop (+ n 1))))
提取 (loop 0) 将是：
(loop 0)
(loop 1)
(loop 2)
0
可以看到要求的space是线性的。将其与：
(define (loop n)
(if (> n 2)
0
(+ n (loop (+ n 1)))))
与(loop 0):
(loop 0)
(1 + (loop 1))
(1 + (2 + (loop 2)))
(1 + (2 + 0))
(1 + 2)
3
您可以看到，在这种情况下，所需的 space 随着所需迭代次数的增加而增加。
在您的情况下，所需的 space 将随着 n 的增加而急剧增加，因为 fib 为每个数字生成一棵完整的树，并且不是尾递归的， sum-fib.
我怀疑所需的 space 也将是 O(n(2^n))。 sum-fib 函数（忽略 fib 调用）似乎在 space 或 O(n) 中是线性的。它每次迭代调用 2 fibs。每个 fib 又分支成 2 个，并且不是尾递归的，因此所需的 space 是 O(2^n)。结合它们，我们得到 O(n(2^n))。是否永远如此，我不确定。
如何测试慢速函数
您正在寻找的是 探查器。它会在 运行 时监视你的代码，并向你报告哪些函数花费了最多时间，哪些函数被调用最频繁等信息。对于 Scheme，Dr. Racket 是一个 IDE 它有一个内置的分析器。
忠告：先让您的软件运行，然后再考虑性能分析和优化。许多程序员陷入过度优化他们的代码，而没有先完成以查看真正的瓶颈所在。当事实证明，5 分钟的调整可以使您获得 50% 的提升时，您可以花费数周的时间利用神秘的算法获得 1% 的性能提升。