确定递归函数的复杂度(大O表示法)

Question

明天我有一门计算机科学期中考试，我需要帮助来确定这些递归函数的复杂度。我知道如何解决简单的案例，但我仍在努力学习如何解决这些较难的案例。这些只是我无法解决的几个示例问题。任何帮助都会让我感激不尽，也会对我的学习有很大帮助，谢谢！

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

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

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

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

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

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

Answer 1

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

这个函数是以5为底的对数，因为每次我们在调用函数之前都要除以5，所以它的对数(以5为底)，通常称为对数对数(O(log(n)))，最常见的是大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)或exponential，，因为每个函数调用都会调用自身两次，除非它已经被递归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)感兴趣。

祝你期中考试好运;)

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

Answer 3

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

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

第一个函数的长度为n，叶节点的个数为1，所以复杂度为n*1 = n

• The，第二个函数的长度为n/5，叶节点的个数为n/5 * 1 = n/5。它应该近似于第三个函数，因为在每次递归调用时，n被5除，递归树的长度将是log(n)(base 5)，而叶节点的数量又是1，所以复杂度将是log(n)(base 5) * 1 = log(n)(base 5)

• For第四个函数，因为每个节点都有两个子节点，叶节点的数量将等于n，递归树的长度将是n，因此复杂度将是(2^n) * n。但是由于n在(2^n)面前是微不足道的，它可以忽略不计，复杂性只能说是第五个函数的(2^n).

• For，所以有两个因素引入了复杂性。函数的递归性质引入的复杂性和每个函数中的for循环引入的复杂性。进行上述计算，函数的递归性质带来的复杂性将是~ n，而for循环n带来的复杂性也是如此。总复杂度将为n*n。

注意:这是一种快速而肮脏的计算复杂性的方法(不是官方的！)。会很乐意听到关于这方面的反馈。谢谢。