如何找到下面函数的时间复杂度？[副本]

Question

有人能指导我找到时间复杂性吗？时间复杂度是否随操作系统而变化？

int fn(int n){
   if(n==1){
     return 1;
    }
    else{
     return(fn(n-1)+ fn(n-1));
    } 
}

Answer 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时没有递归调用，因此，计算t(1)将需要一个恒定的时间b。

如果我们看一下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

T(N) = 2^k * T(N-k) + ((2^k)-1 * c)

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)

时间复杂度是衡量一个算法在输入大小方面的扩展程度，而不一定是衡量它运行的速度。因此，时间复杂性并不依赖于您的操作系统。