大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;
}
}
什么是这个递归算法的复杂性,我没有这个算法的解决方案,能够你帮我?
答
你的前两个答案是正确的。 让我们分析一下你的第三个问题, 每次,n除以2,我们需要加n次n, 所以复杂度将是 1 * n + 1 * n/2 + 1 * n/4 + ..... + 1 = n(1 + 1/2 + 1/4 + ...)= O(n)
答
@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)
通过“他们的大O符号”,你的意思是他们的时间复杂性或者他们结果的增长顺序? – meowgoesthedog
我认为你需要时间复杂性。另外,编辑你的函数f3,它不会带任何参数 –
[Master-Theorem](https://en.wikipedia.org/wiki/Master_theorem)是解决更复杂的问题的常用方法,像最后一个你的问题。 – Paul