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