诡秘深奥的现代魔法 1.2 上

1.2 过程与它们产生的计算

菜鸟的读书笔记,如果有常识性错误和非常识性错误请毫不留情的开口指正!

1.2.1 线性的递归和迭代

能耐心看这个语焉不详的文章的读者都知道递归和迭代是两种循环的方式。但是SICP 中说道,一个递归的过程中也有递归和迭代的区别,这就是文中所说的:递归计算过程,和迭代计算过程,我们通常说的递归和迭代只是从语法上而言的,书里说的是计算过程,一个递归计算过程需要维护一个栈来储存信息,所以所需的空间是线性增长的(空间复杂度O(n)),但是迭代计算过程对空间的要求是常数级的(O(1)),是维护着一系列“状态”,当调用自身的时候,其会释放空间,所以会保持函数的递归深度为1。
所以如果要用递归过程的话,如果可能最好用迭代计算过程,当然,编译器或者解释器要支持尾递归优化(当一个过程是迭代计算过程,那么就可以说是尾递归的),能够在递归中不断释放栈,比如说我喜欢的Python 就不支持,仁慈的终生独裁者先生还讲了一堆说程序员最好不要用递归balabala,不过这种实用主义的哲学正是Python 的魅力所在。

迭代计算过程就是那种其状态可以用固定数目的状态变量描述的计算过程,而与此同时,有存在一套固定的规则,描述了计算过程在一个状态到下一个状态转换时,这些变量的更新方式;还有一个(可能有的)结束检测,它描述了这一计算过程应该终止的条件。

注:书中说常见语言的递归过程,即使是尾递归也往往需要线性储存空间,但是现在C 是支持尾递归优化的。并且即使编译器没有尾递归优化也可以用手动 goto 语句来实现。

练习

1.9

1.10

1.2.2 树形递归

这一小节,最大的收获是原来用黄金分割来计算斐波那契数列可以在对数时间复杂度O(logN)内完成。

换零钱那个,我一直对这种排列组合发愁,所以没怎么看懂,之后想了想,是分两拨:

  1. 用了最大的面额的,减去最大面额的值,递归。
  2. 没有用最大面额兑换的,不考虑最大的面额,递归。

然后这样就会展开一个二叉树,其中树叶的数量就是总数,可以画图来看一下:

count

这张图是用这样的方法,用1, 2, 5 去划分 6的情况。每个节点的左枝是第一种方法所递归的,右枝是第二种。(update: 之前这里左右搞反了。)

然后蓝色的线就代表每个叶子所对应的排列方式。

练习

1.11

做的时候脑袋愚蠢没想出来迭代过程怎么写,竟然想用迭代过程遍历递归树(但最后因为没办法还原父节点的位置而作罢),躺在床上才想到可以直接递推。

其中 (f 2 1 0 2) 需要解释一下,2 1 0 分别是f(3-1) f(3-2) f(3-3) 也就是说表示的是f(4) 中的几个项,下一次迭代中就会变成f(4) f(3) f(2),这样不断递推。

1.12

如果从第一层往下推很难,但是从某层往上推就很简单,就像造金字塔一样,从地基开始。

1.13

喵的这是数学题吧!一定是数学题吧!当然是数学题吧!还是证明题!要用数学归纳法有没有!有空再做。至少要等我会用LaTeX 了再说。

1.2.3 增长的阶

常说的时间复杂度和空间复杂度。

练习

1.14

我再画一张图,和 1.22 小节的图比较。虽然题目里让画的是cc 的,但是应该没有差别。

count_2

大致可以看出,空间和时间复杂度都是线性增长的。但是我在网上看了一下有分歧,这个暂且保留。

1.15
  • a) 应该是五次,因为 12.15/(3^4) = 0.15 > 0.1 12.15/(3^5) = 0.05 < 0.1。
  • b) 应该是对数阶。

未完待续,不知道下一篇是“下” 还是“中”。

诡秘深奥的现代魔法 1.2 上》上有3条评论

  1. Pingback引用通告: 诡秘深奥的现代魔法 – SICP 读书笔记 0 | 蛋炒饭

发表评论

电子邮件地址不会被公开。 必填项已用*标注