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

我明天有计算机科学期中考试，我需要帮助确定这些递归函数的复杂性。我知道如何解决简单的情况，但我仍在努力学习如何解决这些更困难的情况。这些只是我无法解决的一些示例问题。任何帮助将不胜感激，并对我的学习有很大帮助，谢谢！

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

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

这个函数是 log(n) 以 5 为底，每次除以 5 在调用函数之前，所以它的O(log(n))（基数为 5），通常称为对数最常见的是 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), or 指数，因为每个函数调用都会调用自身两次，除非它已递归n times.

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

祝你期中考试好运;)