Какой из них является более быстрым методом для подсчета количества единиц?

Question

Предположим, я хочу посчитать число 1 в двоичном числе n в Python
, затем я могу сделать это, используя следующие два метода:

def count_ones(n):
    count=0
    while n>0:
        count+=n&1
        n=n>>1
    return count

или я могу сначала преобразовать данное число в двоичном виде и затем считать 1 как

bin(n).count('1')

Какой путь лучше (с точки зрения сложности времени) и почему?

Answer 1

Временная сложность первой функции составляет O (log n), потому что именно столько бит требуется для представления n в двоичном формате, а bin(n) и .count('1') требуют линейного времени в количестве бит.

Временная сложность второй функции равна O (log ² n), потому что l oop повторяет O (log n) раз и сдвиг битов n >> 1 внутри l oop занимает O (журнал N) время. То есть число итераций является линейным по количеству битов, а сдвиг занимает линейное время по числу битов.

Таким образом, временная сложность первой функции ниже.