algorithm - 形成递推关系

Question

我有一个关于形成递归关系和计算时间复杂度的问题。

如果我们有一个递归关系 T(n)=2T(n/2) + c 那么这意味着恒定的工作量 c 分为两部分 T(n/2) + T(n/2)在绘制递归树时。

现在考虑阶乘的递归关系，即 T(n)=n*T(n-1) + c 。如果我们按照上面的方法那么我们应该将工作c分成n个实例每个T(n-1)然后评估时间复杂度。但是，如果以这种方式计算，则答案将为 O(n^n)，因为我们将进行 O(n^n) 次递归调用，这是错误的。

所以我的问题是为什么我们不能使用与第一种情况相同的方法将元素划分为子部分。

Answer 1

令递归关系为 T(n) = a * T(n/b) + O(n)。

这种递归意味着有一个递归函数:

• 将原问题分解成一个个子问题
• 如果当前问题大小为 n，则每个子问题的大小将为 n/b
• 当子问题很简单(太容易解决)时，不需要递归，直接解决(这个过程将花费 O(n) 时间)。

当我们说原问题被分解成a个子问题时，是指函数体中有a个递归调用。

因此，例如，如果函数是:

int f(int n)
{
    if(n <= 1)
        return n;
    return f(n-1) + f(n-2);
}

我们说问题(大小为 n)分为 2 个子问题，大小为 n-1 和 n-2。递归关系为 T(n) = T(n-1) + T(n-2) + c。这是因为有 2 个递归调用，并且参数不同。

但是，如果函数是这样的:

int f(int n)
{
    if(n <= 2)
        return n;
    return n * f(n-1); 
}

我们说问题(大小为 n)仅分为 1 个子问题，大小为 n-1。这是因为只有 1 次递归调用。

因此，递归关系为 T(n) = T(n-1) + c。

如果我们将 T(n-1) 与 n 相乘，这看起来很正常，我们表示有 n 递归调用。

请记住，我们形成递归关系的主要动机是对递归函数执行(渐近)复杂度分析。尽管看起来 n 不能从关系中丢弃，因为它取决于输入大小，但它的作用与它在函数本身中的作用不同。

但是，如果您谈论的是函数的返回值，则为f(n) = n * f(n-1)。在这里，我们乘以 n 因为它是一个实际值，将在计算中使用。

现在，来到 T(n) = T(n-1) + c 中的 c；它只是表明，当我们解决大小为 n 的问题时，我们需要解决大小为 n-1 和其他一些常量 的较小问题> 还执行(恒定时间)比较、乘法和返回值等工作。

我们永远不能将“恒定工作量 c”分成两部分 T(n/2) 和 T(n/2)，甚至使用递归树方法。事实上，我们将问题分成两半。在递归树的每一层中，每次递归调用都需要相同的“c”工作量。

如果存在像 T(n) = 2T(n/2) + O(n) 这样的递归关系，其中要完成的工作量取决于输入大小，那么正如您所描述的，每个级别要完成的工作量将在下一个级别减半。

但是，如果递归关系是 T(n) = T(n-1) + O(n)，我们就不会在接下来的工作中将工作量分成两半递归级别。我们只是在每个连续级别上将工作量减少一个(n 大小的问题在下一级别变为 n-1)。

要检查工作量如何随着递归而变化，请将替换方法应用于您的递归关系。

希望我已经回答了你的问题。