Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1719821
  • 博文数量: 177
  • 博客积分: 9416
  • 博客等级: 中将
  • 技术积分: 2513
  • 用 户 组: 普通用户
  • 注册时间: 2006-01-06 16:08
文章分类

全部博文(177)

文章存档

2013年(4)

2012年(13)

2011年(9)

2010年(71)

2009年(12)

2008年(11)

2007年(32)

2006年(25)

分类: Python/Ruby

2012-02-25 13:51:55

例1:计算x^n(X的n次方)
可以采用如下算式来计算:
x^0 = 1
x^n = x*x^(n-1) = x*x*x^(n-2) = ……
那么,很容易得到该计算过程的递归表示:
    (define (exp x n)
  1. (if (= n 0)
  2.     1
  3.     (* x (exp x (- n 1)))))

很容易看出来,这个计算的时间和空间复杂度均为O(n)。这便是一个线性递归。为了减少其空间复杂度,可以使用线性迭代来代替(使用递归实现):

    (define (exp-iter x n)
  1.   (define (iter x n r)
  2.     (if (= n 0)
  3.         r
  4.         (iter x (- n 1) (* r x))))
  5.   (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)
  1.   (define (iter x n r)
  2.     (cond ((= n 0) r)
  3.           ((even? n) (iter (* x x) (/ n 2) r))
  4.           (else (iter x (- n 1) (* r x)))))
  5.   (iter x n 1))

例2:a*n可以写成a+a*(n-1)的形式。那么采用加法和递归来计算则是:

    (define (mul x n)
  1.   (if (= n 0)
  2.       0
  3.       (+ x (mul x (- n 1)))))

同样,可以采用迭代的方式来计算:

    (define (mul-iter x n)
  1.   (define (iter x n r)
  2.     (if (= n 0)
  3.         0
  4.         (iter x (- n 1) (+ r x))))
  5.   (iter x n 0))

与例1相似,也可以将迭代计算的时间复杂度降为O(logn):

  1. (define (fast-mul-iter x n)
  2.   (define (iter x n r)
  3.     (cond ((= n 0) r)
  4.           ((even? n) (iter (+ x x) (/ n 2) r))
  5.           (else (iter x (- n 1) (+ r x)))))
  6.   (iter x n 0))
这个计算过程的循环不变式是什么呢?
阅读(3246) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~