阶乘、快速幂与斐波那契数列

今天看《计算机程序的构造和解释》第一章，里面提到了快速幂和斐波那契数列的快速算法。感觉还挺巧妙的，做一点笔记。

阶乘

通常我们求，需要进行n次迭代，也就是说方法的时间复杂度为，如果使用的是递归的算法

#阶乘的递归算法
(define (factorial n)
    (if  (= n 1)
          1
          (* n (factorial (- n 1))))

那么该算法的空间复杂度为，因为在每一次迭代都需要保存相应的值等待递归的数值进行计算。
如果使用的是迭代的方法

#阶乘的迭代算法
(define (factorial n)
     (fact-tier 1 1 n)  #调用fact-iter方法
 (define （fact-tier product counter max-count)
        (if  (> counter max-count)
              product
              (fact-tier (* counter product) #目前的阶乘值
                         (+ counter 1)   #目前的迭代轮数
                         (max-counter))) #目标迭代轮数

这样的话，迭代方法在时间复杂度依然为的情况下，把空间复杂度降到了也就是说只需要常数大小的空间即可完成算法。

快速幂

对于幂函数，我们也可以用以上两种方法进行计算，是时间复杂度和空间复杂度也和阶乘的相应算法一致。但是如果使用快速幂的方法，可以使得时间复杂度从减小到。
计算x的n次幂,如果n为偶数显然有也就是说我们仅需要计算其n/2幂，然后平方即可，如果n为奇数可以写成，该方法可以迭代的进行，例如对，仅需计算，两轮迭代就可以得到结果。而通常的算法需要进行16轮计算。可以大大降低计算所需时间。

斐波那契数列的快速算法

斐波那契数列是非常有名的一个数列，因为在兔子繁殖的例子中被使用，也有时被叫做兔子数列
简单的描述斐波那契数列：

如果我们需要计算第n个斐波那契数，如果使用比较直观的递归算法，也就是上面描述的这样，那么算法的时间复杂度达到了，空间复杂度达到了，因为对于每一个分支都需要独立的进行一次计算。
显然如果使用迭代的方法，从第一个数开始依次计算出第n个数，会大大提高算法的效率，每个数都只需要计算一次因而时间复杂度和空间复杂度分别为.
那么有没有更快的方法进行斐波那契数的求解呢。
在这里利用矩阵迭代可以加快这个速度，具体实现依据以下举证的点乘：

注意到这里出现了矩阵的幂，那么我们就可以想到上面提到过的快速幂，从而实现复杂度的算法。