关于时间复杂度：
“O”的定义：若f(n)是正整数n的一个函数，则O(f(n))表示$M≥0 ，使得当n ≥ n0时，| f(n) | ≤M| f(n0)| 。
表示时间复杂度的阶有：
O(1) ：常量时间阶 O (n)：线性时间阶
O(㏒n) ：对数时间阶 O(n㏒n)：线性对数时间阶
O (nk)：k≥2，k次方时间阶
例１ 两个n阶方阵的乘法
for(i=1，i<=n;++i)
for(j=1; j<=n; ++j)
{ c[i][j]=0 ;
for(k=1; k<=n;++k)
c[i][j]+=a[i][k]*b[k][j]; }
由于是一个三重循环，每个循环从1到n，则总次数为：n×n×n=n3 时间复杂度为T(n)=O(n3)
例２ {++x; s=0 ;}
将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)。
如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。
例３ for(i=1;i<=n; ++i)
{ ++x; s+=x ; }
语句频度为：2n，其时间复杂度为：O(n)，即为线性阶。
例４ for(i=1;i<=n; ++i)
for(j=1;j<=n; ++j)
{ ++x; s+=x ; }
语句频度为：2n2，其时间复杂度为：O(n2)，即为平方阶。
定理：若A(n)=a m nm+a m-1n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m)
例５ for(i=2;i<=n;++i)
for(j=2;j<=i-1;++j)
{++x; a[i,j]=x;}
语句频度为： 1+2+3+…+n-2=(1+n-2)×(n-2)/2
=(n-1)(n-2)/2 =n2-3n+2
∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。
以下六种计算算法时间的多项式是最常用的。其关系为：
O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)
O(2n)<O(n!)<O(nn)
当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。