结构推理
如果doIt这个算法的复杂度为n
2
，那么计算下面这个程序段的时间代价：
inti=1;
while(i＜=n){
intj=1;
while(j＜=n){
doIt(…);
j=j+1;
}
i=i+1;
}
【正确答案】
循环控制变量i从1增加到n，外层循环体执行n次，循环控制变量j从1增加到n，内层循环体执行n-1次，所以该程序段总的时间代价为：
T(n)=1+n+n{1+n+(n-1)(n
2
+1)+1}+n+1
=n
4
-n
3
+2n
2
+3n+2
=O(n
4
)
【答案解析】
提交答案
关闭