分而治之算法的递归公式 - 错误？

Question

我目前正在研究分而治之算法的递归（CLRS 第 4 章），并且我正在努力理解对本书最新（第 4 版）版本所做的细微更改。

递归关系定义为

T(n) = a*T(n/b) + f(n)

，可解析为：

T(n) = Θ(n^log(a, b) + ∑j=0→log(n,b): a^j * f(n/b^j)

CLRS 章节。 4 递归树解决方案

在本书的前一版本和我在网上看到的很多地方，Σ 的限制是

log(n,b)-1

，这是有道理的，因为您只包括除最后一个级别之外的每个级别的组合成本

f(n)

。 但现在总和只是

log(n,b)

，考虑到

j

从 0 开始并以

log(n,b)

结束，意味着

f(n)

包含在包括叶子在内的所有级别中。 树的高度的定义也更改为

log(n,b) + 1

（包括根），而以前只是

log(n,b)

。

有人可以解释为什么要进行这些更改吗？我一定是误会了什么。

例如，对于只有 2 个元素且递归定义为

 T(1) = c1 and T(n) = 2T(n/2) + n(c2)

的二叉树，其中

c1

和

c2

是常量，我得到

T(2) = 2(c1) + 2(c2)

。 如果我使用解决方案公式，我会得到

T(2) = 2(c1) + 4(c2)

，因为有额外的总和，因此数学不匹配。

这里展示我的作品

Answer 1

TLDR

有人可以解释为什么要进行这些更改吗？我一定是误会了什么。

进行这些更改是为了反映程序化^*的一致性，即如果您的输入大小n是奇数并且除法因子b是偶数，则您的递归程序可能不会一致地输入基本情况（对于每种可能的情况）奇数输入大小）通过指定条件：

if n == 1

；由于浮点运算。然而，使用 floor 函数可以解决这个问题。

_{* 尽管如此，CLRS 是一本计算机科学书籍，而不是一本核心数学书籍。因此，在研究书中提供的示例时，人们应该保持编程的心理背景（除了数学背景之外）。}

---

详细说明

定义了递归关系 ，可解析为：

通过“解决到[...]”，我希望您指的是这样一个事实：原始递归的bounds（即渐近复杂性）对应于所述分辨率，而不是宣告递归的值相当于分辨率的值，因为后者是不准确的。

其次，正如评论中指出的，总和限制改为而不是。因此，从逻辑上讲，将递归树的高度声明为 是有利的，因为分辨率的 LHS 只处理树的最后一级（叶子），而 RHS 则负责所有其他级别 - 仅相距一步。

最后：

例如，对于只有 2 个元素的二叉树，其递归定义为：

其中 是常数，我得到 。 如果我使用解决方案公式，我会得到 ，因为有额外的总和，因此数学不匹配。

请理解，您所说的“解决方案”是：（1）一个用于确定递归关系界限的临时框架，作为前面引理的证明（特别是 CLRS 第 4 版的引理 4.2） ., p.108）在相关书籍部分，而不是对该形式的所有重复出现的明确的全能解决方案（精确的价值评估）； (2) 主定理的先例，如果您现在已经了解了，它会告诉您什么样的递归可以可接受地确定其界限。

因此，您不能简单地将值插入临时框架，其唯一目的是确定“二叉树”循环的准确评估输出，就像您似乎在此处所做的那样。为了确定这个新递归的边界，你应该简单地遵循作者提出的框架，即树方法。

---

这里有一个使用 回代法 的解决方案（树法留作练习以强化你的理解；你的答案必须与此相同）。

鉴于 并具有上述条件：

在某个时刻（基本情况），意味着

将这些值代入，我们得到：

递归的界限就是 。