O (1) установить счетчик бит

Question

Я просматривал эту страницу подсчета битов: https://www.geeksforgeeks.org/count-set-bits-in-an-integer/

Последний алгоритм Отображение чисел с битом говорит: Он просто поддерживает Map ( или массив) чисел в биты для полубайта. Полубайт содержит 4 бита. Итак, нам нужен массив до 15.

int num_to_bits[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};

Теперь нам просто нужно рекурсивно получить полубайты заданного long / int / word et c.

num_to_bits =[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];  

# Recursively get nibble of a given number  
# and map them in the array 
def countSetBitsRec(num): 
    nibble = 0; 
    if(0 == num): 
        return num_to_bits[0]; 

    # Find last nibble 
    nibble = num & 0xf; 

    # Use pre-stored values to find count 
    # in last nibble plus recursively add 
    # remaining nibbles. 

    return num_to_bits[nibble] + countSetBitsRec(num >> 4);  

num = 31
from timeit import default_timer as timer
t1 = timer()
print(countSetBitsRec(num))
t2 = timer()
print(t2-t1)
num = 421342356246244235625423523626342453143523624526434636546745745634523546346346346346344506546456909546540964596956306030963068359683578753068340634960340683463906835096835068309683486036830563596
t1 = timer()
print(countSetBitsRec(num))
t2 = timer()
print(t2-t1)

t1 = timer()
print(bin(num).count('1'))
t2 = timer()
print(t2-t1)

5
0.00013369599992074654
335
0.00015420899990203907
335
0.00011028399990209437

В разделе временной сложности говорится, что это O (1) как по времени, так и по памяти. Несмотря на то, что время для обоих целых чисел близко, я не могу понять, как это O (1), поскольку он выполняет рекурсивные вызовы?

Answer 1

Сложность памяти показана O(1) на основе того факта, что он использует фиксированный массив (но есть много рекурсивных вызовов, и эта память не будет O (1)).

Временная сложность не O(1), каждый раз nibble = num & 0xf; это дает целое число меньше 15 (0xf равно 15, а операция & гарантирует, что результат не больше 15). Затем он рекурсивно использует эти индексы для полубайта.

Мы можем рассчитать шаги для обоих чисел для сравнения; если время выполнения равно O(1), количество шагов должно быть таким же.

num_to_bits =[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];  

# Recursively get nibble of a given number  
# and map them in the array 

num_steps = 0
def countSetBitsRec(num): 
    global num_steps
    num_steps += 1
    nibble = 0; 
    if(0 == num): 
        return num_to_bits[0]; 

    # Find last nibble 
    nibble = num & 0xf; 

    # Use pre-stored values to find count 
    # in last nibble plus recursively add 
    # remaining nibbles. 

    return num_to_bits[nibble] + countSetBitsRec(num >> 4);  

num = 31
from timeit import default_timer as timer
t1 = timer()
print(countSetBitsRec(num))
print(f'num steps: {num_steps}')
t2 = timer()
print(t2-t1)
num = 421342356246244235625423523626342453143523624526434636546745745634523546346346346346344506546456909546540964596956306030963068359683578753068340634960340683463906835096835068309683486036830563596
global num_steps
num_steps = 0
t1 = timer()
print(countSetBitsRec(num))
print(f'num steps: {num_steps}')
t2 = timer()
print(t2-t1)

5
num steps: 3
0.00024106499995468766
335
num steps: 163
0.0012161659999492258

Как видите, количество шагов напрямую зависит от самого целочисленного размера. Для больших целых чисел число пропорционально длине, а не O(1).