《算法导论》第三章-思考题（参考答案）
（多项式的渐进行为） 假设 是一个关于 的 次多项式，其中 ， 是一个常量。使用渐进符号的定义来证明下面的性质。
a. 若 ，则 。
b. 若 ，则 。
c. 若 ，则 。
d. 若 ，则 。
e. 若 ，则 。
已知： ，易得 。
故 。
情况 1：
，即： 。
故 。
情况 2：
，即： 。
故 。
情况 3：
，即： 。
故 。
情况 4：
，即： 。
故 。
情况 5：
，即： 。
故 。
（相对渐进增长） 为下表中的每对表达式 指出 是否是 的 或 。假设 且 均为常量。回答应以表格的形式，将“是”或“否”写在每个空格中。
a.
令 代替 ，并令 代替 a，可得：
即： 。
又：若 。故： 。
b.
故， 。
令 。故 。
c.
。又 的值为在区间 中波动，故 与 无任何关系
d.
严格递增，故对于任意正常量 ，总存在 ，使得 ，即：
也易证：故对于任意正常量 ，总存在 ，使得 ，即：
e.
。故 。
f.
故，
又， 是严格递增的函数。故，
故， ，也即
也即
（根据渐进增长率排序）
a. 根据增长的阶来排序下面的函数，即求出满足 的函数的一种排列 。把你的表划分成等价类，使得函数 和 在相同类中当且仅当 。
b.给出非负函数 的一个例子，使得对所有在（a）部分中的函数 ， 既不是 也不是 。
（渐进记号的性质） 假设 和 为渐进正函数。证明或反驳下面的每个猜测。
a. 蕴含 。
错。例如： 。
b. 。
错。例如： 。
c. 蕴含 ，其中对所有足够大的 ，有 且 。
正确。
对于足够大的 ，有 ；且 ，则存在正常量 ，使得 ，有
又 ，故当 ，且 足够大，有：
故原问题成立。
d. 蕴含 。
错。例如： 。
e. 。
当 时， ；其他条件下，不成立。
f. 蕴含 。
正确。 ，即存在正常量 ，使得 ，有
，即
令 ，得 。
g. 。
错。例如： 。
h. 。
正确。
易得， ，即存在正常量 ，使得 ，都有 。
令 ，即存在正常量 ，使得 ，都有 。
令 ，则 ，有 。
即 。
（ 与 的一些变形） 某些作者用一种与我们稍微不同的方式来定义 ；假设我们使用 （读作“ 无穷”）来标识这种可选的定义。若存在正常量 ，使得对无穷多个整数 ，有 ，则称 。
a. 证明：对渐进非负的任意两个函数 和 ，或者 或者 或者二者均成立，然而，如果使用 来代替 ，那么该命题并不为真。
主要缺少了 这个条件；则若 ，必然有无穷多个正整数 ，使得 成立；
若 ，则上述两者均成立；
反例： ，但 。
b. 描述用 代替 来刻画程序运行时间的潜在优点与缺点。
优点： 对下届的要求更宽松，可以兼容更多的情况；
缺点： 并非严格的渐进下界。因此实际意义并不大。
某些作者也用一种稍微不同的方式来定义 ；假设使用 来标识这种可选的定义。我们称 当且仅当 。
c. 如果使用 代替 但仍然使用 ，定理 3.1 中的“当且仅当”的每个方向将出现什么情况？
没有变化。 成立意味着 渐进非负，故 。
有些作者定义 （读作“软 ”）来意指忽略对数因子的 ：
：存在正常量 和 ，使得对所有 ，有 。
d. 用一种类似的方式定义 和 。证明与定理 3.1 相对应的类似结论。
：存在正常量 和 ，使得对所有 ，有 。
：存在正常量 和 ，使得对所有 ，有 。
（多重函数） 我们可以把用于函数 中的多重操作符 * 应用于实数集上的任意单调递增函数 。对给定的常量 ，我们定义多重函数 为
该函数不必再所有情况下都是良定义的。换句话说，值 是为缩小其参数到 或更小所需函数 重复应用的数目。
对如下每个函数 和常量 ，给出 的一个尽量紧确的界。
11111
2024-11-15 广告
