A-A+

设n是描述问题规模的非负整数下面程序片段的时间复杂度是()。 int i=1： while

2022-08-07 16:22:31 问答库阅读 182 次

问题详情

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是()。
int i=1：
while(i<=n)
i=i*2：
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)请帮忙给出正确答案和分析，谢谢！

正确答案：A
解析：这是一个比较有趣的问题。如果不仔细分析的话，可能会得到O(n)的结果。
关键在于分析出while语句执行的次数。由于循环体中，i=i*2，所以循环执行的次数是log₂n，由此可见，算法的时间复杂度不是由问题规模n直接决定，而是log₂n。