确定递归函数的复杂性（大O符号）(Determining complexity for recurs

我有一个明天计算机科学期中和我需要帮助确定这些递归函数的复杂性。我知道如何解决简单的情况，但我仍然努力学习如何解决这些困难的情况下。这些只是一小部分，我无法弄清楚的例子问题。任何帮助将非常感激，在我的研究将极大地帮助，谢谢！

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符号，对于每个功能，是按数字顺序：

第一功能正在到达基地壳体所以其前递归调用n次O(n)通常被称为线性的 。
第二个功能被称为N-5每次，所以我们在调用之前扣除五名来自N，但N-5也O(n) （实际上称为N / 5倍顺序。而且，为O（n / 5）= O（N））。
此功能的log（n）基地5，对于我们每次调用函数所以它之前除以5 O(log(n))基地5），通常被称为对数和最经常大O符号和复杂性分析使用基地2 。
第四，这是O(2^n) ，或指数，因为除非它已经被递归n次的每个函数调用调用本身两次。
至于最后一个函数，for循环需要N / 2，因为我们增加2，和递归取n-5，因为for循环递归调用，因此时间复杂度为（N-5）*（N / 2）=（2N-10）* N = 2 ^ 2- 10N，由于渐近行为和最坏的情况下考虑或上限即大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 * a + T(0) * 2 ^ n 
     = a * 2^(n+1) - a + b * 2 ^ n
     = (2 * a + b) * 2 ^ n - a
     = O(2 ^ n)

其中，a，b是常数一些。

5。

T(n) = n / 2 + T(n - 5)

我们可以通过感应证明T(5k) >= T(5k - d)其中d = 0，1，2，3，4

写n = 5m - b （M，b是整数; b = 0，1，2，3，4），然后m = (n + b) / 5 ：

T(n) = T(5m - b) <= T(5m)

（实际上，要更严格这里，一个新的函数T'(n)应被定义为使得T'(5r - q) = T(5r)其中q = 0, 1, 2, 3, 4 ，我们知道。 T(n) <= T'(n)如上证明，当我们知道， T'(n)是O(f)这意味着存在恒定的a，b，使得T'(n) <= a * f(n) + b ，我们可以推导出T(n) <= a * f(n) + b ，因此T(n)是在O(f)这一步是不是真的必要的，但它更容易想到当你没有对付其余部分。）

扩展T(5m)

T(5m) = 5m / 2 + T(5m - 5) 
      = (5m / 2 + 5 / 2) * m / 2 + T(0) 
      = O(m ^ 2) = O(n ^ 2)

因此， T(n)是O(n ^ 2)

Answer 3:

有一个问题我找到的最佳途径逼近递归算法的复杂度绘制递归树。一旦你的递归树：

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

第一个函数将具有长度n叶节点的数目和1 ，从而复杂性将是n*1 = n
第二函数将具有长度n/5和叶节点的数目再次1所以复杂性将是n/5 * 1 = n/5 。应该近似于n
对于第三功能，因为n正在由5上的每个递归调用划分，递归树的长度将被log(n)(base 5)和叶节点的数目再次1，从而复杂性将被log(n)(base 5) * 1 = log(n)(base 5)
对于自每个节点的第四功能将有两个子节点，叶节点的数量将等于(2^n)和递归树的长度将是n所以复杂性将是(2^n) * n 。但由于n是前面微不足道(2^n) ，可以忽略不计和复杂性只能说是(2^n)
对于第五功能，有两个元件引入了复杂性。通过复杂的功能和复杂性介绍递归特性介绍for每个功能回路。做上述计算中，通过函数递归性质带来的复杂性将是~ n和复杂性由于for循环n 。总的复杂性将是n*n 。