算法 : Recurrence relations from CLRS

Question

我最近试图通过 CLRS 求解一些递归关系，并且在求解这些方程时我注意到了一个奇怪的细微差别。我不知道你们中的任何人是否注意到它，或者理论冠军可以对此进行更多说明。 (我也拥有计算机科学学位，但没有理论学位!)。在求解主定理的递归时:

T(n) = 一个 T(n/b) + f(n)

我注意到推理是这样的:

i) 扩展 a-ary 递归树，我们得到 a^{log_b n} 叶节点，其中每个节点完成的工作是 Θ(1)，给出 Θ( n^{log_b a}) 所有叶节点

ii) 对于所有非叶节点，g(n) = Σ a^j f(b/n^j) 其中 j 从 0 到 floor (log _b n - 1)，其中树的高度为 log_b n

iii) 现在大胆尝试:声明 f(n) 对于某些 ε 确实受 O(n^{log_b a} - ε) 的限制> 0

iv) 现在根据 f(n) 求解 g(n) 并根据 g(n) 求解 T(n)。正如在步骤 i 中提到的，T(n) 实际上是 Θ(n^{log_b a}) + g(n)，所以一旦你有一些 g(n) 结合提出 T(n) 的另一个术语

我在使用这种方法时遇到的问题是，这里的推理是这样的:看，如果我们假设右侧为 X，那么我们将其代入方程式以求解左侧。这个推理是不是有点离奇？是不是像这样:

给定:X² = 8X - 16

所以让我们假设 X=4 并将其放入 RHS 中并求解 X，很酷，看，我们得到了 4!!!这绝对很有趣，但您是否真正解决了问题 - 为什么您不猜测 X 是无理数，为什么不是虚数？

此外，我实际上想知道这种推理存在于数学的哪个分支中，因为我怀疑它已经从该领域进入 CS。任何想法？我知道 CS 中几乎 99% 的数学只是“在某些假设下的一些更奇特的论证形式”(因为 CS 专业不解决传统意义上的方程式)，但这种方法看起来仍然非常独特。有什么想法吗？

Answer 1

有趣的跳跃式步骤是数学归纳的捷径。基本上，它是这样的:

• 检查假设是否适用于某些基本情况(例如只有一个非叶节点)。
• 鉴于第 n 个非基本情况为真，请确保第 n+1 个非基本情况为真。

您通常可以通过假设您想要证明的是真实的、插入它并证明它有效来简化此过程。在这个特定实例中是否属于这种情况，我不太清楚。

解决这类问题通常会涉及一些灵感，因为您必须为递归选择正确的形式才能使归纳步骤起作用，但这通常不是凭空挑选东西;在这种情况下，它是从仔细检查叶节点与其他节点之间的关系而产生的非常厚的空气中挑选东西。