|
第三章 函数的增长 第三章读书笔记基本完成了，最后三题（思考题）的答案没给或者没给全，这是因为最近我的时间确实比较紧，请大家原谅（如果迫切需要解答请与我联系），另外，我想结识一点正在学习算法的仁兄，把算法导论（我想学算法的都会看这本书吧）的读书笔记完善，并且尽量减少错误。我的读书笔记原版是用Word2007+Aurora插件（使用MikTex脚本的一个工具）所写，如果哪位想帮我一起完善这部笔记，请联系我，我会把word版本笔记发给你的。 第三章没有真正的算法出现，但是这些数学方面的知识对以后学习算法，特别是判断和计算算法的效率和复杂度是有很大帮助的。本章的内容很抽象，但是其实都是很容易理解的。重要的是不仅仅看，而且要多想，动手算。 以后的读书笔记将不再把一些书本上的原本内容（比如题目）抄录下来，而只是把一些重点内容和我的理解和一些题的解答写上去，这本书很有用的，建议大家不要不舍得花这点钱，买一本吧。 记号：渐近确界 ，存在正常数 和 ，使对所有的 ，有： 记号：渐近上界 ，存在正常数和 ，使对所有的 ，有： 记号：渐近下界 ，存在正常数和 ，使对所有的 ，有： 记号：非渐近紧确的上界 ，对任意正常数，存在常数 ，使对所有的，有： 记号：非渐近紧确的下界 ，对任意正常数，存在常数 ，使对所有的，有： 定理： 传递性： 自反性： 对称性： 转置对称性： 函数f和g的渐近比较和两个实数a与b的比较做类比： 这个类比对理解这些渐近记号很有帮助。 如果较大。 ，则比渐近较小；如果，则比渐近 三分性：对两个实数a和b，下列三种情况恰有一种成立： 都是渐近非负函数。利用记号的基本定义来证明 。 证明： 要使 只要存在正常数 ，当n足够大时： 1. 只要取2. 这里取 故存在正常数 ， ，使n足够大时 轮换对称，假设， 恒成立 成立，故 3.1-2：证明对任意实常数a和b，其中 证明： 要使 。 ，有 取1. ，则当 时 在在 故存在正常数2. 中取中取 使 ，即 在在 故存在正常数 中取中取 使 ，即 3.1-3：解释为什么“算法A的运行时间至少是”这句话是无意义的。 大于等于渐近上界就不是这个算法的合理运行时间了，所以是无意义的。 3.1-4： 1. 2. 不存在正常数c使上式成立。 成立吗？ ，取 成立吗？ 3.1-5：证明定理3.1 证明： 条件一：存在正常数，使 3.1-6：证明：一个算法的运行时间是且最佳情况运行时间是见定理3.1 3.1-7：证明 是空集。 。 当且仅当其最坏情况运行时间是， 简单的说明如下（可以用基本定义进行严格证明）：一个是非渐近紧确的上界而另一个是非渐近紧确的下界，其交集显然是空集。 3.1-8：可以将我们的表示法扩展到有两个参数n和m的情形，其中n和m的值可以以不同的速率，互相独立地趋于无穷。对给定的函数集 存在正整数。 给出对应的 和 的定义。 和 ，使对所有 或 ，有 和 ，使对所有 ， 或 为函数 ，有 存在正整数。 存在正整数 。 下取整：上取整： 和，使对所有或，有 其中： 多重对数函数： 婓波那契数： ， ， 性质：第i个斐波那契数等于和 我总结的一些关系： 1.2.3.4.5.6. 最接近的整数。所以斐波那契数以指数形式增长。 是单调递增的函数，则是非负的，那么 和 也是单调递增的。 也是单调递 证明： 时，1.2. 故3.故 是单调递增函数。 是单调递增函数且是单调递增函数。 ， ，故 是单调递增函数。 3.2-2：证明等式（3.15）。 1.2.3. 3.2-3：证明等式（3.18）。并证明证明： 1.2.3.a. 对于足够大的n，一定有，对数函数是单调递增函数，所以取 。 和 。 取，当时： 取 故存在正常数 ，当 时， 。 3.2-4：函数多项式有界条件利用 是否是多项式有界？函数呢？ 所以该多项式不是多项式有界的。 假设（i个2） ， 更大些。 所以在渐近上 3.2-6：用归纳法证明：第i个斐波那契数满足等式 其中是黄金分割律，是共轭数。 证明： 1. 当i=1， 2. 假设i=k-2时， i=k-1时， 则当n=k时，有 3.2-7：证明：对于证明： ，第 个斐波那契数满足 。 显然成立。故有【思考题】 3-1：多项式的渐近性质 设 。 为一个n的d次多项式，其中，令k为一个常数。利用渐近 a：b：c：d：e：f： ,, ,, ,, 函数是周期性变换大小的。因此具有不确定性。A、B关系不定。 , ，显然当取 时有 成立， , , , 3-3：根据渐近增长率排序 a) 根据增长率来对下列函数排序，即找出函数的一种排列 。将该序列划分成等价类，使 同一个等价类中当且仅当 。 b) 给出非负函数 的一个例子，使对任何在（a）中的 ， 既不是 也 ，使 和 在 a:略 b: 3-4：渐近记号的性质 设a)b)c) 的n成立。 d)e)f)g)h) 3-5：和的一些变形 某些作者定义的方式和我们略有不同，可以用（读作“无穷大”）来表示这种定义。若存在正常数c使a） 说明渐近非负的两个函数 对无穷多的整数n成立，则说和 ，要么 ，要么 。 ，其中 且 对足够大 和 为渐近正函数。证明或否定以下的假设： ，要么二者都成立，然后再用代替时并不成立。 b） 请描述用代替以刻画程序运行时间的潜在优点和缺点。 某些作者定义的也略有不同，设为。称 。 c） 如果我们用代替而仍然使用，定理3.1的“当且仅当”的两个方向各有 当且仅当 14 什么变化？ 某些作者定义的表示略去了对数因子的 存在正常数c，k 和使得 成立 d） 请类似的定义和，并证明与定理3.1的类似关系。 ，对所有 15 转载请保留出处，http://www./doc/97daa00203d8ce2f00662356.html |
|
|
