algorithm - 大 O 符号 - 递归函数

Question

我需要找到这种递归算法的复杂性，所以，我有 3 种递归算法，只想知道它们的大 O 表示法。我想我有针对其中 2 种算法的解决方案，只是想与社区核实一下。

int f1(int n)
{
    if ( n<= 1)
        return (1);
    else 
        return (n *f1(n-1))
}

我认为这个问题的解决方案是 O(n)。

int f2 (int n)
{
    if(n<=1)
        return(1);
    else
        return(n*f2(n / 2))
}

我认为这个问题的解决方案是 O(Log 2 (n))

int f3 
{
    int x, i; 
    if( n <= 1)  
        return 1;  
    else 
    {
        x = f3 (n / 2);           
        for( i = 1 ; i <= n ; i++)   
         x++;        
         return x;  
    }
}

这个递归算法的复杂度是多少，我没有这个算法的解法，你能帮我吗？

Answer 1

您的前两个答案是正确的。 让我们来分析你的第三个问题， 对于每一次，n 除以 2，我们需要将 x 添加 n 次， 所以复杂性将是 1*n+1*n/2+1*n/4+.....+1=n(1+1/2+1/4+...)=O(n)