相关疑难解决方法(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)
{ …

假设我们有一个1.000.000元素的数组,我们通过它们来检查一些简单的东西,例如,如果第一个字符是"A".从我(很少)的理解,复杂性将是O(n),并将需要一些X时间.如果我添加另一个IF(不是if)进行检查,让我们说,如果最后一个字符是"G",它将如何改变复杂性？它会增加复杂性和时间吗？喜欢O(2n)和2X？

我想避免考虑不同命令必须进行的计算次数.例如,我理解Len()需要更多的计算才能给出结果而不是简单的char比较,但是我们可以说IF中使用的命令(几乎)具有相同的复杂度.