algorithm - 线性递归、二元递归与运行时的关系

Question

假设我们有一个需要 n 步的方法，但在最坏的情况下它会线性调用自身 n 次。在这种情况下，大 O 会是 n*n 吗？那么递归调用通常是 n^2 类似于两个 for 循环吗？

现在让我们采用二进制递归算法，例如二进制斐波那契。该算法的 1 次调用需要 n 步，但假设它最多可以重复 n 次。该算法的运行时间会是 2^n 吗？

Answer 1

设f()是一个调用自身 n 次的函数。考虑代表函数的 C 代码f()。

int f(int n)
{
  int i;
  if(n==0)
  {
     printf("\n Recursion Stopped");
  }
  else
  {
     for(i=0;i<=n;i++)
     {
        printf("\n Hello");
     }  
     f(n-1);
  }
} 

对于n = 5，消息Hello将被打印15多次。对于n = 10，消息Hello将被打印55多次。

一般来说，该消息将被打印n*(n+1)/2多次。

因此函数f()的复杂度为O(n ² )。记住f()是一个函数，它具有复杂性n并且f()被递归地称为n时间。如果内部循环包含诸如加法、减法等恒定时间表达式，则此类函数的复杂度等于以下循环顺序。

for(i=0;i<=n;i++)
{
  for(j=i;j<=n;j++)
  {
     /* Some constant time operation */
  }
}

对于 a Binary Recursion，时间复杂度为O(2 ⁿ )。

二进制递归函数调用自身两次。

以下函数g()是二进制递归的示例，（即 a Fibonacci binary recursion）

int g(int n)
{
  int i;
  if(n==0)
  {
     printf("\n Recursion Stopped");
  }
  else
  {
     printf("\n Hello");
     g(n-1);
     g(n-2);
  }
} 

递推关系为g(n) = g(n-1)+g(n-2)，对于n>1。

求解我们得到O(2 ⁿ )的上限。该函数g()也是Θ(φ ⁿ )，其中φ是golden ratio和φ = ((1+ √5)/2)