假设我们有以下函数:

def func(x, value_):
    assert 0 < x < value_
    while x < value_:
        x *= 2

尽管 value_ 可以是任意大的,但 while 循环不是无限的,并且比较的次数在 value_ 之上。因此,该函数的计算复杂度为 O(N) 是否正确?

最佳答案

它是 O(log n),因为每次执行时 x 通过将值加倍到 _value 来增加。尝试绘制两条线的图形,您会看到它。

10-07 17:49