时间复杂度计算分为以下三个步骤（推导大O阶）：

1.用常数1取代运行时间中的所有加法常数

2.在修改后的运行次数函数中，只保留最高阶项

3.如果最高阶项存在且不是1，则去除与这个项相乘的常数，得到的结果就是大O阶。

下面给大家看几个例子：

（1）常数阶O（1）：

int sum = 0,n = 100;/*执行一次*/
sum = (1+n)*n/2;/*执行一次*/
printf("%d",sum);/*执行一次*/

这段代码的运行次数是3，根据我们推导大O阶的方法，第一步把常数项3改为1；然后第二步保留最高项，但是它没有最高项，所以这个算法的时间复杂度为O（1）。

另外，对于分支结构而言，无论是真是假，执行次数都是恒定的，不会随着n的变化而变化，它的时间复杂度也是O（1）。

（2）线性阶O（n）：

int i;
for(i = 0;i<n;i++){
	/*时间复杂度为O（1）的程序步骤序列*/
}

这个算法的运行次数为n，第一步我们将其常数项变为1，但是它没有常数项，故跳过；第二步只保留最高项n；第三步去除最高项的系数，这个最高项的系数本身就是1；所以这个的时间复杂度就为O(n)。

（3）对数阶O(logn):

int count = 1;
while(count<n)
{
	count = count*2;
	/*时间复杂度为O（1）的程序步骤序列*/
}

同样的，我们首先要计算出这个算法总共需要的运行次数，当count=1时，while里面会执行：

count = 1* 2 = 2

count = 2* 2 = 4

count = 4* 2 = 8

count = 8* 2 = 16

……

设总共执行了t次

所以2^(t-1)*2 = n

t = log_2 n

（4）平方阶O(n^2)：

int i,j;
for(i = 0;i<n;i++){
	for(j = 0;j<n;j++){
	/*时间复杂度为O（1）的程序步骤序列*/
}
}

循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。

int i,j;
for(i = 0;i<n;i++){
	for(j = i;j<n;j++){
	/*时间复杂度为O(1)的程序步骤序列*/
}
}

当i = 0时，里面循环执行了n次；

当i = 1时，里面循环执行了（n-1）次；

当i = 2时，里面循环执行了（n-2）次；

……

当i = n-1时，里面循环执行了（n-(n-1)）次

所以总的执行次数为n+(n-1)+……+(n-(n-1))=(n^2)/2+n/2

同样的，第一步将常数项变为1，此式没有；

第二步只保留最高项，即(n^2)/2；

第三步去除这个项的系数，所以它的时间复杂度为O(n^2)。

时间复杂度的计算，你，学会了吗？