基本的计算步骤
时间复杂度的定义
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数f（n），使得当n趋近于无穷大时，T（n）/f（n）的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数。记作T（n）=O（f（n）），称O（f（n））为算法的渐进时间复杂度（O是数量级的符号 ），简称时间复杂度。托福答案
根据定义，可以归纳出基本的计算步骤
1. 计算出基本操作的执行次数T（n）
基本操作即算法中的每条语句（以；号作为分割），语句的执行次数也叫做语句的频度。在做算法分析时，一般默认为考虑最坏的情况。
2. 计算出T（n）的数量级
求T（n）的数量级，只要将T（n）进行如下一些操作：
忽略常量、低次幂和最高次幂的系数
令f（n）=T（n）的数量级。
3. 用大O来表示时间复杂度
当n趋近于无穷大时，如果lim（T（n）/f（n））的值为不等于0的常数，则称f（n）是T（n）的同数量级函数。记作T（n）=O（f（n））。
一个示例：
（1） int num1, num2;
（2） for（int i=0; i<n; i++）{
（3） num1 += 1;
（4） for（int j=1; j<=n; j*=2）{
（5） num2 += num1;
（6） }
（7） }
分析：
1.
语句int num1, num2;的频度为1;
语句i=0;的频度为1;
语句i<n; i++; num1+=1; j=1; 的频度为n;
语句j<=n; j*=2; num2+=num1;的频度为n*log2n;
T（n） = 2 + 4n + 3n*log2n
2.
忽略掉T（n）中的常量、低次幂和最高次幂的系数
f（n） = n*log2n
3.
lim（T（n）/f（n）） = （2+4n+3n*log2n） / （n*log2n）
= 2*（1/n）*（1/log2n） + 4*（1/log2n） + 3
当n趋向于无穷大，1/n趋向于0,1/log2n趋向于0
所以极限等于3.
T（n） = O（n*log2n）
简化的计算步骤
再来分析一下，可以看出，决定算法复杂度的是执行次数最多的语句，这里是num2 += num1,一般也是最内循环的语句。
并且，通常将求解极限是否为常量也省略掉？
于是，以上步骤可以简化为：
1. 找到执行次数最多的语句
2. 计算语句执行次数的数量级
3. 用大O来表示结果
继续以上述算法为例，进行分析：
1.
执行次数最多的语句为num2 += num1
2.
T（n） = n*log2n
f（n） = n*log2n
3.
// lim（T（n）/f（n）） = 1
T（n） = O（n*log2n）
--------------------------------------------------------------------------------

一些补充说明
最坏时间复杂度
算法的时间复杂度不仅与语句频度有关，还与问题规模及输入实例中各元素的取值有关。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的运行时间不会比任何更长。
求数量级
即求对数值（log），默认底数为10,简单来说就是"一个数用标准科学计数法表示后，10的指数".例如，5000=5x10 3 （log5000=3） ,数量级为3.另外，一个未知数的数量级为其最接近的数量级，即最大可能的数量级。
求极限的技巧
要利用好1/n.当n趋于无穷大时，1/n趋向于0
--------------------------------------------------------------------------------
一些规则（引自：时间复杂度计算 ）
1） 加法规则
T（n,m） = T1（n） + T2（n） = O （max （ f（n）， g（m） ）
2） 乘法规则
T（n,m） = T1（n） * T2（m） = O （f（n） * g（m））
3） 一个特例（问题规模为常量的时间复杂度）
在大O表示法里面有一个特例，如果T1（n） = O（c）， c是一个与n无关的任意常数，T2（n） = O （ f（n） ） 则有
T（n） = T1（n） * T2（n） = O （ c*f（n） ） = O（ f（n） ）
也就是说，在大O表示法中，任何非0正常数都属于同一数量级，记为O（1）。
4） 一个经验规则
复杂度与时间效率的关系：
c < log2n < n < n*log2n < n2 < n3 < 2n < 3n < n! （c是一个常量）
|--------------------------|--------------------------|-------------|
较好 一般 较差
其中c是一个常量，如果一个算法的复杂度为c 、 log2n 、n 、 n*log2n,那么这个算法时间效率比较高 ,如果是 2n , 3n ,n!,那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。
--------------------------------------------------------------------------------------------------
复杂情况的分析
以上都是对于单个嵌套循环的情况进行分析，但实际上还可能有其他的情况，下面将例举说明。雅思答案
1.并列循环的复杂度分析
将各个嵌套循环的时间复杂度相加。
例如：
for （i=1; i<=n; i++）
x++;
for （i=1; i<=n; i++）
for （j=1; j<=n; j++）
x++;
解：
第一个for循环
T（n） = n
f（n） = n
时间复杂度为Ο（n）
第二个for循环
T（n） = n2
f（n） = n2
时间复杂度为Ο（n2）
整个算法的时间复杂度为Ο（n+n2） = Ο（n2）。
2.函数调用的复杂度分析
例如：
public void printsum（int count）{
int sum = 1;
for（int i= 0; i<n; i++）{
sum += i;
}
System.out.print（sum）；
}
分析：
记住，只有可运行的语句才会增加时间复杂度，因此，上面方法里的内容除了循环之外，其余的可运行语句的复杂度都是O（1）。
所以printsum的时间复杂度 = for的O（n）+O（1） = 忽略常量 = O（n）
*这里其实可以运用公式 num = n*（n+1）/2,对算法进行优化，改为：
public void printsum（int count）{
int sum = 1;
sum = count * （count+1）/2;
System.out.print（sum）；
}
这样算法的时间复杂度将由原来的O（n）降为O（1），大大地提高了算法的性能。
3.混合情况（多个方法调用与循环）的复杂度分析
例如：
public void suixiangMethod（int n）{
printsum（n）；//1.1
for（int i= 0; i<n; i++）{
printsum（n）； //1.2
}
for（int i= 0; i<n; i++）{
for（int k=0; k
System.out.print（i,k）； //1.3
}
}
suixiangMethod 方法的时间复杂度需要计算方法体的各个成员的复杂度。
也就是1.1+1.2+1.3 = O（1）+O（n）+O（n2） ----> 忽略常数 和 非主要项 == O（n2）
--------------------------------------------------------------------------------------------------
更多的例子
O（1）
交换i和j的内容
temp=i;
i=j;
j=temp;
以上三条单个语句的频度为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T（n）=O（1）。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O（1）。托福答案
O（n2）
sum=0; /* 执行次数1 */
for（i=1;i<=n;i++）
for（j=1;j<=n;j++）
sum++; /* 执行次数n2 */
解：T（n） = 1 + n2 = O（n2）
for （i=1;i<n;i++）
{
y=y+1; ①
for （j=0;j<=（2*n）；j++）
x++; ②
}
解： 语句1的频度是n-1
语句2的频度是（n-1）*（2n+1） = 2n2-n-1
T（n） = 2n2-n-1+（n-1） = 2n2-2
f（n） = n2
lim（T（n）/f（n）） = 2 + 2*（1/n2） = 2
T（n） = O（n2）。
O（n）
a=0;
b=1; ①
for （i=1;i<=n;i++） ②
{
s=a+b; ③
b=a; ④
a=s; ⑤
}
解： 语句1的频度：2,
语句2的频度：n,
语句3的频度：n,
语句4的频度：n,
语句5的频度：n,
T（n） = 2+4n
f（n） = n
lim（T（n）/f（n）） = 2*（1/n） + 4 = 4
T（n） = O（n）。
O（log2n）
i=1; ①
while （i<=n）
i=i*2; ②

解： 语句1的频度是1,
设语句2的频度是t, 则：nt<=n; t<=log2n
考虑最坏情况，取最大值t=log2n,
T（n） = 1 + log2n
f（n） = log2n
lim（T（n）/f（n）） = 1/log2n + 1 = 1
T（n） = O（log2n）
O（n3）
for（i=0;i<n;i++）
{
for（j=0;j<i;j++）
{
for（k=0;k<j;k++）
x=x+2;
}
}
解：当i=m, j=k的时候，内层循环的次数为k当i=m时， j 可以取 0,1,…，m-1 , 所以这里最内循环共进行了0+1+…+m-1=（m-1）m/2次所以，i从0取到n, 则循环共进行了： 0+（1-1）*1/2+…+（n-1）n/2=n（n+1）（n-1）/2次
T（n） = n（n+1）（n-1）/2 = （n3-n）/2
f（n） = n3
所以时间复杂度为O（n3）。