x=x-10;y--;} 解析 y=100;//1 hile(y>0)//1101 if(x>100)//110 x=x-10;//100 y-;//100 e⊥se x++;//1000 以上程序段右侧列出了执行次数。该程序段的执行时间为: T(n)=0(1) 三.按增长率由小至大的顺序排列下列各函数 2,(3/2),(2/3)",n,n°5,n!,2",1gn,n,n 解答: 常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶 0(logn)、线性阶0(m)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k 次方阶0(n)、指数阶0(2)。 先将题中的函数分成如下几类: 常数阶:20 对数阶:1gn K次方阶:n5、n2 指数阶(按指数由小到大排):n、(3/2)"、2"、n!、n" 注意:(2/3)由于底数小于1,所以是一个递减函数,其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下: (2/3)°<21<1gn<n0<n<n<(3/2)"<2<n!<n{x=x-10;y--;} else x++; 解析： x=91; //1 y=100; //1 while(y>0) //1101 if(x>100) //1100 { x=x-10; //100 y--; //100 } else x++; //1000 以上程序段右侧列出了执行次数。该程序段的执行时间为： T(n)=O(1) 三. 按增长率由小至大的顺序排列下列各函数： 2 100, (3/2)n，(2/3)n， n n ,n 0.5 , n! ，2 n ，lgn ,nlgn , n (3/2) 解答： 常见的时间复杂度按数量级递增排列,依次为:常数阶 0(1)、对数阶 0(log2n)、线性阶 0(n)、线性对数阶 0(nlog2n)、平方阶 0(n2 )、立方阶 0(n3 )、k 次方阶 0(nk )、指数阶 0(2n )。 先将题中的函数分成如下几类： 常数阶：2 100 对数阶：lgn K 次方阶：n 0.5、n (3/2) 指数阶 (按指数由小到大排)：n lgn、(3/2)n、2 n、 n!、 n n 注意：(2/3)^n由于底数小于 1，所以是一个递减函数，其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下： (2/3)n < 2100 < lgn < n0.5 < n(3/2) < nlgn < (3/2)n < 2n < n! < nn