Является ли этот алгоритм подсчета количества установленных битов в натуральном, n, O (1) или O (log n) времени?

Question

Есть 2 способа вычислить количество установленных бит в целом числе, n, которое я проиллюстрирую ниже. Есть также O (1) способ, который зависит от платформы, но это не относится к этому вопросу.

2 способа:

int count = 0;
while(n)
{
  count++;
  n &= n - 1;
}

int count = 0;
while(n)
{
  if(n & 1) count++;
  n >>= 1;
}

Для любого 32-разрядного целого числа, оба цикла будут выполняться максимум 32 раза, где каждый l oop выполняет O (1). Так что это звучит так, как если бы алгоритм выполнялся за O (1) раз в области 32-битных целых чисел. Но мы также можем сформулировать это, поскольку число циклов равно log (n), которое ограничено 32, но это выражение предполагает, что алгоритм зависит от входных данных и выполняется за время O (log n), но верхняя граница по-прежнему является константой.

Правильнее ли говорить, что эти алгоритмы работают за O (1) или O (log n)?

Answer 1

Ни один из них не является O (1). Вы накладываете ограничение на размер ввода, когда говорите, что верхняя граница фиксирована. Существуют числа, намного превышающие 32 бита.

Время, необходимое алгоритму для вычисления выходных данных, прямо пропорционально размеру входных данных, т.е. n

Пример O (1) al go - это сумма первых n натуральных чисел, т.е. n * (n + 1) / 2

Здесь, даже если n становится больше, число требуемых вычислений остается постоянным - и, следовательно, O (1).

Answer 2

Эти циклы выполняются каждый раз за время O (log n). Вы можете сделать еще более жесткое утверждение для первого и сказать, что оно выполняется за время O (b), где b - количество битов, установленных в числе. Случается, что b = O (log n), потому что число n требует O (log n) битов для записи.

Говорить о времени выполнения алгоритмов, обрабатывающих числа, всегда немного рискованно по одному, потому что у вас есть две вещи в напряжении друг с другом. Одним из них является то, что в математическом смысле число бит в числе растет логарифмически с величиной числа. То есть количество битов в числе n равно O (log n). С другой стороны, на реальных машинах существует фиксированное ограничение на число бит в числе, из-за чего время выполнения «должно» быть константой, поскольку вы не можете иметь неограниченно большие значения n.

Одна ментальная модель, которую я нахожу здесь полезной, состоит в том, чтобы подумать о том, что на самом деле означало бы неограниченный рост n. Если у вас есть 45-битное число, я предполагаю, что вы либо

1. работаете в 64-битной системе, либо
2. работаете в 32-битной системе и используете несколько 32-разрядных целых чисел для сборки вашего 45-разрядного числа.

Если мы сделаем предположение (1), то мы неявно говорим, что по мере того, как наши числа становятся все больше и больше, мы движемся к большему и большие машины размера слова. (Это может быть формализовано как модель трандихотомной машины ). Если мы сделаем предположение (2), то мы предполагаем, что наши числа не обязательно вписываются в машинное слово, и в этом случае число битов не является константой. Для этого нужно ввести другой параметр w, указывающий размер машинного слова, а затем выполнить анализ в терминах w. Например, мы можем сказать, что время выполнения обоих алгоритмов равно O (w). Это устраняет зависимость от n, что может переоценить проделанную работу.

Надеюсь, это поможет!