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

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²)

每个函数的时间复杂度，用大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²)

---

祝你们期中考试好运!)

我看到对于公认的答案(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)...

我们可以用数学证明，这是我在上面的答案中所遗漏的。

它可以极大地帮助你理解如何计算任何方法。 我建议你从头到尾通读一遍，以充分理解如何做到这一点:

T(n) = T(n-1) + 1 It means that the time it takes for the method to finish is equal to the same method but with n-1 which is T(n-1) and we now add + 1 because it's the time it takes for the general operations to be completed (except T(n-1)). Now, we are going to find T(n-1) as follow: T(n-1) = T(n-1-1) + 1. It looks like we can now form a function that can give us some sort of repetition so we can fully understand. We will place the right side of T(n-1) = ... instead of T(n-1) inside the method T(n) = ... which will give us: T(n) = T(n-1-1) + 1 + 1 which is T(n) = T(n-2) + 2 or in other words we need to find our missing k: T(n) = T(n-k) + k. The next step is to take n-k and claim that n-k = 1 because at the end of the recursion it will take exactly O(1) when n<=0. From this simple equation we now know that k = n - 1. Let's place k in our final method: T(n) = T(n-k) + k which will give us: T(n) = 1 + n - 1 which is exactly n or O(n). Is the same as 1. You can test it your self and see that you get O(n). T(n) = T(n/5) + 1 as before, the time for this method to finish equals to the time the same method but with n/5 which is why it is bounded to T(n/5). Let's find T(n/5) like in 1: T(n/5) = T(n/5/5) + 1 which is T(n/5) = T(n/5^2) + 1. Let's place T(n/5) inside T(n) for the final calculation: T(n) = T(n/5^k) + k. Again as before, n/5^k = 1 which is n = 5^k which is exactly as asking what in power of 5, will give us n, the answer is log5n = k (log of base 5). Let's place our findings in T(n) = T(n/5^k) + k as follow: T(n) = 1 + logn which is O(logn) T(n) = 2T(n-1) + 1 what we have here is basically the same as before but this time we are invoking the method recursively 2 times thus we multiple it by 2. Let's find T(n-1) = 2T(n-1-1) + 1 which is T(n-1) = 2T(n-2) + 1. Our next place as before, let's place our finding: T(n) = 2(2T(n-2)) + 1 + 1 which is T(n) = 2^2T(n-2) + 2 that gives us T(n) = 2^kT(n-k) + k. Let's find k by claiming that n-k = 1 which is k = n - 1. Let's place k as follow: T(n) = 2^(n-1) + n - 1 which is roughly O(2^n) T(n) = T(n-5) + n + 1 It's almost the same as 4 but now we add n because we have one for loop. Let's find T(n-5) = T(n-5-5) + n + 1 which is T(n-5) = T(n - 2*5) + n + 1. Let's place it: T(n) = T(n-2*5) + n + n + 1 + 1) which is T(n) = T(n-2*5) + 2n + 2) and for the k: T(n) = T(n-k*5) + kn + k) again: n-5k = 1 which is n = 5k + 1 that is roughly n = k. This will give us: T(n) = T(0) + n^2 + n which is roughly O(n^2).

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

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