大O符号 - 递归函数

我需要找到这个递归算法的复杂性，所以，我有3个递归算法，只是想知道它们的大O符号。我想我有这些算法中的2个的解决方案，只是想检查一下社区。大O符号 - 递归函数

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

什么是这个递归算法的复杂性，我没有这个算法的解决方案，能够你帮我？

来源

2017-09-14 Wolvy

通过“他们的大O符号”，你的意思是他们的时间复杂性或者他们结果的增长顺序？ – meowgoesthedog

我认为你需要时间复杂性。另外，编辑你的函数f3，它不会带任何参数 –

[Master-Theorem]（https://en.wikipedia.org/wiki/Master_theorem）是解决更复杂的问题的常用方法，像最后一个你的问题。 – Paul

你的前两个答案是正确的。让我们分析一下你的第三个问题，每次，n除以2，我们需要加n次n，所以复杂度将是 1 * n + 1 * n/2 + 1 * n/4 + ..... + 1 = n（1 + 1/2 + 1/4 + ...）= O（n）

来源

2017-09-14 15:18:12 codecrazer

@codecrazers answer已经涵盖了如何逐步计算复杂度。但总的来说，Master-Theorem使问题变得更加简单。

要开始，让我们改变这个代码

进入复发：

int f(int n) 
{ 
    if(n <= 1) 
     1 
    else 
     f(n/2) + θ(n) 
}

所以

T(n) = T(n/2) + θ(n) 
T(n <= 1) = 1

是区分3，从而产生

T(n) = θ(n)

来源

2017-09-14 15:37:03 Paul

大O符号 - 递归函数

回答

相关问题