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

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

admin2019-12-10  47
问题 设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，所以循环执行的次数是log2n，由此可见，算法的时间复杂度不是由问题规模n直接决定，而是log2n。
转载请注明原文地址:https://kaotiyun.com/show/ys3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)