【习题解答】从算法视角重审数学概念

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ##2.2 证明：对于任意整数,都存在非负整数，使得。

则

又

故对于任意整数都有

##2.5 本题直接证明第二问即可 证明:利用数学归纳法，很容易证明二叉树的边数比点数少一个。

基础：根节点0条边，1个点。

归纳：假设k个点的二叉树，边数比点数少1，则k+1个点的二叉树，去掉某叶节点后的子树有k个点，k-1个边，故加上该叶节点后有k+1个点，和k个边，假设依然成立。

结论：二叉树的边数比点数少一个。

故

所以，任意二叉树T都满足关系

##2.7 ###(1) 证明传递性:

证明传递性:

###(2)

故满足自反性

###(3) 证明对称性:

故同时满足自反、对称、传递关系，因此是等价关系。

###(4)

且

###(5) 和的对偶证明:

和的对偶证明:

###(6) 要证明这三个集合是空集，可以考虑反证。

假设第一个集合不是空集，则集合中存在一个，使得且

则

故矛盾。其他两个集合是空集同理，用反证法结合极限定义证明是空集，详略。

##2.8 本题对渐进增长率从小到大排序，并用表示偏序关系 ###(1)

###(2)

##2.16 ###(1) 由

故

###(2) 比较, 无法使用主定理，要么考虑用递归树结合直接计算，要么考虑用替换法结合数学归纳法证明。

例如本题可以直接计算。

注：中间用到了等比数列求和。

###(3)

任意取常数，显然都有

故

###(4)

故

###(5) , 无法用主定理，则考虑直接计算：

把看成整体，结合(2)得:

故

注：可以发现，能用主定理解决的问题，本质上都可以直接计算，传统的换元、数列求和等数学手段都是可以的；一旦使用主定理，必须要满足主定理的种种条件的限制。

###(6) , 无法用主定理，则考虑直接计算：

令，得:

故

###(7) ,

任意取常数，显然都有

故

###(8) 由得 ,

任意取常数，显然都有

故

###(9) 这种加型的递推公式，显然不是用主定理。直接计算这个等差数列得：

###(10) 对于等幂求和，显然

###(11) 先对递推公式变形，得：

由，故

###(12) (i) 对于偶数下标情况

由等幂求和，

对于奇数下标情况

由等幂求和，

综上，

###(13) 首先，符合题干递推公式，下面用数学归纳法证明。

设

基础情况：对于成立

归纳情况：假设对于成立

则成立

故极限情况，

因此证得

注：本题的思想是替换法加数学归纳法证明，其中常数c的选取和放缩的技巧，很有微积分极限证明题内味儿了

##2.18 由

故

假设进行次根号操作变成(我们认为根号后取到下整数)，即解。

即

故

##2.19 例如取2.15题的(2)和(5)中的取值，仔细体会master定理的情况(3)不能覆盖一些例子的原因。

##2.22 ###(1) 算法的输出是找到输入数组中最小的元素

###(2) 对于算法1，复杂度，故。

对于算法2，复杂度，由，故。

##2.24 ### MYSTERY

最坏情况时间复杂度

PERSKY

最坏情况时间复杂度

PRESTIFEROUS

最坏情况时间复杂度

CONUNDRUM

最坏情况时间复杂度

注：根据评论区反馈，上面答案有误，正确答案更新如下，更新时间2022.4.17

根据,则因为，需要修改的上限，

即

又根据，同理需要修改的上限

即

最坏情况时间复杂度