计算时间复杂度

规则

斐波那契数列

表达式：F[1]=1,  F[2]=1,  F[n]=F[n-1]+F[n-2]（n>=3）

如果是递推去计算，也就是一个for循环搞定，肯定是 O(n) 的，因为每一项的值可以通过前面两项的值得到，属于是记忆化了

所以啊，计算复杂度一定要注意是否有记忆化

那么如果是递归去计算，函数如下：

int F(int n) {
	if (n<=2) return 1;
	else return F(n-1)+F(n-2);
}

A.O(1)   B.O(n)   C.O(n^2)   D.O(Fn)

我们可以画成一棵二叉树，根节点的值等于两个子结点的和，每个叶子结点的值为1，其中，结点中的数字 i ，代表f[i]

形如此图：

我们发现，如果要计算f[5]，也就是要计算f[4]，和f[3]，计算f[4]，又要计算f[3]，f[2]，计算f[3]，又要计算f[2]，f[1]

最终我们发现，每个结点都会被跑一次，也就是说，计算f[5]，也就是计算这棵树有多少结点。

那么这还不好算？约等于2^n即可了。但题目选项没有这个。我们继续推。

我们还可以发现，每一个结点，都是由这个结点的叶子结点去计算，然后才有这个值的。

譬如，f[5]的值自己不就是由这张图的每个叶子结点的值的和去构成的吗？也就是此图中，f[5]=5

为什么？可以感性理解一下，刚开始就只有叶子结点有值，然后每个结点的值都是由叶子结点的值推来。所以加上这个结点的值，就是加上这个结点底下包含的叶子结点的值。

那么有了叶子结点的个数，非叶子结点个数也可以推出来了

假设一棵树有k层，那么叶子结点的数量知道了，也就是2^(k-1)算出来了，那么整棵树的结点数量，2^k  -  1还不好算吗？

也就是 叶子结点数量*2-1

所以此图结点数量就算出来了，5*2-1

那么推到一般情况。计算f[n]，就有n个叶子结点，整棵树就是 n*2-1个结点

所以计算整棵树约等于计算n个结点时调用F(i)所花费的时间，我们计算起来就是O(Fn)

通杀之招

计算 T(n)=2*T(n/2)+2n，T(n)=O(？)

A.O(n)   B.O(nlogn)   C.O(n^2)   D.O(n^2logn)

首先注意到了n/2，容易联想到带log，AC排除。

我们展开一下就知道了

T(n)=2*T(n/2)+2n

T(n/2)=2*T(n/4)+n

T(n/4)=2*T(n/8)+n/2

算3个就ok，我们再带回去

T(n)=2*( 2*T(n/4)+n )+2n

T(n)=4*T(n/4)+2n+2n

T(n)=4*( 2*T(n/8)+n/2 )+2n+2n

T(n)=8*T(n/8)+2n+2n+2n

这个时候，我们发现，我们迭代logn次就结束了，而每次迭代都会产生一个2n出来，那么logn次迭代，就产生logn个2n，我们最终需要计算logn个2n相加起来是多少。

那就是2n+2n+2n+...+2n（一个logn个），也就是2nlogn，约等于一下，所以总体复杂度是O(nlogn)

选B

总结一下，展开一下计算总递推式需要用到的递推式，再带入总递推式即可。看到除法肯定带log。我们只需看总共迭代多少次，每次迭代产生的数。

好了，知道了这一个，我们剩下的直接秒杀了。（至少历年NOIP的是秒杀了）

小练手

T(n)=2T(n/4)+sqrt(n)，T(1)=1，求O(?)

我们去找每次迭代多产生了啥，一共迭代几次即可。

T(n)=2T(n/4)+sqrt(n)

T(n/4)=2T(n/16)+sqrt(n/4)

T(n/16)=2T(n/64)+sqrt(n/16)

带入

T(n)=2( 2T(n/16)+sqrt(n/4) )+sqrt(n)

T(n)=4*T(n/16)+ 2*sqrt(n/4) + sqrt(n)

T(n)=4*( 2T(n/64)+sqrt(n/16) )+ 2*sqrt(n/4) + sqrt(n)

T(n)=8*T(n/64)+  4*sqrt(n/16)+ 2*sqrt(n/4) + sqrt(n)

每次迭代都多了约等于一个sqrt(n)，

最终迭代logn次结束，多出了一共是logn个sqrt(n)，计算相加，也就是sqrt(n)*logn

答案：O（sqrt(n)*logn）

T(n)=2T(n/2)+nlogn，T(1)=1，求O(?)

不多说了，logn次迭代，每次多出nlogn，最终也就是要算  logn*nlogn，也就是n*logn*logn，也就是n*log^2*n

答案：O(n*log^2*n)

 这个表达可能有误差，手写出来是这样的：

原因：