斐波那契数列的计算复杂性
我理解Big-O符号，但我不知道如何计算它的许多function。 特别是，我一直在试图弄清斐波那契数列的天真版本的计算复杂性：
int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); } 斐波纳契数列的计算复杂度是多less？它是如何计算的？
您可以将时间函数build模为将Fib(n)计算为Fib(n-1)加上计算Fib(n-2)的时间加上将它们加在一起的时间（ O(1) ）的时间总和。
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
你解决这个重复关系（例如使用生成函数），你将会得到答案。
或者，您可以绘制recursion树，其深度为n并直观地指出该函数是渐近O(2 n ) 。 然后你可以通过归纳certificate你的猜想。
基数： 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) 。
recursion树的叶子将总是返回1. Fib(n)的值是recursion树中叶子返回的所有值的和，等于树叶的数量。 由于每一片叶片都将采用O（1）进行计算，因此T(n)等于Fib(n) x O(1) 。 因此，这个函数的紧束缚是斐波那契数列本身（ θ(1.6 n ) ）。 你可以通过使用上面提到的生成函数来找出这个紧密的界限。
只要问自己需要执行多less条语句才能完成F(n) 。
对于F(1) ，答案是1 （条件的第一部分）。
对于F(n) ，答案是F(n-1) + F(n-2) 。
那么，什么函数满足这些规则？ 尝试n （a> 1）：
a n == a （n-1） + a （n-2）
除以（n-2） ：
a 2 == a + 1
解决a和你得到(1+sqrt(5))/2 = 1.6180339887 ，否则被称为黄金比例 。
所以需要指数的时间。
麻省理工学院对这个具体问题有一个很好的讨论。 在第5页，他们指出，如果你假设一个加法需要一个计算单位，计算Fib（N）所需的时间与Fib（N）的结果非常相关。
因此，您可以直接跳至斐波那契数列的非常接近的近似值：
Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)
并且说，因此，朴素algorithm的最坏情况的性能是
O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))
PS：如果你想了解更多的信息，可以参考Wikipedia 上第N个斐波纳契数的封闭expression式 。
我同意pgaur和rickerbh，recursion斐波那契的复杂度是O（2 ^ n）。
我以相当简单的方式得出了相同的结论，但我相信仍然是有效的推理。
首先，计算第N个斐波纳契数时，要计算多less次recursion斐波那契函数（F（）从现在起）被调用。 如果在序列0到n中每个数字被调用一次，那么我们有O（n），如果每个数字被调用n次，那么我们得到O（n * n）或O（n ^ 2）等等。
所以，当F（）被调用到数n时，在0和n-1之间给定数字调用F（）的次数随着接近0而增长。
作为第一印象，在我看来，如果我们把它放在一个可视化的方式中，每次绘制一个单位F（）被称为一个给定的数字，弄湿得到一种金字塔形状（也就是说，如果我们水平居中）。 像这样的东西：
n * n-1 ** n-2 **** ... 2 *********** 1 ****************** 0 ***************************
现在的问题是，随着n的增长，这个金字塔的基础有多快？
我们来看一个真实的案例，例如F（6）
F(6) * <-- only once F(5) * <-- only once too F(4) ** F(3) **** F(2) ******** F(1) **************** <-- 16 F(0) ******************************** <-- 32
我们看到F（0）被称为32次，即2 ^ 5，对于这个样本情况是2 ^（n-1）。
现在我们想知道F（x）被调用了多less次，我们可以看到F（0）被调用的次数只是其中的一部分。
如果我们从F（6）到F（2）的所有行从心理上移动到F（1）行，我们可以看到现在F（1）和F（0）行的长度是相等的。 这意味着当n = 6时F（）被调用的总次数是2×32 = 64 = 2 ^ 6。
现在，就复杂性而言：
O( F(6) ) = O(2^6) O( F(n) ) = O(2^n)
它的下限为2^(n/2) ，上限为2 ^ n（如其他评论所述）。 这个recursion实现的一个有趣的事实是它有一个Fib（n）本身的紧的渐近界。 这些事实可以概括为：
T(n) = Ω(2^(n/2)) (lower bound) T(n) = O(2^n) (upper bound) T(n) = Θ(Fib(n)) (tight bound)
如果你愿意的话，可以用封闭的forms进一步减less紧密的边界。
certificate答案是好的，但我总是需要手动做一些迭代才能真正说服自己。 于是我在白板上画出了一个小小的调用树，并开始计算节点。 我将我的计数分成总节点，叶节点和内部节点。 这是我得到的：
IN | OUT | TOT | LEAF | INT 1 | 1 | 1 | 1 | 0 2 | 1 | 1 | 1 | 0 3 | 2 | 3 | 2 | 1 4 | 3 | 5 | 3 | 2 5 | 5 | 9 | 5 | 4 6 | 8 | 15 | 8 | 7 7 | 13 | 25 | 13 | 12 8 | 21 | 41 | 21 | 20 9 | 34 | 67 | 34 | 33 10 | 55 | 109 | 55 | 54
立即跳出来的是叶节点的数目是fib(n) 。 需要注意的是，内部节点的数量是fib(n) - 1 。 因此节点的总数是2 * fib(n) - 1 。
由于在对计算复杂度进行分类时会丢弃系数，因此最终答案是θ(fib(n)) 。
那么，据我所知这是O(2^n)在这个函数中只有recursion占用相当的时间（分而治之）。 我们看到，上面的函数将继续在一棵树上，直到当叶子达到F(n-(n-1))的水平时，叶子就接近F(1) 。 所以，在这里当我们记下树的每个深度遇到的时间复杂度时，总和系列是：
1+2+4+.......(n-1) = 1((2^n)-1)/(2-1) =2^n -1
即2^n [ O(2^n) ] 。
http://www.ics.uci.edu/~eppstein/161/960109.html
时间（n）= 3F（n）-2
你可以扩大它，并可视化
T(n) = T(n-1) + T(n-2) < T(n-1) + T(n-1) = 2*T(n-1) = 2*2*T(n-2) = 2*2*2*T(n-3) .... = 2^i*T(ni) ... ==> O(2^n)
由于计算中的重复，斐波那契的天真recursion版本是指数devise的：
在你正在计算的根源上：
F（n）依赖于F（n-1）和F（n-2）
F（n-1）再次依赖于F（n-2），F（n-3）
F（n-2）再次依赖于F（n-3），F（n-4）
那么你在每个级别都有2个recursion调用，在计算中浪费了大量的数据，时间函数看起来是这样的：
T（n）= T（n-1）+ T（n-2）+ C，其中C恒定
T（n-1）= T（n-2）+ T（n-3）> T（n-2）
T（n）> 2 * T（n-2）
…
T（n）> 2 ^（n / 2）* T（1）= O（2 ^（n / 2））
这只是一个下限，为了您的分析的目的应该是足够的，但实时函数是由相同的斐波那契公式的一个常数的因素，并且已知封闭forms是黄金比率的指数。
另外，你可以使用这样的dynamic编程来find斐波那契的优化版本：
static int fib(int n) { /* memory */ int f[] = new int[n+1]; int i; /* Init */ f[0] = 0; f[1] = 1; /* Fill */ for (i = 2; i <= n; i++) { f[i] = f[i-1] + f[i-2]; } return f[n]; }
这是优化的，只做n步，但也是指数。
成本函数是从input大小到解决问题的步骤数量定义的。 当你看到Fibonacci的dynamic版本（ n个步骤来计算表）或最简单的algorithm来知道一个数字是否为素数（ sqrt（n）来分析数字的有效除数）。 你可能会认为这些algorithm是O（n）或者O（sqrt（n）），但是这是不正确的，原因如下：algorithm的input是一个数字： n ，使用二进制表示法input整数n是log2（n）然后做一个variables的变化
m = log2(n) // your real input size
让我们找出作为input大小函数的步数
m = log2(n) 2^m = 2^log2(n) = n
那么作为input大小函数的algorithm的成本是：
T(m) = n steps = 2^m steps
这就是为什么成本是一个指数。
这performance得更好：
unsigned int Fib(unsigned int n) { // first Fibonaci number is Fib(0) // second one is Fib(1) and so on // unsigned int m; // m + current_n = original_n unsigned int a = 1; // Fib(m) unsigned int b = 0; // Fib(m-1) unsigned int c = 0; // Fib(m-2) while (n--) { c = b; b = a; a = b+c; } return a; }
