如何计算此斐波那契算法的效率？

Question

我正在使用 Racket（Scheme/Lisp 的派生词），并且我编写了这个使用累加器的斐波那契算法：

(define (fibonacci* n)
  (local (; NaturalNumber NaturalNumber NaturalNumber -> NaturalNumber
          ; Add accumulators for current and previous fibonacci numbers
          (define (fibonacci-acc x current previous)
            (if (= x n) current
                (fibonacci-acc (add1 x) (+ current previous) current))))
    (fibonacci-acc 0 0 1)))

这是对不使用累加器的函数的重大改进，如下所示：

(define (fibonacci n)
  (if (<= n 1) n
      (+ (fibonacci (- n 1))
         (fibonacci (- n 2)))))

但是我如何设置递归方程来计算效率多少？

Answer 1

好吧，这很容易，如果你计算新的数字，你只需取两个你已经知道的较小的数字。

每个新数字都在恒定时间内计算。

因此第 n 个斐波那契数的复杂度为 O(n) - 线性。

Answer 2

第二个函数多次计算相同的东西，所以它的复杂度是指数级的（O(2^n)，你可以得到更好的界限，但它在那个范围内）。

         f(5)
       /     \
     f(3)    f(4)
   /  |     /    \
f(1) f(2)  f(2)   f(3)
          /    \    |   \
        f(0)  f(1) f(1)  f(2)
                         /   \
                       f(0)  f(1)

正如您通过绘制递归树所见，即使对于小值，也经常重新计算多个值。

要看到它真的是指数的，想象一下 f(6) 的树：它将包含这棵树，因为它调用 f(5) 和 f(4) 的树，所以它将是一棵几乎两倍大的树。

使用累加器的解决方案通过自下而上找到所需的斐波那契数来避免这种情况，因此只计算绝对必要的。这使得 O(n) 得到第 n 个斐波那契数。

要了解第一种算法的效率如何，请查看线性函数与指数函数相比如何增长：

n   |   2^n
===========
1   |   2
2   |   4
3   |   8
4   |  16
5   |  32
6   |  64

基本上，正如您通过实验确定的那样，线性确实要快得多。

Answer 3

设 T(n) 为计算 (fib n) 的时间，其中 fib 为：

(define (fib n)
  (if (<= n 1) 
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

由于fib的正文有条件(if (<= n 1) ...)我们需要考虑两种情况。

如果 n<=1，则计算表达式 n。它是一个变量引用，需要常数时间。让我们将时间设置为 1（时间单位）。

简而言之，我们有：

T(0) = 1
T(1) = 1

对于大于 1 的 n，计算表达式 (+ (fib (- n 1)) (fib (- n 2)))))。根据 T 的定义，计算 (fib (- n 1)) 所需的时间恰好是 T(n-1)。同样，计算 (fib (- n 2)))) 需要时间 T(n-2)。然后将两个子表达式的结果相加 (+ ...)。添加两个 fixnums（63 位数字）所需的时间与变量引用的时间大致相同。所以我们设置时间对 1 进行加法。一起我们得到：

T(n) = 1 + T(n-1) + T(n-2)    for n>1

三个递推方程为：

T(0) = 1
T(1) = 1
T(n) = 1 + T(n-1) + T(n-2)    for n>1

有关 T 的分析，请参阅以下文档的第 8 页：

http://users.cecs.anu.edu.au/~peter/seminars/RunningTimeInduction.

归纳证明T(n)<=2^n.