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

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

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

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

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

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

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。

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

---

祝你们期中考试好运!)