下列程序段的时间复杂度是_______。 count=0； for(k=1，k＜=n；k*=2) for(j=1，j＜=n，j++) count++；

admin2015-12-30 51

问题下列程序段的时间复杂度是_______。
count=0；
for(k=1，k＜=n；k*=2)
for(j=1，j＜=n，j++)
count++；

选项 A、O(log₂n)
B、O(n)
C、O(nlog₂n)
D、O(n²)

答案C

解析内层循环条件j＜=n与外层循环的变量无关，每次循环j自增1，每次内层循环都执行n次。
外层循环条件为k＜=n，增量定义为k*=2，可知循环次数为2^k＜=n，即k＜=log2n。所以内层循环的时间复杂度是O(n)，外层循环的时间复杂度是O(log2n)。对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度T(n)=T₁(n)*T₂(n)=O(n)*O(log₂n)=O(nlog₂n)，选C。

转载请注明原文地址:https://kaotiyun.com/show/h7xi777K

本试题收录于：计算机408题库学硕统考专业分类