以下两种方法其实是一样的
1、方法一
其实所有人都知道T(n)= T(n-1) + T(n-2), T(1) = T(2)=1,T(n)也是一个斐波那契数列，求解时间复杂度的本质也就是求数列通项，结果MB的一个通项就把我难住了，只好回来google一下，把高中数学用的求通项的方法放出来，软院的学生，果然还是跌倒在了数学上。。。
P.S.用线代知识也能解据说？据说高中学的特征根法求通项实际上就是线代中某个定理？线代弱比给跪了，求解答。。。
下面就是斐波那契数列通项的求法：
已知数列
，其中
，
，求数列的通项。
解：首先我们要构造一个等比数列，于是设
则有
。 （1）
则由已知得 
（2）
对照（1）（2）两式得
解得
或 
。
我们取前一解，就会有
。
设
，则有
所以数列
为等比数列，首项为
，公比为
所以 
。即
（3）
再次构造等比数列，设
则有
对照（3）式，可得
所以 x=
.
于是有
设
，则有数列
为等比数列，首项为
，公比为
，于是
=
所以有
。
于是有T(n) = O((5^(2/1)+1/2)^n)....
2、方法二 （转自http://www.pep.com.cn/gzsx/xszx_1/jtzd/201107/t20110708_1054105.htm）
做了这些年的数学题，我时常有这样的感受。一个新的数学题初次接触时，会觉得这个题的解题技巧很妙，甚至有点非夷所思，但如果把同类型问题多做几个，你就会发现原来所谓的技巧，其实是一种再正常不过的想法，是一种由已知到未知的必然之路。这样我们就由解题的技巧而转化到了通解通法，进一步就会形成解题的思想，所以我对于数学爱好者建议，做题时要把同类型题多种总结和分析，这样你的数学才会有长足的进步。
下面我们就由递推推导通项的问题，进行对比分析。
例1 在数列中，
，求数列的通项。（普通高中课程标准实验教科书人教A版必修5第69页6题）
分析：此题可分两步来进行，首先由
构造一个等比数列，其中
，并写出的通项；然后利用
，两边同除以
得
，由累加法，就可求出数列的通项。
解：
（
设，则
（
）所以数列为等比数列，且首项为
，公比为3。所以
。
于是有
，两边都除以得
设
，则有
由累加法可得
因为
所以
（）
于是有
。
总结：上面的求解过程实质，求是一个把已知条件逐步化简的过程，由相邻三项的递推关系化为相邻两项的递推关系，进一步求出通项公式。
下面我们来研究一下著名的斐波那契数列的通项。
已知数列，其中，，求数列的通项。
解：首先我们要构造一个等比数列，于是设
则有。 （1）
则由已知得 （2）
对照（1）（2）两式得解得 或 。
我们取前一解，就会有。
设，则有
所以数列为等比数列，首项为，公比为
所以 。即 （3）
再次构造等比数列，设
则有
对照（3）式，可得所以 x=.
于是有
设，则有数列为等比数列，首项为，公比为，于是=
所以有。
