algorithm - 开发算法的递归关系

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。如果，比如说，递归调用是在 for 循环内而不是在循环外。