我发现的估算递归算法复杂度的最好方法之一是画递归树。一旦你有了递归树:

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

The first function will have length of n and number of leaf node 1 so complexity will be n*1 = n The second function will have the length of n/5 and number of leaf nodes again 1 so complexity will be n/5 * 1 = n/5. It should be approximated to n For the third function, since n is being divided by 5 on every recursive call, length of recursive tree will be log(n)(base 5), and number of leaf nodes again 1 so complexity will be log(n)(base 5) * 1 = log(n)(base 5) For the fourth function since every node will have two child nodes, the number of leaf nodes will be equal to (2^n) and length of the recursive tree will be n so complexity will be (2^n) * n. But since n is insignificant in front of (2^n), it can be ignored and complexity can be only said to be (2^n). For the fifth function, there are two elements introducing the complexity. Complexity introduced by recursive nature of function and complexity introduced by for loop in each function. Doing the above calculation, the complexity introduced by recursive nature of function will be ~ n and complexity due to for loop n. Total complexity will be n*n.

注意:这是一种计算复杂度的快速且不规范的方法(不是官方的!)很乐意听到这方面的反馈。谢谢。

我看到对于公认的答案(recursivefn5)，有些人对解释有问题。所以我要尽我所能来澄清一下

The for loop runs for n/2 times because at each iteration, we are increasing i (the counter) by a factor of 2. so say n = 10, the for loop will run 10/2 = 5 times i.e when i is 0,2,4,6 and 8 respectively. In the same regard, the recursive call is reduced by a factor of 5 for every time it is called i.e it runs for n/5 times. Again assume n = 10, the recursive call runs for 10/5 = 2 times i.e when n is 10 and 5 and then it hits the base case and terminates. Calculating the total run time, the for loop runs n/2 times for every time we call the recursive function. since the recursive fxn runs n/5 times (in 2 above),the for loop runs for (n/2) * (n/5) = (n^2)/10 times, which translates to an overall Big O runtime of O(n^2) - ignoring the constant (1/10)...

对于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)

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

---

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

这个函数在到达基本情况之前被递归调用n次，所以它的O(n)通常被称为线性的。

---

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);
}

这个函数是log(n)以5为底，每次除以5 在调用函数之前，它的O(log(n))(以5为底)，通常称为对数，最常见的是大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²)

---

祝你们期中考试好运!)

我发现的估算递归算法复杂度的最好方法之一是画递归树。一旦你有了递归树:

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

The first function will have length of n and number of leaf node 1 so complexity will be n*1 = n The second function will have the length of n/5 and number of leaf nodes again 1 so complexity will be n/5 * 1 = n/5. It should be approximated to n For the third function, since n is being divided by 5 on every recursive call, length of recursive tree will be log(n)(base 5), and number of leaf nodes again 1 so complexity will be log(n)(base 5) * 1 = log(n)(base 5) For the fourth function since every node will have two child nodes, the number of leaf nodes will be equal to (2^n) and length of the recursive tree will be n so complexity will be (2^n) * n. But since n is insignificant in front of (2^n), it can be ignored and complexity can be only said to be (2^n). For the fifth function, there are two elements introducing the complexity. Complexity introduced by recursive nature of function and complexity introduced by for loop in each function. Doing the above calculation, the complexity introduced by recursive nature of function will be ~ n and complexity due to for loop n. Total complexity will be n*n.

注意:这是一种计算复杂度的快速且不规范的方法(不是官方的!)很乐意听到这方面的反馈。谢谢。

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

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 level 2 N-2 level 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-10 c15 ．.． ~ 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);
}

调用树为:

n n / 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 level 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-3… …~ n级-> L = n

其中每个节点的子节点数为C = 2，而L = n。其余函数的复杂度为O(1)。 这一次我们使用调用树中节点数的完整公式，因为C > 1。因此总复杂性(C ^ l - 1) /(颈- 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-10 c15 ．.． ~ n/5级-> L = n/5

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