Вычислительная сложность

Question

Предположим, у нас есть функция ниже:

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

Хотя value_ может быть сколь угодно большим, цикл while не бесконечен, а число сравнений ограничено сверху value_.Следовательно, правильно ли, что эта функция имеет вычислительную сложность O (N)?

Answer 1

Это O(log n), так как x увеличивается удвоением значения до _value для каждого выполнения.Попробуйте нарисовать график из двух линий, вы увидите его.

Answer 2

Сложность времени будет O(log(m/n, 2)), где m = value_ и n = x.Здесь log(i, 2) представляет логарифмическое значение i в базе 2.

Учтите, что если удвоить x, то для фиксированного value_ вычисляется еще одна итерация.

Напротив, если value_ удвоено, для фиксированного x вычисляется одна дополнительная итерация.