假设我们有以下函数:
def func(x, value_):
assert 0 < x < value_
while x < value_:
x *= 2
尽管
value_
可以是任意大的,但 while 循环不是无限的,并且比较的次数在 value_
之上。因此,该函数的计算复杂度为 O(N) 是否正确? 最佳答案
它是 O(log n)
,因为每次执行时 x
通过将值加倍到 _value
来增加。尝试绘制两条线的图形,您会看到它。