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

admin2019-07-18 38

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

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

答案A

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

转载请注明原文地址:https://jikaoti.com/ti/PnGjFFFM

计算机408

相关试题推荐

随机试题

最新回复(0)