算法之美第零章 习题
11 Mar 2013 by LelouchHe
0.1
简单的做法是能一眼看出来最好,不过这个对于某些很难,通用的方法是利用微积分中阶的概念(这就是O的意义好不好!),二者一减或者一除,然后比较结果同某常数的关系即可.
这是数学问题,但是对于常见的我们需要牢记.
0.2
\[c = 1 时, S = (n + 1) c\] \[c \neq 1 时, S = \frac{1 - c ^ n}{1 - c}\]然后容易证明结论(和0.1类似)
(数学啊..不行..我得补补数学..)
0.3
-
利用数学归纳法来证明,不过证明有个小trick,就是我们这里需要两个前提才能进行后推,所以得先说明$n = 6$和$n = 7$的时候都成立,然后去证明$n \geq 7$时会成立(此时我们就可以利用$n - 1$了,因为$n$至少为7,$n - 1$至少为6,肯定成立) 不过话说回来,这不是trick,而是数学归纳法的基本,还是数学差.
-
仍然使用归纳法来做,假设条件成立,反推最后c的范围.其实可以看到,这个条件并不强,在一开始的时候我就陷进去了,以为问题是找一个强的条件,但其实问题只要求找到,并没有像第三问那样求边界的值,所以有即可.这个提醒我们,不能过早陷入强条件的求解.
-
看了网友写的答案,觉得甚为不妥\(F _ n \leq 2 ^ {c n}\) \(F _ {n - 1} \leq 2 ^ {c (n - 1)}\)并不能推倒出\(F _ {n + 1} = F _ n + F _ {n - 1} \leq 2 ^ {c n} + 2 ^ {c (n - 1)} \leq 2 ^ {c (n + 1)}\) 因为这个条件强,这样的条件肯定能满足结论,但是满足结论的前提却不一定是这个,所以证明有欠缺(当然,可能补充说明一下才可以)
数学是薄弱的一项,逻辑思维还有待提高
0.4
-
写出算式即可证明 \(\begin{bmatrix} a & b \\\\ c & d \end{bmatrix} \cdot \begin{bmatrix} a & b \\\\ c & d \end{bmatrix} = \begin{bmatrix} a ^ 2 + b c & a b + b d \\\\ a c + c d & b c + d ^ 2 \end{bmatrix}\) 可以看到,2x2矩阵乘法需要4次加法和8次乘法
-
看到了$\log n$的记号,大家肯定都知道是分治了,其实计算$X ^ n$本来也有很多重复计算 \(X ^ n = \left \\\{ \begin{aligned} {X ^ {n / 2}} \cdot {X ^ {n / 2}} & \, & n = 2 k \\\\ {X ^ {(n - 1) / 2}} \cdot {X ^ {(n - 1) / 2}} \cdot X & \, & n = 2 k + 1 \end{aligned} \right.\)
-
假设某次运算结果为 $ \begin{bmatrix} a & b \
c & d \end{bmatrix} $ 乘以Fib矩阵 $ \begin{bmatrix} 0 & 1 \
1 & 1 \end{bmatrix} $,可得 \(\begin{bmatrix} a & b \\\\ c & d \end{bmatrix} \cdot \begin{bmatrix} 0 & 1 \\\\ 1 & 1 \end{bmatrix} = \begin{bmatrix} b & a + b \\\\ d & c + d \end{bmatrix}\) 这个最多是原先矩阵的2倍(因为只有两个加法而已,其实应该远远不到),初始矩阵大小为$O(1)$,所以$n$次相乘后,大小最多为$O(2 ^ n)$,根据数字大小和位数的关系($N = O(\log n)$),可知,最多位数为$O(\log {2 ^ n}) = O(n)$ -
Fib3需要做乘法的次数为$O(\log n)$,每次乘法耗时$M(n)$,那么总时间就是$O(\log n) M(n) = O(M(n)\log n)$
-
Fib3的乘法每次都会折半,其算式类似于下: \(T _ n = T _ {n / 2} + M(n) + O(n) = T _ {n / 2} + O(n ^ 2) + O(n)\) 对比2的答案即可看出,每次乘法都会折半,然后加上一个正比于N的矩阵(如果次数为奇数的话),可以看到$T _ n = O(n ^ 2)$,得到结论.
总结
这章本是引导章节,结果出现了很多我目前尚且不会的数学计算,当然,这是需要加强的,所以我尽量一边跟着solution,一边看导论研习,希望能完成目标
数学什么时候都是我的软肋,还有逻辑思维.