012章 绪论+向量

01b-5: 图灵机

which of the following is not a component of a turing machine? 以下哪项不是图灵机的组成要件？

a tape of finite length 有限长的纸带 a tape of finite length 有限长的纸带 - 正确

a finite alphabet 有限的字母表

a finite set of states 有限种状态

a head for reading and writing 读写头

01-e-5: 数组倒置

the base cases of a recursive function are degenerated cases, without which the sequence of recursive function calls would go forever.

01xc-2: fib()：递推方程

the naive way of computing fib(n) recursively leads to a time complexity of 
直接用定义以递归的方式计算fib(n)的时间复杂度是：

 

θ(n2)

o(2n)  正确

θ(2n)

o(n)