问答题
分析以下各程序段的时间复杂度。
问答题
void main()
{
int i=1,k=0,n=10;
while(i＜=n-1)
{
k+=10*i;
++i;
}
}
【正确答案】O(n)
【答案解析】
问答题
void main()
{
int i=1,k=0,n=100;
do
{
k+=10*i;++i;
} while(i==n);
}
【正确答案】O(1)
【答案解析】
问答题
void main()
{
int i=1,j=0,n=10;
while(i+j＜=n)
if(i＞j)
++j;
else
++i;
}
【正确答案】O(n)
【答案解析】
问答题
void main()
{
int n=10,x=n,y=0;
while(x＞=(y+1)*(y+1))
++y;
}
【正确答案】[*]
【答案解析】
问答题
void main()
{
int n=9,i=1;
while(i＜=n)
i=i*3;
}
【正确答案】O(log3n)
【答案解析】[解析] 设执行k次，则有3k+C=n(其中C是起到修正作用的常数)，即k=log3(n-C)。
log3(n-C)与log3n同数量级，因此复杂度为O(log3n)。
log3(n-C)与log3n同数量级，因此复杂度为O(log3n)。
问答题
分析以下程序段的时间复杂度。
...
i=1;
while(i＜=n)
i=i*2;
...
【正确答案】此处循环体里面是i=i*2，即每循环一次，i值增加一倍，所以执行次数与n之间是以2为底的对数关系，故时间复杂度为O(log2n)。
【答案解析】
问答题
假设n为2的乘幂，如n=2，4，8，16，…试求下列程序的时间复杂度及变量count的值(以n的函数形式表示)。
void counter()
{
int n,x,count;
cout＜＜"n: ";
cin＞＞n;
count=0;
x=2;
while(x＜n/2)
{
x=2*x;
++count;
}
cout＜＜count＜＜endl;
}
【正确答案】n与count的关系如下：
当n=20时，count=0；当n=21时，count=0；当n=22时，count=0；当n=23时，count=1；当n=24时，count=2，…；当n=2m时，count=m-2。则本算法的时间复杂度为O(log2n)。count=log2n-2。
当n=20时，count=0；当n=21时，count=0；当n=22时，count=0；当n=23时，count=1；当n=24时，count=2，…；当n=2m时，count=m-2。则本算法的时间复杂度为O(log2n)。count=log2n-2。
【答案解析】
问答题
某算法所需时间由下述方程表示，试求出该算法的时间复杂度(以大O形式表示)。注意，n为求解问题的规模，为简单起见，设n是2的正整数幂。
【正确答案】设n=2m，则
T(n)=T(2m)=2T(2m-1)+2m
=2(2T(2m-2)+2m-1)+2m=22×T(2m-2)+2×2m
[*]
=2m×T(1)+m×2m
=(m+1)2m
=(log2n+1)n
=O(nlog2n)
T(n)=T(2m)=2T(2m-1)+2m
=2(2T(2m-2)+2m-1)+2m=22×T(2m-2)+2×2m
[*]
=2m×T(1)+m×2m
=(m+1)2m
=(log2n+1)n
=O(nlog2n)
【答案解析】
问答题
分析order函数的时间复杂度。
order(int j,int n)
{
int i,temp;
if(j＜n)
{
for(i=j;i＜=n; ++i)
if(a[i]＜a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
++j;
order(j,n); //递归调用
}
}
【正确答案】order()函数是一个递归排序过程，设T(n)是排序n个元素所需要的时间。在排序n个元素时，算法的计算时间主要花费在递归调用order()上。在第一次调用时，处理的元素序列个数为n-1，也就是对余下的n-1个元素进行排序，所需要的计算时间应为T(n-1)。又因为在其中的循环中，需要n-1次比较，所以排序n个元素所需要的时间为
T(n)=T(n-1)+n-1，n＞1
可以得到如下方程：
T(1)=0
T(n)=T(n-1)+n-1，n＞1
求解过程为
T(n)=[T(n-2)+(n-2)]+(n-1)
=[T(n-3)+(n-3)]+(n-2)+(n-1)
[*]
=(T(1)+1)+2+…+n-1
=0+1+2+…+n-1
=n(n-1)/2
=O(n2)
所以order函数的时间复杂度为O(n2)。
T(n)=T(n-1)+n-1，n＞1
可以得到如下方程：
T(1)=0
T(n)=T(n-1)+n-1，n＞1
求解过程为
T(n)=[T(n-2)+(n-2)]+(n-1)
=[T(n-3)+(n-3)]+(n-2)+(n-1)
[*]
=(T(1)+1)+2+…+n-1
=0+1+2+…+n-1
=n(n-1)/2
=O(n2)
所以order函数的时间复杂度为O(n2)。
【答案解析】