今天看《计算机程序的构造和解释》第一章, 里面提到了快速幂和斐波那契数列的快速算法. 感觉还挺巧妙的, 做一点笔记.
阶乘
通常我们求, 需要进行 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 个数, 会大大提高算法的效率, 每个数都只需要计算一次因而时间复杂度和空间复杂度分别为.
那么有没有更快的方法进行斐波那契数的求解呢.
在这里利用矩阵迭代可以加快这个速度, 具体实现依据以下举证的点乘:
注意到这里出现了矩阵的幂, 那么我们就可以想到上面提到过的快速幂, 从而实现 复杂度的算法.
来源: http://www.jianshu.com/p/e36aff31c078