algorithm - 混合函数的增长顺序

Question

SICP 1.3.1节的求和过程产生一个空间和时间复杂度为N阶的线性递归过程。此过程的代码是:

(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 的空间和时间复杂度？我会忽略整个过程的线性递归风格，并将其中 fib 的树递归优先考虑为最坏的情况吗？我是否必须以某种方式结合 fib 和 sum-fib 的空间/时间复杂性，如果是这样，怎么做？另外，假设我从另一个程序员那里得到了 sum-fib，并且我将它用作更大系统中的一个组件。如果我的程序因为 fib 的实现方式而变慢，我怎么知道？

这是我在这个平台上的第一个问题，所以还请指教如何更好地发帖和找到问题的答案。感谢您的贡献。

Answer 1

您的代码中有一个轻微错误。检查 SICP 后，我假设您打算使用 >而不是 <在两个sum-integers和 sum-fib .这是我做的唯一修改，如果做错了，请指正。

注意:我没有正式的背景，但这个问题已经有一段时间没有答案了，所以我想我会与遇到这个问题的其他人分享我的想法。

时间

在处理时间复杂度时，我们关心执行了多少次迭代，如n变大。在这里，我们可以假设 n成为 a 之间的距离和 b (含)在sum-fib .函数 sum-fib本身只会递归 n在这种情况下的时间。如果a是 0 和 b是 9，那么该函数将运行 10 次。这是完全线性的，或 O(n)，但并不是那么简单:下一个要问的问题是每次迭代会发生什么？

我们知道求和部分是线性的，所以剩下的就是斐波纳契函数了。在内部，您会看到它要么立即终止( O(1) )，要么分支成两个对自身的递归调用。大 O 表示法关注最坏情况，即分支。我们将有 1 个调用转向 2，转向 4，转向 8，等等，n次。这种行为是 O(2^n)。

不要忘记这叫做 n次作为总体 O(n) 求和循环的一部分，因此总函数将为 O(n(2^n))。

空间

函数的空间要求有点不同。通过手写出发生了什么，你可以开始看到函数形式的形状。这就是 SICP 早期显示的内容，其中将“金字塔”函数与线性函数进行比较。

要记住的一件事是，Scheme 是尾调用优化的。这意味着，如果递归调用在函数的末尾(意味着在递归调用之后没有指令发生)，则可以重用该帧，并且不需要额外的空间。例如:

(define (loop n)
    (if (> n 2)
    0
    (loop (+ n 1))))

画出来(loop 0)会是:

(loop 0)
(loop 1)
(loop 2)
0

可以看到所需的空间是线性的。比较一下:

(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

在这种情况下，您可以看到所需的空间随着所需迭代次数的增加而增加。

在您的情况下，所需的空间将急剧增加为 n增加，因为 fib为每个数字生成一棵完整的树，并且不是尾递归的，sum-fib 也不是.

我怀疑所需的空间也将是 O(n(2^n))。 sum-fib函数(忽略 fib 调用)，似乎在空间上是线性的，或 O(n)。它调用 2 fib s 每次迭代。每个fib分支成 2 个以上，并且不是尾递归的，所以所需的空间是 O(2^n)。结合它们，我们得到 O(n(2^n))。我不确定这种情况是否会一直如此。

如何测试慢函数

您正在寻找的是一个探查器。它会在运行时监视您的代码，并向您报告哪些函数花费的时间最多、哪些函数被调用最频繁等信息。对于 Scheme，Dr. Racket是一个具有内置分析器的 IDE。

忠告:首先让您的软件运行，然后再考虑性能分析和优化。许多程序员陷入过度优化他们的代码，而没有先完成以查看真正的瓶颈所在。当事实证明 5 分钟的调整可以使您获得 50% 的提升时，您可以花费数周的时间利用神秘的算法获得 1% 的性能提升。