大O复杂度递归Vs迭代

Question

关于Determining complexity for recursive functions (Big O notation)的问题5是：

int recursiveFun(int n)
{
    for(i=0; i<n; i+=2)
        // Do something.

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun(n-5);
}

为了突出我的问题，我将递归参数从n-5更改为n-2

int recursiveFun(int n)
{
    for(i=0; i<n; i+=2)
        // Do something.

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun(n-2);
}

我理解循环在n/2中运行，因为标准循环在n中运行，我们迭代了一半的次数。

但是，递归调用也会发生同样的情况吗？对于每个递归调用，n减少2。如果n为10，调用堆栈为：

recursiveFun(8)
recursiveFun(6)
recursiveFun(4)
recursiveFun(2)
recursiveFun(0)

...which是5个调用(即10/2或n/2)。然而，Michael_19提供的答案表明，它运行在n-5中，在我的示例中是n-2。显然，n/2与n-2不一样。我哪里出错了，为什么递归与迭代在分析Big-O时有所不同？

Answer 1

分析递归算法大O的常用方法是找到一个递归公式，该公式“计数”该算法所做的操作数。它通常表示为T(n)。

在您的示例中:这个代码的时间复杂度可以用公式来描述：

T(n) = C*n/2                                   +    T(n-2)
       ^                                              ^
    assuming "do something is constant        Recursive call

由于它显然将在O(n^2)中进行，所以让我们使用归纳法向Omega(n^2)展示：

归纳假说：

T(k) >= C/8 *k^2  for 0 <= k < n

事实上：

T(n) = C*n/2 + T(n-2) >= (i.h.) C*n/2 + C*(n-2)^2 / 8
     = C* n/2 + C/8(n^2 - 4n + 2) =
     = C/8 (4n + n^2 - 4n + 2) =
     = C/8 *(n^2 + 2)

事实上：

T(n) >= C/8 * (n^2 + 2) > C/8 * n^2

因此，T(n)在big-Omega(n^2)中。

显示大-O也是类似的：

假设：T(k) <= C*k^2适用于所有2 <= k < n

T(n) = C*n/2 + T(n-2) <= (i.h.) C*n/2 + C*(n^2 - 4n + 4) 
     = C* (2n + n^2 - 4n + 4) = C (n^2 -2n + 4)

对于所有的n >= 2，-2n + 4 <= 0，所以对于任何n>=2

T(n) <= C (n^2 - 2n + 4) <= C^n^2

根据大O的定义，T(n)是O(n^2)。

由于我们已经证明了T(n)是O(n^2)和Omega(n^2)，所以它也是在Theta(n^2)中。

分析递归不同于分析迭代，因为：

1. n (和其他局部变量)每次更改，可能很难捕捉到这种行为。
2. 当有多个递归调用时，事情会变得更加复杂。