python - 计算复杂度

假设我们有以下函数:

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

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

最佳答案

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