即将回家

Posted by David Gu on January 25, 2014

中午去吃饭的路上,发现居然有家还开着的文具店,便进去逛了逛;看到这个古铜色的小本子——最让我“倾心”的是,连里面的纸张也是古铜色的。

Pretty Notebook

我是用不了这么漂亮的本子的;回家后,该送给谁呢?

前阵子,在图书馆里无意中和友人谈起了斐波那契数列,大概是围绕着“利用递归结构提高运算速度”这样的话题。当时我并没有回答好,因为想举个简单到显而易见的例子其实并不简单。于是,抽空又翻了翻 Structure and Interpretation of Computer Programs第一章,回顾了一下经典。

首先,举个简单到显而易见的计算乘幂的例子 —— 实现 $a^b$ 的计算大概有以下思路:

对于这种情况,代码倒是很好写:

long my_exp(int a, int b){
  if(b==0) return 1;
  return a*my_exp(a, b-1);
}

此时,时间的增长阶为 $ \Theta(n) $,空间的增长阶也为 $ \Theta(n) $ 。(线性递归嘛)

当然了,你也可以将其修改成“迭代”版本的 —— 也许 Lisp 的用户更喜欢这种“迭代”(另一方面,你可能更熟悉“尾递归”这个概念):

long my_exp(int a, int b, long result){
  if(b==0) return result;
  return my_exp(a, b-1, result*a);
}

此时,时间增长阶不变,空间增长阶变为 。(这些都是线性递归与线性迭代的基本属性)

举这么简单的例子可不是为了秀下限,而是为了下面的“魔术”所作之铺垫:

这样做的目的是把时间增长阶降为对数阶1 。代码如下:

long fast_exp(int a, int b){
  if(b == 0)
    return 1;
  else if(b%2 == 0)
    //注意b为偶数时的操作
    return pow(fast_exp(a, b/2), 2);
  else
    return a*fast_exp(a, b-1);
}

此时,空间的增长阶依然为 ;当然,类似的,依然可以将其改写为“迭代”的形式从而使空间的增长阶变为为 。(事实上,这是 SICP 后面的对应习题)

暂且撇开空间的增长阶,对于这个问题,是什么使时间的增长阶从 降为 ?答案就是“奇偶性”因素的利用。例如,对于 ,在第二种思路下,利用平方,可将步骤减少“大概”一半;即将 分解成子问题

下面,再来看篇头提到的那个问题:斐波那契数列。这个问题实在是经典,当时在图书馆谈论它,是因为我正巧在 Hackerrank 上提交关于斐波那契数列的问题;而代码是凭着对 SICP 书中一道习题的记忆写的,其基本思路是利用线性变换:

若对于 中的向量 做一次线性变换 ,得到:

则易知变换阵为

现应用变换 两次,令其效果等同于应用同样的一次变换 ,即:

在将这个数学模型应用于斐波那契数列之前,我们有必要看一下它的“迭代”计算版本(递归计算版本就不写了,众所周知的显而易见但低效),留意开头的那段注释:

//斐波那契数列的“迭代”版本
//我们定义斐波那契数列第0个数为0, 第一个数为1,之后的数为前两个数的和
//于是它的调用形式为fib(1, 0, n),n即为你欲求结果的序号
//可以看到,每次的迭代过程即为:next <- next+pre, pre <- next
long fib(long next, long pre, int n){
  if(n == 0)
    return pre;
  else
    return fib(next+pre, next, n-1);
}

上述“迭代”算法的时间增长阶为 ;而如果用之前阐述的线性变换模型,我们可以成功将时间增长阶降为

设初始向量为 ,初始变换矩阵 ,即 ;于是:

并且,最关键的一步是:

于是,正如对于乘幂的处理那样,我们把时间的增长阶降到了对数级(n 为偶数时,子问题的划分将步骤减少的大概一半)。这个问题的代码我就不写了;它本身就是 SICP 的一道习题,而比起用 Algo 语法来描述,我还是保留对 S 表达式的个人喜好。

尾声

我最终决定还是回家一趟,因为有些事情还是当面商议的好;但是,即使是回归故里,即使是所谓春节(我们的春节还真的是春节吗…除了放鞭炮;不知何地、何时能“古风犹存”),也不能在态度上有所放松。当然,目前作为一些公开课的忠实观众,我相信这一切是不会很容易松懈的;而最关键的是,对于我(们)来说,时间不多了,真的不多了。

最近差一点就戒烟失败了。我强忍着,半躺在凳子上,电脑放着 Cypress Hill 的 Rap,想象自己猛吸一口,“威武”地咳嗽,“吞云吐雾”,“行尸走肉”…

“Alright, that’s enough.”

  1. 确切的说,底数应为2;但根据渐进符号 的数学定义,其实底数并不是那么重要;SICP 中对这部分问题一笔带过,具体可参阅 MIT 的另一本经典教材《Introduction to Algorithms》