结构推理
一个算法运行规模为n的输入。如果n=4096，运行时间为512ms；如果n=16384，运行时间为1024ms。计算这个算法的复杂度，并用大O表示法来描述。
【正确答案】
由题意可知：
n
1
=4096，f(n
1
)=512；n
2
=16384，f(n
2
)=1024。
因为n
2
=4n
1
，则有f(n
2
)=2f(n
1
)，
所以时间代价对输入呈平方根增长，即T(n)=O(n
1/2
)。
【答案解析】
提交答案
关闭