数据结构基础知识总结，时间复杂度是重点

本章的重点是分析程序的时间复杂度。一定要掌握分析时间复杂度的方法和步骤，很多同学在做题时一眼就能看出程序的时间复杂度，但就是无法将其推导过程规范地表述出来。为此，编者查阅众多资料，总结出此类题型的两种形式，供大家参考：

一是循环主体中的变量参与循环条件的判断。

此类题应该找出主体语句中与T(n)成正比的循环变量，将之带入条件中进行计算。例如：

// 程序①
int i=1;
while (i<=n) 
i=i*2;   
// 程序②
int y=5;
while((y+1)*(y+1)<n)
y=y+1;

程序①中，i乘以2的次数正是主体语句的执行次数T(n)，因此有2^T(n)<=n，取对数后，即得 T(n)<=log₂n。

程序②中，y加1的次数恰好与T(n)成正比，则令T(n)=y-5，即y=T(n)+5，(T(n)+5+1) *(T(n)+ 5+1)<n，得出，即。

二是循环主体中的变量与循环条件无关。

此类题可采用数学归纳法，或直接累计循环次数；多层循环时从内到外分析，忽略单步语句、条件判断语句，只关注主体语句的执行次数。此类问题又可分为递归程序和非递归程序。

递归程序一般使用公式进行递推。例如习题5的时间复杂度分析如下：
         T(n)=1+T(n-1)=1+1+T(n- 2)=...=n-1+T(1)
         即
         T(n)=O(n)。

非递归程序比较简单，可以直接累计次数。例如习题7、8等。

思维拓展

求解斐波那契数列有两种常用的算法:递归算法和非递归算法。试分别分析两种算法的时间复杂度。

（提示：请结合归纳总结中的两种方法进行解答。）