为什么学习算法

Author Avatar
WincerChan 7月 16, 2017
  • 在其它设备中阅读本文章

前言

对于算法,我个人的心情是挺复杂的,去年的时候有去刷过一段时间的 ACM 算法题,后来就不知怎么荒废了,直到最近看「SICP」才决定捡起来,这篇文章也算是对算法的一点感想。

增长的阶

不同计算过程在消耗计算资源速率可能存在巨大差异。为了描述这些差异的一种方法是采用「增长的阶」的记法,分析这一过程消耗的资源也就是我们平时所说的「算法分析」。

「令 $n$ 为一个参数,它能作为问题规模的一种度量,令 $R(n)$ 是一个计算过程在处理规模为 n 的问题时所需要的资源量。

我们称 $R(n)$ 具有 $\Theta(f(n))$ 的增长阶,记为 $R(n)=Θ(f(n))$,如果存在与 $n$ 无关的整数 $k_1$ 和 $k_2$,使得:$k_1f(n)\leq R(n)\le k_2f(n)$ 对于足够大的$n$值都成立。」

有了增长的阶的定义,我们就可以对一个过程所需资源有较具体的描述,例如:在上篇博客描述的线性递归计算过程中,步骤数目增长正比于输入 $n$。也就是说,这一计算过程所需步骤增长为 $Θ(n)$,其空间需求也是 $Θ(n)$。迭代的阶乘,其步数还是 $Θ(n)$ 而空间是 $Θ(1)$,即为一个常数。本文介绍的树形递归的「斐波那契」计算需要 $Θ(\phi^n)$ 步骤和 $Θ(n)$ 的空间。

实例

下面这个定义给定基数 $b$ 和正整数指数 $n$ 来计算 $b^n$:

$b^n=b\cdot b^{n-1}$

$b^0=1$

可以直接翻译成如下过程:

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

这是一个线性的递归计算过程,需要 $Θ(n)$ 步和 $Θ(n)$ 空间。就像阶乘和「斐波那契」,我们很容易将其形式化为一个等价的线性迭代:

(define (expt b n)
  (expt-iter b n 1))
(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product))))

这一版本需要 $Θ(n)$ 步和 $Θ(1)$ 空间。这一算法自然比一算法更好,复杂度更低,那么,还能更优化吗?

我们可以采用递归的思想,把问题转化为规模较小的子问题。例如:不是以采用下面这样的方式算 $b^8$:

$b\cdot(b\cdot(b\cdot(b\cdot(b\cdot(b\cdot(b\cdot b))))))$

而是用连续求平方,以更少的步骤完成计算:
$b^8=b^4\cdot b^4$
$b^4=b^2\cdot b^2$
$b^2=b\cdot b$

这一方法对于指数是 2 的乘幂都可以用。如果采用下面规则,我们就可以借助于连续求平方,来完成一般性的乘幂运算:

$b^n=(b^{n/2})^2$ 若 $n$ 是偶数

$b^n=b\cdot b^{n-1}$ 若 $n$ 是奇数

这一方法翻译为如下程序:

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))
(define (even? n)
  (= (remainder n 2) 0))

这一计算过程,在空间和步数上相对于 $n$ 都是对数的:用 fast-expt 计算 $b^{2n}$的时候,只需要比 $b^n$ 多做一次乘法。能够计算的指数值大约增长一倍。这样,计算指数 $n$ 所需要乘法次数增长大约以 $2$ 为底 $n$ 的对数值,这一计算过程增长的阶为 $\Theta(log\ n)$。

随着 $n$ 变大,$\Theta(log\ n)$ 增长与 $\Theta(n)$ 增长差异会变得非常明显。当 $n =1000$ 时,fast-expt 只需要 $14$ 次乘法。

当然,我们同样可以通过连续求平方的方法,设计一个对数步数的计算乘幂的迭代算法:

(define (even? n)
 (= (remainder n 2) 0))

(define (fast-expt b n)
 (fast-expt-iter b n 1))

(define (fast-expt-iter b counter product)
 (cond ((= counter 0) 1)
       ((even? counter) (square (fast-expt-iter b (/ counter 2) (* product b))))
       (else (* b (fast-expt-iter b (- counter 1) (* product b))))))

这一计算过程需要 $\Theta(log\ n)$ 步,$\Theta(1)$ 空间。

总结

你越努力的去思考、将算法的复杂度降的越低,算法应用于程序所占用的资源就越少,尽管该程序会不那么直截了当,但这是值得的。

本文标题: 为什么学习算法
最后更新:2017 年 12 月 24 日 - 20:12
本文链接:https://blog.itswincer.com/posts/af991767/
本文采用:署名-非商业性使用-禁止演绎 4.0 国际 协议进行许可,阅读 相关说明