Большой O этой функции степени двойки

Что такое «большой O» следующей функции? Я предполагаю, что это O (log (n)), но я хотел бы перепроверить. Функция просто определяет, является ли ее аргумент степенью числа 2.

def pow_of_2(x):
    a = math.log(x, 2)
    if a == math.floor(a):
       return True
    else:
       return False

python time-complexity big-o
person user3121369    schedule 19.01.2016    source источник
comment
Похоже, что это O(1), потому что он выполняет фиксированные вычисления, а затем возвращает либо True, либо False.   -  person Tim Biegeleisen    schedule 19.01.2016
comment
но разве вычисление не является переменной, основанной на x @TimBiegeleisen   -  person user3121369    schedule 19.01.2016
comment
Функция имеет вид O(log(x)) (поскольку преобразование x в двойное значение равно O(log x)), но также дает неверные результаты для больших x. Например, pow_of_2(2 ** 1000) возвращает False.   -  person Paul Hankin    schedule 19.01.2016
comment
Я думаю, вы запутались в анализе времени выполнения. Функция просто вычисляет журнал и затем возвращается. Это постоянный штраф. Если бы у вас была петля или структура другого типа, время работы не было бы постоянным.   -  person Tim Biegeleisen    schedule 19.01.2016
comment
Я с Тимом. О (1). Не имеет смысла, чтобы это было что-то еще, поскольку в задаче нет ничего, что было бы n. Есть одна скалярная переменная (x), и вы выполняете с ней только фиксированное количество операций (независимо от того, какое значение имеет x).   -  person mgilson    schedule 19.01.2016
comment
Я подозреваю, что ОП спрашивает о сложности с точки зрения x, то есть как удвоение x повлияет на время возврата функции. На этот вопрос невозможно ответить, не зная точно, как математическая библиотека вычисляет логарифмическую функцию. Однако, как правило, чем больше x, тем больше время, но с ростом x этот штраф будет уменьшаться. Это, конечно, не так плохо, как O(x), но определенно хуже, чем O(1). Я подозреваю, что O (log (x)), вероятно, близко. Запуск функции много раз для больших x предполагает, что время асимптотически пропорционально log(x).   -  person Matthew    schedule 19.01.2016

Ответы (1)


arrow_upward
5
arrow_downward

Big-O функции не является постоянным временем.

Big-O функции будет таким же, как Big-O функции math.log. Это в основном зависит от реализации функции. (Функция math.floor может быть реализована за постоянное время).

Функция log обычно вычисляется с использованием разложения в ряд Тейлора и равна O(M(n) * n^0.5), где M(n) — сложность умножения двух n-значных чисел.

Для получения дополнительной информации об этом перейдите по этой ссылке.

Примечание. Если вы хотите проверить, является ли число степенью 2, все, что вам нужно сделать, это выполнить следующую проверку с помощью двоичной арифметики.

def pow_of_2(x): вернуть ((x & (x - 1)) == 0)

В основном вам нужно проверить, установлен ли ровно один бит в 1 в двоичном представлении. Более подробное объяснение того, как это работает, здесь.

person user1952500    schedule 19.01.2016