开发算法的递归关系

Question

我在开发算法的递归关系时遇到困难。这是我给出的算法：

int result = silly (n);
public static int silly (int n)
{
if (n <= 1)
  {
   return -100;
  }
int sum = 0;
for (int i = 0; i < n; i++)
  {
  sum += i;
  }
return sum + silly (n-2);
} 

我知道基本情况是 T(1) = 1，但不明白T(n)是什么。会不会

T(n) = n[T(n-2) + 1]

Answer 1

您非常接近正确的复发，但您的复发有点不对。

通常来说，递归关系将完成的工作分为两部分：

• 在 一次递归调用中完成的工作，并且
• 由于触发新的递归调用而完成的工作。

那么让我们看看这个函数的作用。由于 for 循环很大，您认为在一次调用中完成的工作是 O(n) 是正确的。所以这意味着我们会有类似

的东西

T(n) = ________ + O(n)

您填写空白的位对应于由单个函数触发的递归调用。在这种情况下，每个函数调用都会触发一个额外的递归调用，其输入大小为 n - 2，因此递归将是

T(n) = T(n - 2) + O(n)

你想出的答案本质上是

T(n) = nT(n - 2) + O(n)

这很接近，但高估了最终进行的递归调用的数量。将 nT(n - 2) 写为递归的一部分意味着有 n 个不同的递归调用 来自单个调用 ，每个调用的大小为 n - 2。这就是你的d 得到，比如说，递归调用是在 for 循环内而不是在循环外。