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

Question

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

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

考虑到一些代码,我怎么能真正想出一个递归关系呢？有什么必要的步骤？

我是否可以记下任何情况,即最坏的,最好的,具有这种关系的平均情况,这是否正确？

有可能有人给出一个代码如何变成递归关系的简单例子吗？

干杯,安德鲁

Answer 1

好的,因此在算法分析中,递归关系是将解决大小n问题所需的工作量与解决较小问题所需的工作量相关联的函数(这与其在数学中的含义密切相关).

例如,考虑下面的Fibonacci函数:

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项的系数跟随Fibonacci数,而常数项是它们之和乘以三:查找它,即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).要解决此类型的递归关系,您应该使用主定理.通过这个定理,这扩展到了T(n) = O(n log n).

最后,考虑这个函数来计算Fibonacci:

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

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

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 次。

最后一次返回将执行一次。

所以，在最坏的情况下，我们会做 1+(n?1)+(n?1)+1

计算，对于总运行时间 T(n)?1+(n?1)+(n?1)+1=2n，所以我们有计时函数 T(n)=O(n)。

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

1.对于给出输入大小的参数“n”，我们假设每个简单语句执行一次将花费恒定时间，为简单起见，假设一个

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

3.所以你的任务是一步一步地写下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)，就像非递归版本一样，因为它发生了。

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