确定递归函数的复杂度(Big O表示法) [英] Determining complexity for recursive functions (Big O notation)

问题描述

明天我有计算机科学中期课程，我需要帮助确定这些递归函数的复杂性.我知道如何解决简单的案件，但我仍在尝试学习如何解决这些较困难的案件.这些只是我无法弄清的几个示例问题.任何帮助将不胜感激，将极大地帮助我的学习，谢谢！

I have a Computer Science Midterm tomorrow and I need help determining the complexity of these recursive functions. I know how to solve simple cases, but I am still trying to learn how to solve these harder cases. These were just a few of the example problems that I could not figure out. Any help would be much appreciated and would greatly help in my studies, Thank you!

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

推荐答案

每个函数的时间复杂度(以O表示):

The time complexity, in Big O notation, for each function:

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

此函数在到达基本情况之前被递归调用n次，因此其O(n)通常称为 linear .

This function is being called recursively n times before reaching the base case so its O(n), often called 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)).

This function is called n-5 for each time, so we deduct five from n before calling the function, but n-5 is also O(n). (Actually called order of n/5 times. And, 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.

This function is log(n) base 5, for every time we divide by 5 before calling the function so its O(log(n))(base 5), often called logarithmic and most often Big O notation and complexity analysis uses base 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 次被递归.

Here, it's O(2^n), or exponential, since each function call calls itself twice unless it has been recursed 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循环是递归调用的，因此时间复杂度在

And here the for loop takes n/2 since we're increasing by 2, and the recursion takes n-5 and since the for loop is called recursively, therefore, the time complexity is in

，

由于渐近行为和最坏情况的考虑或大O争取的上限，我们只对最大项感兴趣，因此O(n^2).

due to Asymptotic behavior and worst-case scenario considerations or the upper bound that big O is striving for, we are only interested in the largest term so O(n^2).

祝你中期顺利；)

这篇关于确定递归函数的复杂度(Big O表示法)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！