时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)，其中n为问题规模。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数。如T(n)=4n^2+5n,或者8n^2+1,那么时间复杂度都为：O(n^2)，取最高幂，并去掉系数。
常见的时间复杂度有：常数阶O(1),对数阶O(logn),线性阶O(n), 线性对数阶O(nlogn),平方阶O(n^2)，立方阶O(n^3),...， k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。也就是从效率上来看，他们的优劣比较如下：
O(1)>O(logn)>O(nlogn)>O(n2)>O(n3)>O(2n)
在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（它的同数量级有以下：1，logn，n，n logn ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))
看看下面的程序时间复杂度：
int max(int x, int y)
{
return x>y?x:y;
}
该程序的基本操作为：x>y?x:y。每次执行一次。所以，它的时间复杂度为O(1)
再看看下面的程序的时间复杂度：
for (i=1;i<=n;++i)
{
for (j=1;j<=n;++j)
{
c[i][j]=0; //该步骤属于基本操作
执行次数：n的平方
for (k=1;k<=n;++k)
c[i][j] += a[i][k]*b[k][j]; //该步骤属于基本操作 执行次数：n的三次方
}
}
因此，T(n)=n^3+n^2
取表达式中次数最大的，并且去掉常数，因此时间复杂度为：O(n^3)
时间复杂度计算的一般方法是：看看有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)，依此类推，如果有二分则为O(logn)，二分例如快速排序、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)
按照该方法，那么下面的冒泡排序算法的时间复杂度为O（n2）
void bubblesort(int a[], int n)
{
int i, j, tmp;
for (i = 0; i < n-1; i++)
{
for (j = n-1; j >= i+1; j--)
{
if (a[j] < a[j-1])
{
tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
}
