（时间管理）算法的时间复
杂度
时间复杂度：如果壹个问题的规模是 n，解这壹问题的某壹算法所需要的时间为 T(n)，它是
n 的某壹函数，T(n)称为这壹算法的“时间复杂度”。
渐近时间复杂度：当输入量 n逐渐加大时，时间复杂性的极限情形称
为算法的“渐近时间复杂度”。
当我们评价壹个算法的时间性能时，主要标准就是算法的渐近时间复
杂度，因此，于算法分析时，往往对俩者不予区分，经常是将渐近时
间复杂度 T(n)=O(f(n))简称为时间复杂度，其中的 f(n)壹般是算法
中频度最大的语句频度。
此外，算法中语句的频度不仅和问题规模有关，仍和输入实例中各元
素的取值关联。可是我们总是考虑于最坏的情况下的时间复杂度。以
保证算法的运行时间不会比它更长。
常见的时间复杂度，按数量级递增排列依次为：常数阶 O(1)、对数阶
O(log2n)、线性阶 O(n)、线性对数阶 O(nlog2n)、平方阶 O(n^2)、立
方阶 O(n^3)、k次方阶 O(n^k)、指数阶 O(2^n)。
下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。
1、 设 三 个 函 数 f,g,h分 别 为
f(n)=100n^3+n^2+1000,g(n)=25n^3+5000n^2,h(n)=n^+5000nlgn
请判断下列关系是否成立：
（1）f(n)=O(g(n))
（2）g(n)=O(f(n))
（3）h(n)=O(n^)
（4）h(n)=O(nlgn)
这里我们复习壹下渐近时间复杂度的表示法 T(n)=O(f(n))，这里的
"O"是数学符号，它的严格定义是"若 T(n)和 f(n)是定义于正整数集
合上的俩个函数，则 T(n)=O(f(n))表示存于正的常数 C和 n0,使得当 n
≥n0时均满足 0≤T(n)≤C?f(n)。"用容易理解的话说就是这俩个函
数当整型自变量 n趋向于无穷大时，俩者的比值是壹个不等于 0的常
数。这么壹来，就好计算了吧。
◆(1)成立。题中由于俩个函数的最高次项均是 n^3,因此当 n→∞时，
俩个函数的比值是壹个常数，所以这个关系式是成立的。
◆（2）成立。和上同理。
◆（3）成立。和上同理。
◆（4）不成立。由于当 n→∞时 n^比 nlgn递增的快，所以 h(n)
和 nlgn的比值不是常数，故不成立。
2、设 n为正整数，利用大"O"记号，将下列程序段的执行时间表示为
n的函数。
(1)i=1;k=0
while(i<n)
{k=k+10*i;i++;
}
解答：T(n)=n-1，T(n)=O(n)，这个函数是按线性阶递增的。
(2)x=n;//n>1
while(x>=(y+1)*(y+1))
y++;
解答：T(n)=n1/2，T(n)=O(n1/2)，最坏的情况是 y=0，那么循环的次
数是 n1/2次，这是壹个按平方根阶递增的函数。
(3)x=91;y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
elsex++;
解答：T(n)=O(1)，这个程序见起来有点吓人，总共循环运行了 1000
次，可是我们见到 n 没有?没。这段程序的运行是和 n无关的，就算
它再循环壹万年，我们也不管他，只是壹个常数阶的函数。
O(1)
Temp=i;i=j;j=temp;
之上三条单个语句的频度均为 1，该程序段的执行时间是壹个和问题
规模 n无关的常数。算法的时间复杂度为常数阶，记作 T(n)=O(1)。
如果算法的执行时间不随着问题规模 n的增加而增长，即使算法中有
上千条语句，其执行时间也不过是壹个较大的常数。此类算法的时间
复杂度是 O(1)。
O(n^2)
.交换 i和 j的内容
sum=0；（壹次）
for(i=1;i<=n;i++)（n次）
for(j=1;j<=n;j++)（n^2次）
sum++；（n^2次）
解：T(n)=2n^2+n+1=O(n^2)
.
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)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度 T(n)=O(n^2).
O(n)
.
a=0;
b=1;①
for(i=2;i<=n;i++)②
{
s=a+b;③
b=a;④
a=s;⑤
}
解：语句 1的频度：2,
语句 2的频度：n,
语句 3的频度：n-1,
语句 4的频度：n-1,
语句 5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).
O(log2n)
.
i=1;①
while(i<=n)
i=i*2;②
解：语句 1的频度是 1,
设语句 2的频度是 f(n),则：2^f(n)<=n;f(n)<=log2n
取最大值 f(n)=log2n,
T(n)=O(log2n)
O(n^3)
.
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)/6所以时间复杂度为
O(n^3).
我们仍应该区分算法的最坏情况的行为和期望行为。如快速排序的最
坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次均仔
细地选择基准值，我们有可能把平方情况(即 O(n^2)情况)的概率减小
到几乎等于 0。于实际中，精心实现的快速排序壹般均能以(O(nlogn)
时间运行。
下面是壹些常用的记法：
访问数组中的元素是常数时间操作，或说 O(1)操作。壹个算法如果能
于每个步骤去掉壹半数据元素，如二分检索，通常它就取 O(logn)时
间。用 strcmp比较俩个具有 n个字符的串需要 O(n)时间。常规的矩
阵乘算法是 O(n^3)，因为算出每个元素均需要将 n对元素相乘且加到
壹起，所有元素的个数是 n^2。
指数时间算法通常来源于需要求出所有可能结果。例如，n个元素的
集合共有 2n个子集,所以要求出所有子集的算法将是 O(2n)的。指数
算法壹般说来是太复杂了，除非 n的值非常小，因为，于这个问题中
增加壹个元素就导致运行时间加倍。不幸的是，确实有许多问题(如
著名的“巡回售货员问题”)，到目前为止找到的算法均是指数的。
如果我们真的遇到这种情况，通常应该用寻找近似最佳结果的算法替
代之。
壹个经验规则
有如下复杂度关系
c<log2N<n<n*Log2N<n^2<n^3<2^n<3^n<n!
其中 c是壹个常量，如果壹个算法的复杂度为 c、 log2N、 n、
n*log2N,那么这个算法时间效率比较高，如果是 2^n,3^n,n!，那么稍
微大壹些的 n就会令这个算法不能动了，居于中间的几个则差强人意。
