为什么学习算法

前言对于算法,我个人的心情是挺复杂的,去年的时候有去刷过一段时间的 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$值都成立。」     阅读全文
WincerChan's avatar
WincerChan 7月 16, 2017

树形递归

树形递归与上一篇介绍的「线性递归」类似的另一种常见计算模式为「树形递归」。本质嘛,可以看作许多分支的线性递归。 还是直接上具体的例题。 「斐波那契数列^1」的定义如下 看到这个定义我们马上就能把它编写成程序: (define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))     阅读全文
WincerChan's avatar
WincerChan 7月 16, 2017

谈谈递归和迭代

前言首次接触递归(recursion)这个概念是在学习 C 语言的时候,当时老师是根据「汉诺塔」^1这一具体问题的求解来介绍递归这个概念,至于迭代(iterate),好像 C 语言老师压根没提这个概念,第一次是在 MIT 的 Python 导论中听说的,但当时听完之后也只是对迭代和递归只有极其有限的了解。正好借着 SICP,好好弄清楚二者的概念。 首先明确二者的概念: 递归:是指在函数的定义中使用函数自身的方法。 迭代:迭代是程序中对一组指令(或一定步骤)的重复。在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。     阅读全文
WincerChan's avatar
WincerChan 7月 10, 2017