例1:计算x^n(X的n次方)
可以采用如下算式来计算:
x^0 = 1
x^n = x*x^(n-1) = x*x*x^(n-2) = ……
那么,很容易得到该计算过程的递归表示:
(define (exp x n)
- (if (= n 0)
- 1
- (* x (exp x (- n 1)))))
很容易看出来,这个计算的时间和空间复杂度均为O(n)。这便是一个线性递归。为了减少其空间复杂度,可以使用线性迭代来代替(使用递归实现):
(define (exp-iter x n)
- (define (iter x n r)
- (if (= n 0)
- r
- (iter x (- n 1) (* r x))))
- (iter x n 1))
计算过程依然有改进空间,那便是可以降低时间复杂度。根据
x^n = x^(n/2)*x^(n/2)
可知,计算x^n的时间复杂度可以降低为O(logn)。此时,需要一个循环不变式来保证计算结果的正确性。设r初始值为1,则在计算过程中,从一个状态迁移到另一个状态(n为奇数迁移到n为偶数)时,r*x^n始终保持不变。而此时计算方法为:
n为奇数,则x^n = x*x^(n-1)
n为偶数,则x^n = x^(n/2)*x^(n/2) = (x^2)^(n/2)
因此,计算过程如下:
(define (fast-exp-iter x n)
- (define (iter x n r)
- (cond ((= n 0) r)
- ((even? n) (iter (* x x) (/ n 2) r))
- (else (iter x (- n 1) (* r x)))))
- (iter x n 1))
例2:a*n可以写成a+a*(n-1)的形式。那么采用加法和递归来计算则是:
(define (mul x n)
- (if (= n 0)
- 0
- (+ x (mul x (- n 1)))))
同样,可以采用迭代的方式来计算:
(define (mul-iter x n)
- (define (iter x n r)
- (if (= n 0)
- 0
- (iter x (- n 1) (+ r x))))
- (iter x n 0))
与例1相似,也可以将迭代计算的时间复杂度降为O(logn):
- (define (fast-mul-iter x n)
- (define (iter x n r)
- (cond ((= n 0) r)
- ((even? n) (iter (+ x x) (/ n 2) r))
- (else (iter x (- n 1) (+ r x)))))
- (iter x n 0))
这个计算过程的循环不变式是什么呢?
阅读(3246) | 评论(0) | 转发(0) |