我理解 Big-O 表示法,但我不知道如何为许多函数计算它。特别是,我一直在尝试计算斐波那契数列的简单版本的计算复杂性:
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
斐波那契数列的计算复杂度是多少以及如何计算?
最佳答案
您对时间函数进行建模以计算 Fib(n)
作为计算时间的总和Fib(n-1)
再加上时间来计算Fib(n-2)
加上将它们加在一起的时间 ( O(1)
)。这是假设重复评估相同的 Fib(n)
采取相同的时间 - 即不使用内存。
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
解决这个递推关系(例如使用生成函数),您最终会得到答案。
或者,您可以绘制递归树,其深度为 n
直观地发现这个函数是渐进的 O(2
n
)
。然后你可以通过归纳法证明你的猜想。
基地:n = 1
很明显
假设T(n-1) = O(2
n-1
)
,因此
T(n) = T(n-1) + T(n-2) + O(1)
等于
T(n) = O(2
n-1
) + O(2
n-2
) + O(1) = O(2
n
)
但是,正如评论中指出的,这不是严格限制。关于此函数的一个有趣事实是,T(n) 与 Fib(n)
的值渐近相同因为两者都定义为
f(n) = f(n-1) + f(n-2)
.
递归树的叶子总是返回1。Fib(n)
的值是递归树中叶子返回的所有值的总和,等于叶子的数量。由于每个叶子需要 O(1) 来计算,T(n)
等于Fib(n) x O(1)
。因此,该函数的紧界是斐波那契数列本身(~ θ(1.6
n
)
)。您可以通过使用我上面提到的生成函数来找出这个紧界。
关于time-complexity - 斐波那契数列的计算复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/360748/