相关疑难解决方法(0)

我明天有一个计算机科学中期,我需要帮助确定这些递归函数的复杂性.我知道如何解决简单的案例,但我仍然在努力学习如何解决这些更难的案例.这些只是我无法弄清楚的一些示例问题.任何帮助将非常感谢,并将大大有助于我的学习,谢谢!

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)
{ …

什么是假多项式时间？它与多项式时间有何不同？在伪多项式时间运行的一些算法具有运行时间,如O(nW)(对于0/1背包问题)或O(√n)(对于试验除法); 为什么不算作多项式时间？