В чем сложность этой программы. Это O (n)?

Question

Это простая программа, я хочу знать всю сложность этой программы. Я предполагаю, что это O (n), поскольку он имеет только одну операцию в цикле for.

a = int(input("Enter a:"))
b = int(input("Enter b:"))
sol = a
for i in range(a,b):
    sol = sol & i+1

print("\nSol",sol)   

Answer 1

Да, это O (n), вроде. Вы должны помнить, что O (n) означает, что количество операций увеличивается с размером ввода. Возможно, вас беспокоит операции & и (i + 1) в цикле for. Здесь нужно помнить, что эти операции являются постоянными, поскольку все они выполняются с 32-разрядным целым числом. Следовательно, единственным параметром, изменяющим продолжительность работы программы, является фактическое количество итераций цикла for.

Если вы предполагаете, что n = b - a, то эта программа O (n). На самом деле, если вы сломаете фактическое время выполнения:

за цикл: 1 операция И, 1 операция сложения теперь выполняем (b-a) итераций, поэтому 2 операции на цикл, (b-a) times = 2 * (b-a) Если мы предположим, что n = b-a, тогда это время выполнения становится 2 * n, что равно O (n).

Answer 2

Полагаю, вы определили n := b - a. Сложность на самом деле n log(n). В цикле всего 1 операция, поэтому сложность равна n * Time(operation in loop), но, поскольку i состоит из log(n) битов, сложность равна O(n log(n))

EDIT:

Я сейчас рассматриваю n := b. Это не влияет на мой исходный ответ, и это имеет больше смысла, поскольку это размер ввода. (Не имеет смысла говорить, что n=1 для какого-то большого a,a+1)

Чтобы сделать его более эффективным, обратите внимание, что вы вычислили (a)&(a+1)&(a+2)&..&(b).
Поэтому нам просто нужно установить 0 вместо 1 в двоичном представлении b во всех местах, где есть 0 в этом месте в представлении некоторого a <= k < b. Как мы можем узнать, установить ли цифру на 0 или нет? Я оставлю это вам:)
Можно сделать в log(n) раз, размер двоичного представления b.
Таким образом, в этом случае мы получаем, что время составляет O(log(n)^2) = o(n)