Как узнать временную и пространственную сложность следующего моментального снимка?

Question

Я понимаю, как работает код в следующем снимке, но мне любопытно, как я узнаю его временную и пространственную сложность?

Я знаю, что это зависит от времени, которое требуется для того, чтобы «b» стало нулевым. Есть ли какой-то математический способ, которым я могу это найти? Я понимаю, что это не пойдет на миллионы рекурсий. Но все же было любопытно, сколько будет рекурсий?

Вопрос: Добавить 2 цифры без использования арифметики осуществления операций

Answer 1

Поскольку перенос - это & b, сдвинутый влево, его бит-0 (младший бит или младший бит) равен нулю. Кроме того, перенос будет иметь нуль в каждой позиции p, где b имеет нуль в позиции p-1. Это означает, что в первом рекурсивном вызове b будет иметь нулевой бит-0, а во втором рекурсивном вызове он будет иметь нуль в бит-0 и бит-1 (2 младших разряда равны нулю) и так далее. В n-м рекурсивном вызове b будет иметь n LSB, которые равны 0, поэтому, когда n является позицией самого значимого ненулевого бита в a, перенос будет равен нулю, и рекурсия закончится при следующем вызове.

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

Answer 2

Это как пульсация кэрри сумматор (но это волшебно «знает», когда выход стабилен и взять ранний выход). С каждым шагом перенос будет иметь строго возрастающее положение младшего бита набора (бесконечность, если нет младшего установленного бита). Таким образом, он может регенерировать не более одного раза за каждый бит. Сколько времени/пространства, которое представляет, зависит от ваших предположений (принимая количество бит в качестве константы, дает бесполезные результаты, которые мешают вам сравнивать его с альтернативными реализациями).

Это явно хвостовой вызов, и его можно переписать в виде цикла, так что вы могли бы сказать, что это занимает меньше места, чем если бы вы притворились, что на самом деле использовали все это пространство стека.

Кроме того, это возможно сделать в ряде шагов, логарифмических в количестве бит, аналогично сумматору Kogge-Stone.