（时间管理）算法的时间复杂度

1、（时间管理）算法的时间复杂度10 / 10时间复杂度：如果壹个问题的规模是 n,解这壹问题的某壹算法所需要的时间为 T(n),它是n 的某壹函数,T(n)称为这壹算法的“时间复杂度”。渐近时间复杂度：当输入量 n 逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂度”。当我们评价壹个算法的时间性能时,主要标准就是算法的渐近时间复杂度,因此,于算法分析时,往往对俩者不予区分,经常是将渐近时间复杂度 T(n)=O(f(n)简称为时间复杂度,其中的 f(n)壹般是算法中频度最大的语句频度。此外,算法中语句的频度不仅和问题规模有关,仍和输入实例中各元素的取值关联。可是我们总是考虑于最坏的情况下的

2、时间复杂度。以保证算法的运行时间不会比它更长。常见的时间复杂度,按数量级递增排列依次为：常数阶 O(1)、对数阶O(log2n)、线性阶 O(n)、线性对数阶 O(nlog2n)、平方阶 O(n2)、立方阶 O(n3)、k 次方阶 O(nk)、指数阶 O(2n)。下面我们通过例子加以说明,让大家碰到问题时知道如何去解决。1 、 设 三 个 函 数 f,g,h 分 别 为f(n)=100n3+n2+1000,g(n)=25n3+5000n2,h(n)=n1.5+5000nlgn 请判断下列关系是否成立：（1）f(n)=O(g(n)（2）g(n)=O(f(n)（3）h(n)=O(n1.5)（4）h

3、(n)=O(nlgn)这里我们温习壹下渐近时间复杂度的表示法 T(n)=O(f(n),这里的"O"是数学符号,它的严格定义是"若 T(n)和 f(n)是定义于正整数集合上的俩个函数,则 T(n)=O(f(n)表示存于正的常数 C 和 n0,使得当 nn0 时均满足 0T(n)C?f(n)。"用容易理解的话说就是这俩个函数当整型自变量 n 趋向于无穷大时,俩者的比值是壹个不等于 0 的常数。这么壹来,就好计算了吧。 (1)成立。题中由于俩个函数的最高次项均是 n3,因此当 n时, 俩个函数的比值是壹个常数,所以这个关系式是成立的。（2）成立。和上同理。（3

4、）成立。和上同理。 （4）不成立。由于当 n时 n1.5 比 nlgn 递增的快,所以 h(n)和 nlgn 的比值不是常数,故不成立。2、设 n 为正整数,利用大"O"记号,将下列程序段的执行时间表示为n 的函数。(1)i=1;k=0while(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

5、)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 的增加而增长,即使算法中有上千条语句,其执行时间也不过是壹个较大的常数。此类

6、算法的时间复杂度是 O(1)。O(n2)2.1.交换 i 和 j 的内容sum=0；（壹次）for(i=1;i<=n;i+)（n 次）for(j=1;j<=n;j+)（n2 次）sum+；（n2 次）解：T(n)=2n2+n+1=O(n2) 2.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)=2n2-n-1 f(n)=2n2-n-1+(n-1)=2n2-2该程序的时间复杂度 T(n)=O(n2). O(n)2.3. a=0;b=1; for(i=2;

7、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) 2.4.i=1; while(i<=n) i=i*2;解：语句 1 的频度是 1,设语句 2 的频度是 f(n),则：2f(n)<=n;f(n)<=log2n取最大值 f(n)=log2n, T(n)=O(log2n) O(n3)2.5.for(i=0;i<n;i+)for(j=0;j<i;j+)for(k=0;

8、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(n3).我们仍应该区分算法的最坏情况的行为和期望行为。如快速排序的最坏情况运行时间是 O(n2),但期望时间是 O(nlogn)。通过每次均仔细地选择基准值,我们有可能把平方情况(即 O(n2)情况)的概率减小到几乎等于 0。于实际中,精心实现的快速排序壹般均能

9、以(O(nlogn) 时间运行。下面是壹些常用的记法：访问数组中的元素是常数时间操作,或说 O(1)操作。壹个算法如果能于每个步骤去掉壹半数据元素,如二分检索,通常它就取 O(logn)时间。用 strcmp 比较俩个具有 n 个字符的串需要 O(n)时间。常规的矩阵乘算法是 O(n3),因为算ft每个元素均需要将 n 对元素相乘且加到壹起,所有元素的个数是 n2。指数时间算法通常来源于需要求ft所有可能结果。例如,n 个元素的集合共有 2n 个子集,所以要求ft所有子集的算法将是 O(2n)的。指数算法壹般说来是太复杂了,除非 n 的值非常小,因为,于这个问题中增加壹个元素就导致运行时间加倍。不幸的是,确实有许多问题(如著名的“巡回售货员问题”),到目前为止找到的算法均是指数的。如果我们真的遇到这种情况,通常应该用寻找近似最佳结果的算法替代之。壹个经验规则有如下复杂度关系c<log2N<n<n