如何知道以下快照的时间和 space 复杂度？
How to know the time and space complexity of the following snapshot?
我了解以下快照中的代码是如何工作的，但我很好奇我如何知道它的时间和 space 复杂性？
我知道这取决于 'b' 变为零所需的时间。有什么数学方法可以找到这个吗？
我知道这不会进入数百万次递归。但是还是很好奇会发生多少次递归？
问题：
在不使用任何算术运算的情况下添加 2 个数字-
它就像一个纹波进位加法器（但它神奇地 "knows" 当输出稳定并提前输出时）。随着每一步，进位将严格增加最低设置位的位置（如果没有最低设置位则为无穷大）。所以它最多可以为每个位递归一次。代表多少 time/space 取决于您的假设（将位数作为常数会产生无用的结果，从而阻止您将其与其他实现进行比较）。
这显然是一个尾部调用，它可以被重写为一个循环，所以你可以说它比你假装它实际使用了所有堆栈 space 花费更少 space。
此外，也可以在位数为对数的多个步骤中执行此操作，类似于 Kogge-Stone 加法器。
由于进位左移 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中最高有效非零位的位置，在最坏的情况下是数a) 中的位数。 space 复杂度也是 O(n) 因为有 n 个递归调用，但由于这是尾递归，它可以被优化掉，所以优化后的 space 复杂度将是 O(1)。
我了解以下快照中的代码是如何工作的，但我很好奇我如何知道它的时间和 space 复杂性？
我知道这取决于 'b' 变为零所需的时间。有什么数学方法可以找到这个吗？ 我知道这不会进入数百万次递归。但是还是很好奇会发生多少次递归？
问题：
在不使用任何算术运算的情况下添加 2 个数字-
它就像一个纹波进位加法器（但它神奇地 "knows" 当输出稳定并提前输出时）。随着每一步，进位将严格增加最低设置位的位置（如果没有最低设置位则为无穷大）。所以它最多可以为每个位递归一次。代表多少 time/space 取决于您的假设（将位数作为常数会产生无用的结果，从而阻止您将其与其他实现进行比较）。
这显然是一个尾部调用，它可以被重写为一个循环，所以你可以说它比你假装它实际使用了所有堆栈 space 花费更少 space。
此外，也可以在位数为对数的多个步骤中执行此操作，类似于 Kogge-Stone 加法器。
由于进位左移 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中最高有效非零位的位置，在最坏的情况下是数a) 中的位数。 space 复杂度也是 O(n) 因为有 n 个递归调用，但由于这是尾递归，它可以被优化掉，所以优化后的 space 复杂度将是 O(1)。