algorithm - 如何知道以下快照的时间和空间复杂度？

Question

我了解以下快照中的代码是如何工作的，但我很好奇我如何知道它的时间和空间复杂度？

我知道这取决于“b”变为零所需的时间。有什么数学方法可以找到这个吗？我知道这不会进入数百万次递归。但是仍然很好奇会发生多少次递归？

问题:在不使用任何算术运算的情况下添加 2 个数字-

Answer 1

由于进位左移 a&b，因此其第 0 位(最低有效位或 LSB)为零。此外，进位在每个位置 p 中都为零，而 b 在位置 p-1 中为零。这意味着在第一次递归调用中，b 的 bit-0 为零，而在第二次递归调用中，它的 bit-0 和 bit-1 为零(2 个 LSB 为零)，依此类推。在第n次递归调用中，b将有n个LSB为0，所以当n是a中最高位非零位的位置时，进位将为零，递归将在下一次调用结束。

所以时间复杂度是O(n)，其中n是a中的位数(更准确地说，是a中最高有效非零位的位置，在最坏的情况下是位数在一个)。空间复杂度也是 O(n)，因为有 n 次递归调用，但由于这是尾递归，它可以被优化掉，所以优化后的空间复杂度将是 O(1)。