本文难度略高于考研数据结构中关于时间复杂度的计算，意在给各位考生对于时间复杂度建立更深层次的理解。
考研中考察重点：选择题中关于时间复杂度的计算，算法题中对算法有时间复杂度的要求。
本文共字，通过阅读本文你可以get：
1.时间复杂度的概念以及皮皮灰的一些看法。
2.非递归函数时间复杂度的计算。
3.递归函数时间复杂度的计算。
1.时间复杂度的概念以及本人的一些看法。
概念：时间复杂度是指执行算法所需要的计算工作量。
这里的工作量是指数量级意义上的工作量，当算法所解决问题的规模增长时，基本操作（举个例子：计算阶乘时的基本操作为乘法，汉莫塔问题中的基本操作为移动一个圆盘）要重复执行的次数必定也会增长，那么我们关心地是这个执行次数以什么样的数量级增长。所谓数量级可以理解为增长率。
参考书上，我们用O(n)来表示时间复杂度的增长率。也就是算法导论中所说的大O表示法。
大O表示法：表示时间复杂性增长率的上界，但不是上确界。
这句话是什么意思呢？举个例子。
例子1.Tn1=O(n)与Tn2=O（2n）是否具有相同的时间复杂度？这里我们可以用到高数中极限的判断方法。在趋近于无穷时limTn1=n,limTn2=2n,又limTn1/Tn2=1/2,因为1/2为常数，数学上称Tn1和Tn2是同阶无穷大。在大O表示法中我们可以认为他们具有相同的时间复杂度增长率。例子2.Tn=lgn+根号n的时间复杂度为多少？根据概念，我们需要找到增长率的上界，也就是对比lgn与根号n哪个增长率大。这里同样可以用到求极限的方法，比较麻烦。在这里举个栗子：lg万=6,根号万=0很明显根号n的增长率更大。所以该题的时间复杂度为根号n。P.S大O表示法要求只写出增长率最大的函数部分，在本例子中为根号n。
在这种描述中使用的基本参数是n，即问题实例的规模。这里的“O”表示量级(order)，比如说“二分检索是O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组。
这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n的平方)算法在n较小的情况下可能比一个高附加代价的O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。
2.非递归函数时间复杂度的计算。
考研中很少考察非递归函数时间复杂度的计算，因为比较简单。
以下为斐波那契的非递归算法（1，1，2，3，5...）
intnon_recursive_method(intn)intp=1;intq=1;if(n==1
n==2)return1;else{for(inti=3;i=n;i++){inttmp=p;//将第一个值p赋给tmpp=q;//将第二个值q赋给p,以后每一次赋值都将得到的最新的和赋给pq=tmp+q;}returnq;}
我们只需要找出其中的基本操作，计算出当问题规模为n时，执行的基本操作的数量级为多少。
该题的基本操作为加法，循环部分从3到n。故该算法时间复杂度为O（n）。
3.递归函数时间复杂度的计算。
考研中重点考察递归函数的时间复杂度计算。
通过2个例子+1个练习介绍解题技巧。
（华科软院）例子1.
假定move（）的时间复杂度为O（1），则下列算法的时间复杂度为_____。
voidhanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);}}
第一步：明确这个函数的基本操作是什么。本题中的基本操作为move(x,n,z);也就是说每次递归都要进行一次该基本操作。根据题目知move（）的时间复杂度为O（1）第二步：列出表达式。T(n)=2T（n-1）+1可以理解为时间复杂度为n的问题进过一次递归后变成了2个时间复杂度为n-1的问题加上执行了一次基本操作。终止条件为if(n==1)move(x,1,z);也就是T(1)=1;第三步：解出该表达式。方法1迭代法：T(n)=2T（n-1）+1...1则T(n-1)=2T（n-2）+1...2对12式联立得T（n）=4T（n-2）+1+2又T（n-2）=2T（n-3）+1重复上述该步骤最后得T(n)=T（1）+1+2+4+8+...+2的n次方又T（1）=1得该算法时间复杂度为O（2的n次方）方法2主方法MasterMethod：
这样可以帮助你快速的分析出你得算法的复杂度是否符合要求。通过公式同样可以得到结果。
（华科软院）例子2.
intfrog｛if(n==0)return1;elsereturn（n+frog（n-1）/2）;｝
上述算法时间复杂度是_____。
本题的/2为陷阱。
第一步：明确这个函数的基本操作是什么。本题中的基本操作为n+frog（n-1）/2第二步：列出表达式。T(n)=T（n-1）+1终止条件为if(n==0)return1;也就是T(1)=1;第三步：解出该表达式。通过上述方法可得时间复杂度为O（n）
（华科软院）练习
证明快速排序算法的时间复杂度是O（NlogN）。
P.S通过上述方法可证。
北京中科白颠疯医院北京中科白颠疯医院