如何为给定的代码段编写递归关系

Question

在我的算法和数据结构中 class 我们得到了一些递归关系来解决或者我们可以看到算法的复杂性。

起初，我认为这些关系的唯一目的是记下递归分而治之算法的复杂性。然后我在麻省理工学院的作业中遇到了一个问题，其中要求为迭代算法提供递归关系。

如果给定一些代码，我自己实际上是如何提出递归关系的？有哪些必要步骤？

我可以记下任何情况，即具有这种关系的最坏、最好、平均情况，这实际上是正确的吗？

谁能举个简单的例子说明一段代码是如何变成递归关系的？

干杯，安德鲁

Answer 1

好的，所以在算法分析中，递归关系是一个函数，将解决大小为n的问题所需的工作量与解决较小问题所需的工作量联系起来（这与其在数学中的含义密切相关）。

例如，考虑下面的斐波那契函数：

Fib(a) 
{
  if(a==1 || a==0)
    return 1;
  return Fib(a-1) + Fib(a-2);
}

这里做了三个操作（比较、比较、加法），也是递归调用自己。所以递归关系是T(n) = 3 + T(n-1) + T(n-2)。要解决这个问题，您可以使用迭代方法：开始扩展项，直到找到模式。对于此示例，您将扩展 T(n-1) 以获得 T(n) = 6 + 2*T(n-2) + T(n-3)。然后展开T(n-2)得到T(n) = 12 + 3*T(n-3) + 2*T(n-4)。再展开一次 T(n-3) 得到 T(n) = 21 + 5*T(n-4) + 3*T(n-5)。请注意，第一个 T 项的系数在斐波那契数列之后，常数项是它们的和乘以三：查找它，即 3*(Fib(n+2)-1)。更重要的是，我们注意到序列呈指数增长；即算法的复杂度为O(2ⁿ).

然后考虑这个函数进行归并排序：

Merge(ary)
{
  ary_start = Merge(ary[0:n/2]);
  ary_end = Merge(ary[n/2:n]);

  return MergeArrays(ary_start, ary_end);
}

此函数在输入的一半上调用自身两次，然后合并两半（使用 O(n) 工作）。即T(n) = T(n/2) + T(n/2) + O(n)。要解决这种类型的递归关系，您应该使用 Master Theorem。根据这个定理，这扩展为 T(n) = O(n log n).

最后，考虑这个函数来计算斐波那契：

Fib2(n)
{
  two = one = 1;
  for(i from 2 to n)
  {
    temp = two + one;
    one = two;
    two = temp;
  }
  return two;
}

这个函数没有调用自己，迭代O(n)次。因此，它的递归关系是T(n) = O(n)。你问的就是这种情况。它是没有递归的递归关系的特例；所以，很容易解决。

Answer 2

要找到算法的运行ning 时间，我们首先需要能够为该算法编写一个表达式，该表达式告诉每个步骤的运行ning 时间。因此，您需要遍历算法的每个步骤才能找到表达式。例如，假设我们定义了一个谓词 isSorted，它将数组 a 和数组的大小 n 作为输入，并且当且仅当数组按递增顺序排序时 return 为真。

bool isSorted(int *a, int n) {
   if (n == 1)
      return true;       // a 1-element array is always sorted
   for (int i = 0; i < n-1; i++) {
      if (a[i] > a[i+1]) // found two adjacent elements out of order
         return false;
   }
   return true;         // everything's in sorted order
}

显然，此处输入的大小将简单地为 n，即数组的大小。对于输入 n，在最坏情况下将执行多少步？

第一个 if 语句算作 1 步

for循环在最坏的情况下会执行n-1次（假设内部测试没有把我们踢出去），循环测试的总时间为n-1，而索引的增量。

循环内部还有一个if语句，每次迭代执行一次，最坏情况下总共执行n−1次。

最后的return会执行一次

所以，在最坏的情况下，我们将完成 1+(n−1)+(n−1)+1

次计算，总共运行次 T(n)≤1+(n−1)+(n−1)+1=2n 因此我们有计时函数 T(n)= O(n).

简而言之，我们所做的是-->>

1.For 一个参数'n'，它给出了输入的大小我们假设每个执行一次的简单语句将花费常数时间，为简单起见，假设一个

2.The 循环和内部主体等迭代语句将花费可变时间，具体取决于输入。它有解决方案 T(n)=O(n)，就像非递归版本一样。

3.So你的任务是一步一步写下n的函数来计算时间复杂度

对于递归算法，你做同样的事情，只是这次你添加每个递归调用所花费的时间，表示为它在输入上花费的时间的函数。例如，让我们将 isSorted 重写为递归算法：

bool isSorted(int *a, int n) {
   if (n == 1)
      return true;
   if (a[n-2] > a[n-1])         // are the last two elements out of order?
      return false;
   else
      return isSorted(a, n-1); // is the initial part of the array sorted?
}

在这种情况下，我们仍然通过算法，计算：第一个 if 的 1 步加上第二个 if 的 1 步，加上时间 isSorted 将采用大小为 n−1 的输入，这将是 T (n−1)，给出递归关系

T(n)≤1+1+T(n−1)=T(n−1)+O(1)

它有解决方案 T(n)=O(n)，就像非递归版本一样。

够简单！！多练习写各种算法的递归关系，记住算法中每个步骤执行的时间

如何为给定的代码段编写递归关系

how to write a recurrence relation for a given piece of code

algorithm

recurrence