确定递归函数的复杂度（大 O 表示法）

每个函数的时间复杂度，用大 O 表示法：

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

此函数在到达基本情况之前被递归调用 n 次，因此它的 O(n)，通常称为 linear。

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

这个函数每次调用n-5，所以我们在调用函数之前从n中减去5，但是n-5也是O(n)。 （实际上称为 n/5 次。并且，O(n/5) = O(n) ）。

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

这个函数是以 5 为底的 log(n)，每次我们在调用函数之前除以 5，所以它的 O(log(n))（以 5 为底），通常称为 logarithmic，最常见的是 Big O 表示法和复杂性分析使用基数 2。

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

在这里，它是 O(2^n) 或 指数，因为每个函数调用自己两次，除非它已被递归 n 次。

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

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

这里 for 循环采用 n/2，因为我们增加了 2，递归采用 n/5，并且由于 for 循环是递归调用的，因此，时间复杂度在

(n/5) * (n/2) = n^2/10,

由于渐近行为和最坏情况的考虑或大 O 正在争取的上限，我们只对 O(n^2) 这样的最大项感兴趣。

祝你期中考试好运；）

---

对于 n <= 0 的情况，T(n) = O(1)。因此，时间复杂度将取决于何时 n >= 0。

我们将在下面的部分考虑案例 n >= 0。

1.

T(n) = a + T(n - 1)

其中 a 是某个常数。

通过归纳：

T(n) = n * a + T(0) = n * a + b = O(n)

其中 a, b 是一些常数。

2.

T(n) = a + T(n - 5)

其中 a 是一些常数

通过归纳：

T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n)

其中 a, b 是一些常数，k <= 0

3.

T(n) = a + T(n / 5)

其中 a 是一些常数

通过归纳：

T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n)

其中 a, b 是一些常数

4.

T(n) = a + 2 * T(n - 1)

其中 a 是一些常数

通过归纳：

T(n) = a + 2a + 4a + ... + 2^(n-1) * a + T(0) * 2^n 
     = a * 2^n - a + b * 2^n
     = (a + b) * 2^n - a
     = O(2 ^ n)

其中 a, b 是一些常数。

5.

T(n) = n / 2 + T(n - 5)

其中 n 是某个常数

重写 n = 5q + r，其中 q 和 r 是整数并且 r = 0, 1, 2, 3, 4

T(5q + r) = (5q + r) / 2 + T(5 * (q - 1) + r)

我们有 q = (n - r) / 5，并且因为 r < 5，我们可以认为它是一个常数，所以 q = O(n)

通过归纳：

T(n) = T(5q + r)
     = (5q + r) / 2 + (5 * (q - 1) + r) / 2 + ... + r / 2 +  T(r)
     = 5 / 2 * (q + (q - 1) + ... + 1) +  1 / 2 * (q + 1) * r + T(r)
     = 5 / 4 * (q + 1) * q + 1 / 2 * (q + 1) * r + T(r)
     = 5 / 4 * q^2 + 5 / 4 * q + 1 / 2 * q * r + 1 / 2 * r + T(r)

由于 r < 4，我们可以找到一些常数b使得b >= T(r)

T(n) = T(5q + r)
     = 5 / 2 * q^2 + (5 / 4 + 1 / 2 * r) * q + 1 / 2 * r + b
     = 5 / 2 * O(n ^ 2) + (5 / 4 + 1 / 2 * r) * O(n) + 1 / 2 * r + b
     = O(n ^ 2)

---

我发现近似递归算法复杂性的最佳方法之一是绘制递归树。一旦你有了递归树：

Complexity = length of tree from root node to leaf node * number of leaf nodes

第一个函数的长度为 n，叶节点数为 1，因此复杂度为 n*1 = n 第二个函数的长度为 n/5，叶节点数再次为 1，因此复杂度为 n/5 * 1 = n/5。它应该近似为 n 对于第三个函数，由于 n 在每次递归调用时都被 5 除，递归树的长度将为 log(n)(base 5)，叶节点的数量再次为 1，因此复杂度将为 log (n)(base 5) * 1 = log(n)(base 5) 对于第四个函数，因为每个节点都有两个子节点，所以叶节点的数量将等于 (2^n) 和递归的长度树将为 n，因此复杂度将为 (2^n) * n。但是由于n在(2^n)前面是微不足道的，所以可以忽略不计，复杂度只能说是(2^n)。对于第五个功能，有两个元素引入了复杂性。函数的递归性质引入的复杂性以及每个函数中 for 循环引入的复杂性。进行上述计算，函数的递归性质引入的复杂度将是 ~ n 和由于 for 循环 n 引起的复杂度。总复杂度为 n*n。

注意：这是一种计算复杂度的快速而肮脏的方法（不是官方的！）。很想听听对此的反馈。谢谢。

---

我们可以在数学上证明这一点，这是我在上述答案中所缺少的。

它可以极大地帮助您了解如何计算任何方法。我建议从上到下阅读它以完全理解如何做到这一点：

T(n) = T(n-1) + 1 这意味着该方法完成所需的时间等于相同的方法，但 n-1 为 T(n-1)，我们现在添加 + 1因为这是完成一般操作所需的时间（T(n-1) 除外）。现在，我们将找到 T(n-1) 如下：T(n-1) = T(n-1-1) + 1。看起来我们现在可以形成一个可以给我们某种形式的函数重复，这样我们才能完全理解。我们将 T(n-1) = ... 的右边而不是 T(n-1) 放在方法 T(n) = ... 中，这将给我们： T(n) = T(n- 1-1) + 1 + 1 即 T(n) = T(n-2) + 2 或者换句话说，我们需要找到我们丢失的 k：T(n) = T(nk) + k。下一步是取 nk 并声明 nk = 1，因为在递归结束时，当 n<=0 时，它将恰好花费 O(1)。从这个简单的等式，我们现在知道 k = n - 1。让我们将 k 放在我们的最终方法中： T(n) = T(nk) + k 这将给我们： T(n) = 1 + n - 1 这是正好是 n 或 O(n)。与 1 相同。您可以自己测试一下，看看是否得到 O(n)。 T(n) = T(n/5) + 1 和以前一样，此方法完成的时间等于相同方法但 n/5 的时间，这就是它受限于 T(n/5) 的原因。让我们像 1 一样找到 T(n/5)：T(n/5) = T(n/5/5) + 1，即 T(n/5) = T(n/5^2) + 1。让我们将 T(n/5) 放在 T(n) 中以进行最终计算：T(n) = T(n/5^k) + k。再次和以前一样，n/5^k = 1，即 n = 5^k，就像问 5 的幂一样，会给我们 n，答案是 log5n = k（以 5 为底的对数）。让我们将我们的发现放在 T(n) = T(n/5^k) + k 中，如下所示： T(n) = 1 + logn 即 O(logn) T(n) = 2T(n-1) + 1我们这里的内容与以前基本相同，但这次我们递归调用该方法 2 次，因此我们将其乘以 2。让我们找到 T(n-1) = 2T(n-1-1) + 1，即 T (n-1) = 2T(n-2) + 1。我们的下一个位置和以前一样，让我们放置我们的发现： T(n) = 2(2T(n-2)) + 1 + 1 即 T(n) = 2^2T(n-2) + 2 得到 T(n) = 2^kT(nk) + k。让我们通过声明 nk = 1 来找到 k，即 k = n - 1。让我们将 k 放置如下： T(n) = 2^(n-1) + n - 1 大致为 O(2^n) T( n) = T(n-5) + n + 1 几乎与 4 相同，但现在我们添加 n，因为我们有一个 for 循环。让我们找到 T(n-5) = T(n-5-5) + n + 1，即 T(n-5) = T(n - 2*5) + n + 1。让我们把它放在：T(n ) = T(n-2*5) + n + n + 1 + 1) 即 T(n) = T(n-2*5) + 2n + 2) 并且对于 k：T(n) = T (nk*5) + kn + k) 再次：n-5k = 1，即 n = 5k + 1，大致为 n = k。这将给我们：T(n) = T(0) + n^2 + n，大致为 O(n^2)。

我现在建议阅读其余的答案，这些答案会给你一个更好的视角。祝你好运赢得那些大 O :)

---

这里的关键是可视化调用树。一旦这样做，复杂性是：

nodes of the call tree * complexity of other code in the function

后一项的计算方式与我们对正常迭代函数的计算方式相同。

相反，完整树的总节点计算为

                  C^L - 1
                  -------  , when C>1
               /   C - 1
              /
 # of nodes =
              \    
               \ 
                  L        , when C=1 (this is special case of a single branch tree)

其中 C 是每个节点的子节点数，L 是树的级别数（包括根）。

可视化树很容易。从第一次调用（根节点）开始，然后绘制与函数中递归调用数相同的子节点数。将传递给子调用的参数写为“节点的值”也很有用。

因此，这里是上述示例的结果：

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

首先考虑调用树：

n 级 1 n-1 级 2 n-2 级 3 n-3 级 4 ... ~ n 级 -> L = n

这里每个节点的子节点数为 C = 1，层数 L = n+1。其余函数的复杂度为 O(1)。因此总复杂度为 L * O(1) = (n+1) * O(1) = O(n)

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

这里的调用树是：

n n-5 n-10 n-15 ... ~ n/5 级 -> L = n/5

同样 C = 1，但 L = n/5。其余函数的复杂度为 O(1)。因此总复杂度为 L * O(1) = (n/5) * O(1) = O(n)

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

调用树是：

nn/5 n/5^2 n/5^3 ... ~ log5(n) 级别 -> L = log5(n)

因此 C = 1，L = log(n)。其余函数的复杂度为 O(1)。因此总复杂度为 L * O(1) = log5(n) * O(1) = O(log(n))

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

在这里，调用树更复杂：

n 1级 n-1 n-1 2级 n-2 n-2 n-2 n-2 ... n-3 n-3 n-3 n-3 n-3 n-3 n-3 n-3 ... ... ~ n 级 -> L = n

这里每个节点的子节点数是 C = 2，而 L = n。其余函数的复杂度为 O(1)。这次我们使用调用树中节点数的完整公式，因为 C > 1。因此总复杂度为 (C^L-1)/(C-1) * O(1) = (2^n - 1 ) * O(1) = O(2^n)。

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

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

同样，调用树是：

n n-5 n-10 n-15 ... ~ n/5 级 -> L = n/5

这里 C = 1，L = n/5。其余函数的复杂度为 O(n)。因此总复杂度为 L * O(1) = (n/5) * O(n) = O(n^2)

---

我看到对于接受的答案（recursivefn5），有些人对解释有疑问。所以我会尽我所能澄清。

for 循环运行 n/2 次，因为在每次迭代中，我们将 i（计数器）增加 2 倍。所以说 n = 10，for 循环将运行 10/2 = 5 次，即当 i 为 0 ,2,4,6 和 8。同样，递归调用每被调用一次就会减少 5 倍，即运行 n/5 次。再次假设 n = 10，递归调用运行 10/5 = 2 次，即当 n 为 10 和 5 时，它遇到基本情况并终止。计算总运行时间，每次调用递归函数时，for 循环都会运行 n/2 次。由于递归 fxn 运行 n/5 次（在上面的 2 中），for 循环运行 (n/2) * (n/5) = (n^2)/10 次，这转换为整体 Big O 运行时间O(n^2) - 忽略常数 (1/10)...

---