在解决复发问题时,地板和天花板何时起作用？

Question

在遇到复发时,我遇到了忽略地板和天花板的地方.

CLRS (第4章,第83页)的例子,其中忽略了最低限度:

这里(第2 页,练习4.1-1)是一个忽略上限的例子:( 编辑:我从公众舆论中得知这有点可疑.)

事实上,在CLRS(第88页)中,它提到:

"解决复发问题时,地板和天花板通常无关紧要"

我的问题:

1. 这里"通常"是指所有情况？如果是的话,我可以一直忘记它们.
2. 如果没有,那么在解决复发问题时,地板和天花板何时真正算在内？

注意:这不是作业问题.当我刷新DS和算法时,我想到了这一点.

Answer 1

楼层和天花板功能满足所有x的以下不等式:

• X -1 <⌊ X ⌋≤ X

• X ≤⌈ X ⌉< X 1

因此,在第一个例子中,我们有⌊ ñ /2⌋≤ ñ/2.此外,因为对数是单调递增函数,我们知道,LG的⌊ ñ /2⌋≤LG(ñ/2).将这些一起,我们得到第一不等式2(ç ⌊ ñ /2⌋LG⌊ Ñ /2⌋)+ ñ ≤ CN LG(ñ/2)+ Ñ.

第二个例子实际上包含一个错误:Ç LG⌈ ñ /2⌉+ 1是从不小于但可以等于Ç LG(ñ/2)+ 1.然而,它是真的,Ç LG⌈ ñ /2⌉+ 1≤ ç LG(ñ/2 + 1)+ 1,我们可以然后从上面的约束,也就是说,ç LG(ñ/2)+ 2(假设ñ ≥2),并因此获得期望的结论,即Ť(ñ)∈ ø(LG ñ).

实际上,第二个例子也包含其他错误:即使使用以下段落中所述的假设(您没有引用),last =符号也应该是≤.

(Ps.Phew,如果没有LaTeX,这是一种真正的痛苦.如果没有其他的话,那就是为什么像math.SE这样的问题更好的问题.)

Answer 2

您的两个示例都可以通过主定理进行分析.所述Akra-Bazzi定理概括了主定理,并给出了当小扰动可以忽略的一个充分条件(扰动H(x)是O(X /日志² X)).对于Akra-Bazzi可分析的整数索引重复,您可以始终忽略地板和天花板,因为它们的扰动最多为1.

在算法和数据结构的背景下,Akra-Bazzi未涵盖的每一次重复都是非常奇特的.