求解递归方程 T(n) = 3 + m * T(n - m)

Question

我明天有一个计算机科学期中考试，我需要帮助确定特定递归函数的复杂性，如下所示，这比我已经做过的东西要复杂得多：它有两个变量

T(n( = 3 + mT(n-m(

在 m 是常数的简单情况下，可以通过编写解包关系来轻松获得公式;然而，在这种情况下，解包不会让生活更轻松，如下所示(假设 T(0( = c(：

T(n( = 3 + mT(n-m(

T(n-1( = 3 + mT(n-m-1(

T(n-2( = 3 + mT(n-m-2(

。

显然，根据这些不平等，没有直接的消除。所以，我想知道我是否应该在这种情况下使用另一种技术。

Answer 1

不用担心m - 这只是一个常量参数。但是，您错误地展开了递归。展开的每个步骤都涉及三个操作：

1. 取 T 的值与参数值
，这m
2. 将其乘以m
3. 添加常量3

所以，它看起来像这样：

T(n) = m * T(n - m) + 3 =                                        (Step 1)
     = m * (m * T(n - 2*m) + 3) + 3 =                            (Step 2)
     = m * (m * (m * T(n - 3*m) + 3) + 3) + 3 = ...              (Step 3)

等等。展开T(n)至步骤 k 将通过以下公式给出：

T(n) = m^k * T(n - k*m) + 3 * (1 + m + m^2 + m^3 + ... + m^(k-1))

现在，您将n - k*m = 0设置为使用初始条件T(0)并获得：

k = n / m

现在你需要使用一个公式来计算几何级数的总和 - 最后你会得到一个T(n)的封闭公式(我把最后一步留给你(。