从指数级增长到对数级增长

under

in algorithm

Published: 2016-11-24

Fibonacci数是递归的经典例子,最简单的算法可以根据Fibonacci数的定义直接写出来:

(define (fib n)
  (cond ((< n 2) n)
        (else (+ (fib (- n 1)) (fib (- n 2))))))

这种算法的时间复杂度是指数级,因为它实际上是遍历了一个二叉树,树的结点介于\(fib(n+1)\)\(2^{n+1}\)之间,其中前者以很快的速度接近\((\frac{\sqrt{5}+1}{2})^{n+1} / \sqrt{5}\)

这种算法包含了非常多的重复计算,例如\(fib(n-2)\)这棵树要被计算2次,如果人工计算Fibonacci数,大部分人会采用迭代算法:

(define (fib n)
  (define (fib-iter k a b)
    (cond ((= k n) b)
          (else (fib-iter (+ k 1) (+ a b) a))))
  (fib-iter 0 1 0))

这种算法消耗的时间正比于参数n

然而还有更快的算法,在迭代算法中,每一次迭代都相当于一次线性变换:

\begin{equation*} \begin{bmatrix} fib(n+1)\\ f(n) \end{bmatrix} = \begin{bmatrix} 1& 1\\ 1& 0 \end{bmatrix} \begin{bmatrix} fib(n)\\ f(n-1) \end{bmatrix} \end{equation*}

\(A = \begin{bmatrix}1& 1\\1& 0\end{bmatrix}\),则:

\begin{equation*} \begin{bmatrix} fib(n)\\ f(n-1) \end{bmatrix} = A^{n-1} \begin{bmatrix} fib(1)\\ f(0) \end{bmatrix} \end{equation*}

其实就是指数的计算,可以用对数时间复杂度的算法完成:

(define (exp x n)
  (cond ((= n 0) 1)
        ((even? n) (exp (mul x x) (/ n 2)))
        (else (mul x (exp x (- n 1))))))

在不使用高阶函数或数据结构的情况下,定义矩阵乘法比较复杂,幸运的是,任何两个矩阵如果满足\(\begin{bmatrix}p+q& q\\q& p\end{bmatrix}\)的形式,则其乘积也一定满足这种形式,于是可以用两个参数p和q来表示这种线性变换:

\begin{equation*} a, b \rightarrow aq + bq + bp, ap + bq \end{equation*}

以及连续两次线性变换对应的新参数:

\begin{equation*} p, q \rightarrow p^2 + q^2, q^2 + 2pq \end{equation*}

最终得出Fibonacci数的算法(见SICP习题1.19):

(define (square x) (* x x))
(define (fib-fast n)
  (define (fib-iter count p q b a)
    (cond ((= count 0) b)
          ((even? count) (fib-iter (/ count 2)
                                   (+ (square p) (square q))
                                   (+ (square q) (* 2 p q))
                                   b
                                   a))
          (else (fib-iter (- count 1)
                          p
                          q
                          (+ (* a q) (* b q) (* b p))
                          (+ (* a p) (* b q))))))
  (cond ((< n 2) n)
        (else (fib-iter (- n 1) 0 1 1 0))))

这个算法和前面的指数计算一样,时间复杂度为对数级。

(完)