14天阅读挑战赛
上一节我们了解了算法的度量方法，算法与归结为的函数中的加上的常数可以忽略，与最高次项相乘的常数可以忽略，与最高阶项外的其他次要项可以忽略，与最高项的指数有关，因此在下面的学习中，我们就可以利用这几句话，化简相关的复杂度。
算法的复杂度分为时间复杂度和空间复杂度。
下面，我们分开学习，先来看时间复杂度。
时间复杂度：算法运行所需要的时间。如果用函数来定义的话，可以定义为：进行算法分析时，执行次数T(n)是关于问题规模n的函数，分析T(n)随n的变化确定T(n)的数量级。记作T(n) = O(f(n))。?
这种用大写的O来表示时间复杂度的记法叫做大O记数法。?O为键盘上I、P之间的那个字母，不是0、1、2、3、4中的0。
随着n的增大，T(n)增大最慢的那个一般就是最优算法。
常见的时间复杂度有以下几类：常数阶、线性阶、对数阶、指数阶、多项式阶等。
我们分别介绍以上几类时间复杂度。
常数阶：先来看一段代码
int a=1,b=2,sum=0;//执行了一次
sum=a+b;//执行了一次
printf("a+b=%d",sum);//执行了一次
每个语句都执行了一次，则函数f(n)=3，用大O表示就是O(3)，但在表示时间复杂度时，如果遇到的是常数，则用常数1代替运行中所有的其他常数，于是，上面这个程序的时间复杂度记为O(1)。
int a=1,b=2,sum=0;//执行第1次
sum=a+b;//执行第2次
sum=a+b+b;//执行第3次
sum=a+b+b;//执行第4次
sum=a+b-b;//执行第5次
sum=a+b-b;//执行第6次
sum=a+b+b;//执行第7次
sum=a+b+b;//执行第8次
sum=a+b-b;//执行第9次
sum=a+b-b;//执行第10次
sum=a+b-b;//执行第11次
sum=a+b+b;//执行第12次
sum=a+b;//执行第13次
printf("a+b=%d",sum);//执行第14次以上代码执行了14次，则函数为f(n)=14，根据上面我们所说的大O记法规则，O(14)应该记为O(1)。
因此，上面这种，能用常数计数的算法复杂度，统统记为O(1)，称为常数阶。
线性阶：先看一段代码
int a,sum=0; //执行了1次
for(i=0,i<n,i++)
{
sum=sum+1; //循环体执行了n次
}
print("%d",sum); //执行了1次我们看到，函数f(n)=n+1+1，根据上一节的知识，常数可以忽略不计，于是1+1我们忽略不计，函数f(n)=n，因此，上面代码的时间复杂度为O(n)。
f(n)=n是线性函数，因此，这种形式的时间复杂度也被称为线性阶。
多项式阶：根据上一节的内容，我们有以下多项式的理论：
若f(n)=
+……+
是m次项多项式，则T(n)=O(
)。
看一段代码：
for(i=1;i<n;i++)
for(j=1;i<j;j++)
for(m=1;m<j;m++)
x=x+1;?为了更准确地分析，我们去掉了到代码中其他的元素，只拿出来关键的循环来分析。
x=x+1从一次循环中，我们执行了一次，从内到外函数f(n)便可以表示为：
根据多项式的理论，我们知道，这段代码的时间复杂度为O()。
这段代码我们可以看到，有时候，复杂度其实转化为了一个数学问题，只要有一定的数学基础，复杂度的计算并不难。
对数阶：下面的代码又该如何处理呢？
int i=1;
while(i<n)
{
i=i*2;
}运行1次：i=，在判断完i<n时候才结束；
运行2次：i=；
运行3次：i=；
……
运行x次：i=。
运行第x次便是i=n时，于是n=，解得：
。
通常，我们在算出并写对数复杂度时，把底数2或者其他数值省略，仅表明这是个对数便可以了，于是上面的代码时间复杂度为O()，这便是对数阶。
指数阶：简单举例一个代码
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
………………………………此处为时间复杂度为O(1)的代码
}
}通过上面多项式阶的计算，我们可以很快知道，这段代码的复杂度函数为，因此，这段代码的时间复杂度为O(
)。
当然常见的其他时间复杂度还有很多，我们整理为：
O(1)<O(
)<O(n)<O(
)<O(
)<O(
)<O(
)<O(n!)<O(
)
我们可以看到，从左向右，当到了O()时，当n稍微大一点，结果将是个大的数字，因此，在日常考试等设计中，一般我们最多用到?O(
)，当然，在实际操作中可能会用到更大的数量级。
综上，我们可以总结出分析时间复杂度的基本方法：
1、找出执行频度最多的那条语句作为基本语句；
2、根据找出来的基本语句得出规模n的某个函数f(n)；
3、算出数量级，用大O表示法表示出来。?
我们还可以得出：
时间复杂度是由嵌套最深层的语句的频度决定的。?
?当然，根据代码段有时候我们是不能直接计算运行次数的，如下面的代码段：
int findx(int x){ //在a[n]中数组中顺序查找x
for(int i=0;i<n;i++){
if(a[i]==x)
return i; //查找成功，返回其下标i
}
return -1; //查找失败，返回-1
}因为这个代码段中，运行次数依赖于数组a[n]中x所在的位置，如果在一个位置，那查找一次就能完成，如果在最后一个位置，那需要执行n次，如果按照概率中的平均来说，那需要次。因此有些算法，可能需要用最好、最差、平均时间复杂度来衡量，但是，对于实际运用有意义的是最坏时间复杂度。
以上便是时间复杂度的主要内容，下一节我们将一起学习空间复杂度和算法绪论中其他几个零散知识点。