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

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)。你问的就是这种情况。它是没有递归的递归关系的特例；因此，它很容易解决。