<分区>
谁能指导我求出时间复杂度？时间复杂度是否随操作系统而变化？
int fn(int n){
if(n==1){
return 1;
}
else{
return(fn(n-1)+ fn(n-1));
}
}
<分区>
谁能指导我求出时间复杂度？时间复杂度是否随操作系统而变化？
int fn(int n){
if(n==1){
return 1;
}
else{
return(fn(n-1)+ fn(n-1));
}
}
最佳答案
你可以做一个递归关系T，表示计算和输入大小N所花费的时间，然后使用伸缩的方法来帮助找到Big -O 像这样:
T(N) = T(N-1) + T(N-1) + c = 2*T(N-1) + c
在这里，我们可以看到计算 T(N) 所需的时间将是 2*T(N-1)加上固定的时间 c .我们还可以通过您的功能看到:
T(1) = b
在这里，我们可以通过您的基本情况看到，当 N=1 时没有递归调用，因此，它将花费常数时间 b计算 T(1) .
如果我们看一下T(N) , 我们需要找出什么 T(N-1)是的，所以计算我们得到:
T(N-1) = 2*T(N-2) + c
计算 T(N-2)我们得到:
T(N-2) = 2*T(N-3) + c
因此，我们可以将它们相互分解...
T(N-1) = 2*(2*T(N-3) + c) + c = 4*T(N-3) + 3c
T(N) = 2*(4*T(N-3) + 3c) + c = 8*T(N-3) + 7c
通过查看方程式下阶梯式生成的模式，我们可以根据 k 对其进行概括:
T(N) = 2^k * T(N-k) + ((2^k)-1 * c)
我们知道我们的递归调用将在 T(N-k) = T(1) 时停止。 , 所以我们想找到什么时候 N-k = 1 ，这是当 k = N-1 ，所以代入我们的值(value) k并删除常数-变量时间，我们可以找到我们的 Big-O:
T(N) = (2^N) * T(1) + (2^N)-1 * c
= (2^N) * b + (2^N)-1*c
= O(2^N) (-1, b & c are constants, so they can be removed, giving 2*(2^N), where 2* is a constant, giving 2^N)
时间复杂度衡量算法在输入大小方面的扩展程度，不一定衡量其运行速度。因此，时间复杂度不依赖于您的操作系统。
关于java - 我如何找到以下功能的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57816109/