求时间复杂度的方法
1.求和法
当算法中语句的执行次数与某一变量有直接关系，而该变量的变化起止范围又较为明确，则可以利用求和公式得出最大的语句频度f(n)，再对其取数量级(阶)即可。
例1有算法如下：
①for(i=1;i
解：以上算法中频度最大的是语句③，它的执行次数跟循环变量i和j有直接关系，因此其频度可以通过求和公式求得：
所以，该算法的时间复杂度为平方阶，记作T(n)=O(n2)。例2有一算法如下：
①for(i=1;i
解：以上算法中频度最大的是语句④，其频度可以通过求和公式求得：
所以，该算法的时间复杂度为立方阶，记作T(n)=O(n3)。例3有如下算法：
①y=0;
②while((y+1)2
解：算法中频度最大的应该是语句③，它的执行次数与y有关，已知y初值为0，当(y+1)2>n时循环终止，则y的最大取值应该为
n姨-1。所以语句③的频度可以通过求和公式得到：
所以，该算法的时间复杂度记作
2.假设法
在某些较为复杂的算法中，循环结构的循环次数很难直接看出，特别是当循环次数与循环体中的某些语句执行有联系时，语句频度的计算变得比较困难。此时，可以先假设循环执行次数为k次，再对算法进行分析，根据循环终止条件求出语句频度f(n)，最后求出T(n)。 例4有一算法如下：
x=91;y=100;while(y>0)
if(x>100){x-=10;y--;}elsex++;
解：假设while循环的循环体执行k次，可以发现：k=1时，x=92，y=100k=2时，x=93，y=100k=3时，x=94，y=100
…
k=10时，x=101，y=100k=11时，x=91，y=99
…
k=22时，x=91，y=98
…
由分析可知，每循环11次，y的值发生一次变化，y需共变化100次。所以，f(n)=100*11=1100。则该算法的执行时间是一个与问题规模n无关的常数，它不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。因此,该算法的时间复杂度为常数阶，记作T(n)=O(1)。
例5有如下算法：
i=s=0；while(s
解：假设循环执行k次，则有：
k=1时，i=1，s=0+1k=2时，i=2，s=0+1+2k=3时，i=3，s=0+1+2+3
…
执行到k次时，。
由于s
，所以
，该算法的时间复杂度
。
3.迭代法
当算法中包含递归函数时，其时间复杂度也会被转化为一个递归方程，上述两种方法此时不再适用。递归方程的形式多种多样，其求解方法也是不一而足，比较常用是迭代法。其基本步骤是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来得到时间复杂度T(n)。
例6有如下算法：
voidfun(inta[],intn,intk){inti;
if(k==n-1)
for(i=0;i
{for(i=k;i
解：设fun(a,n,k)的执行时间为T(k)，由算法可以得到时间复杂度的递归关系如下： 则：
所以，该算法的时间复杂度T(n)=O(n2)