计算机二级
下面这个程序段的时间复杂度是( )。 for (i=1；i＜n；i++) { y=y+1； for (j=0；j＜=(2*n)；j++) x++； }A．O(log2n)B．O(n)C．O(nlog2n)D．O(n2)
题目
下面这个程序段的时间复杂度是( )。 for (i=1；i＜n；i++) { y=y+1； for (j=0；j＜=(2*n)；j++) x++； }
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
相似问题和答案
第1题：
以下程序运行后的输出结果是【13】。
include<stdio．h>
main()
{ int n[2]，i，j；
for(i=0；i<2；i++)n[i]=0；
for(i=0；i<2；i++)
for(j=0；j<2；j++)n[j]=n[i]+1；
printf("％d＼n"，n[1])；
}
3 解析：该题先是初始化数组n[2]中的元素全部赋值为0，然后执行两层for循环，当i=0，j=0，a[0]为1、a[1]为0，当j=1时，a[0]为1、a[1]为2；当i=1，j=0，a[0]为3、a[1]为2，当i=1，j=1时，a[0]为3、a[1]为3。
第2题：
执行下面程序段，语句3的执行次数为______。 for(i=0;i＜n-1;i++) for(j=n;j＞i;j++) state;
A．n(n+2)/2
B．(n-1)(n+2)/2
C．n(n+1)/2
D．(n-1)(n+2)
解析：本题考查如何衡量算法的复杂度，根据题目可以看出，两层循环每次执行的次数是不相等的，第一次循环执行了n次，第二次循环只执行了n-1次，直到最后一次循环，他执行了2次，这样就是一个等差数列的求和，可得到总的执行次数为(n-1)(n+2)/2。
第3题：
有以下程序
main()
{ int i,j,x=0;
for(i=0;i<2;i++)
{ x++;
for(j=0;j<=3;j++)
{ if(j ％ 2) continue;
x++;
}
x++;
}
printf("x= ％ d\n",x);
}
程序执行后的输出结果是
A)x=4
B)x=8
C)x=6
D)x=12
(32)B) 解析 : 此程序考察了 for 循环和 x++ 。 对于大循环 , 有两个 x++, 其中循环 3 次 , 对于小循环 , 循环三次 , 但是运行了两次 x++, 所以最后结果是 6+2=8 。
第4题：
下面程序段的时间复杂度为 ( ) for(i=0;i＜m;i++) for(j=0;j＜n;j++) A[i][j]=i*j;
A．O(m2)
B．O(n2)
C．O(m*n)
D．O(m+n)
解析：此程序的时间复杂度即为程序中循环次数的时间耗费。由程序为嵌套循环，外层循环的时间复杂度T(n1)=m，内层循环的时间复杂度T(n2)=n，则此程序的时间复杂度T(n)=m*n，即为0(m*n)。
第5题：
阅读下列函数说明和C代码，填入(n)处。
[说明]
以下C语言程序实现了生成从里到外是连续的自然数排列的回旋矩阵，矩阵形式如下：
7 6 5 16
8 1 4 15
9 2 3 14
10 11 12 13
程序的变量说明如下：
x1：矩阵上边界；
x2：矩阵下边界；
y1：矩阵左边界；
y2：矩阵右边界；
s：数组元素升降标记，s等于1为升，s等于-1为降；
a[]：存放矩阵元素的数组。
仔细阅读C语言程序源码，将(n)处的语句补充完整。(注：每处仅一个语句)
[C程序]
include＜stdio.h＞
void main ( )
{
const int N=20;
int i=0,j=0,a[N][N],n;
int m,x1,x2,y1,y2,s;
while (1)
{
Printf ("\ninput matrix row N( N＞=2): ");
scanf ("%d",&n);
printf ("\n");
if (n＞=2)
break;
}
m=n*n;
x1=0; y1=0; x2=n; y2=n;
if(n%2==0)
{j=n-1; y2=n-1; s=1;}
else
{i=n-1; y1=1; s=-1; }
while (1)
{
if (s==1)
{
for (i; i＜x2; i++) a[i][j]=m--;
i--;
j--;
(1)
for (j;j＞=y1;j--) a[i][j]=m--;
j++;
i--;
y1++;
(2)
}
else
{
for (i;i＞=x1;i--)
a[i][j]=m--;
i++;
j++;
(3)
for (j;j＜y2;j++)
(4)
(5)
i++;
(6)
S=i;
}
if (m＜1) break;
}
for (i=O;i＜n; i++)
{
for (j=O;j＜n;j++)
printf ("%6d",a[i][j]);
printf ("\n");
}
printf ("\n");
}
(1)x2--; (2)s=-1; (3)x1++; (4)a[i][j]=m--; (5)j--; (6)y2--; 解析：自然数排列的回旋矩阵是一个经典程序设计题目。本题中生成的是一个从里到外是连续的自然数排列的回旋矩阵。仔细阅读代码，能够发现(1)处应该为矩阵下边界递减；(2)处应该为数组元素递减状态，即为降；(3)处应该为矩阵上边界递增；(4)处应该为存放矩阵元素的数组中的数据递减；(5)处应该为数组元素的列序号递减，即j--；(6)矩阵右边界递减。
第6题：
下面这个程序段的时间复杂度是( )。 for (i=1; i＜n; i++) { y=y+3; for (j=0;j＜=(2*n);j++) x++; }
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
解析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。在本例算法中，语句①的频度是n-1，语句②的频度是(n-1)(2n+1)-2n2-n-1。则该程序段的时间复杂度是T(n)=n-1+2n2-n-1=O(n2)。
第7题：
以下程序的输出结果是______。main(){ int i，j，x=0； for (i=0；i＜2；i++) { x++； for(j=0；j＜3；j++) { if(j%2) continue； x++； } x++； } printf("x=%d\n"，x)；}
A．x=4
B．x=8
C．x=6
D．x=12
第8题：
A、O(n)
B、O(m+n+1)
C、O(m+n)
D、O(m*n)
第9题：
以下程序的执行结果是______。 main() { int i，j，m=O，n=0； for (i=0；i＜2；i++) {for (j=0；j＜2；j++) if(j＞=i) m=1；n++； printf("%d\n"，n)； } }
A．4
B．2
C．1
D．0
第10题：
下面这个程序段的时间复杂度是( )。 for (i=1； i＜n； i++) { y=y+1； for (j=0；j＜=(2*n)；j++) X++； }
A．O(log2n)
B．O(n)
C．0(nlog2n)
D．O(n2)
解析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。在本例算法中，其中语句“y=y+1；”的频度是n-1，语句“x++；”的频度是(n-1)(2n+1)=2n2-n-1，则该程序段的时间复杂度是T(n)=n-1+2n2-n-1=O(n2)。