Java-位操作的大O？

Question

这个代码的大O是什么？我知道除了递归部分，所有的线都是O（1）。我不确定递归的大O是什么，我有一种感觉，它仍然是O（1），因为我们没有比O（1）更差的线，但通常递归是O（n）。

代码：

public int getSum(int a, int b) {

        if (b == 0){
            return a;
        }

        if (a == 0){
            return b;
        }

        int add = a ^ b;
        int carry = (a&b) << 1;

        return getSum(add, carry);
    }

编辑：顺便说一句，这不是家庭作业，而是为面试做准备。

Answer 1

首先让我引用维基百科：

大O表示法是一种数学表示法，用于描述当参数趋向于特定值或无穷大时函数的极限行为。

在计算机科学中，大O符号用于根据算法的运行时间或空间需求随输入大小的增长而增长的方式对算法进行分类。

你问性能是否为O（n）。在我们回答之前，什么是n？

如上所述，n通常定义为输入的大小。虽然这通常指的是输入的数量（计数），但在这种情况下，这可以定义为a或b的大小，所以问题是：流转时长（即html" target="_blank">递归次数）是否随着a的增加和/或b的增加而增加？

答案是否定的。a或b的幅度与递归次数之间没有相关性。当然，递归的数量不同，但与大小无关

无论n是a还是b，您都有O_min（1）、O_avg（6.24）和O_max（33）。

更新

但是，如果a和b的值较低，则无法获得33次迭代。迭代次数受较大输入的位长度限制。位长度为log2（n），这给出了答案：

O（对数n），其中n=max（a，b）

Answer 2

当您试图分析递归算法的复杂性时，找到输入的“大小”随时间下降的方式通常会有所帮助。例如，如果您正在分析递归阶乘实现，那么您可能会注意到每次调用时输入的大小都会减少一个，然后用它来表示总共有O（n）个调用，因此总共完成了O（n）个工作。

这个递归函数分析起来有点棘手，因为它根本不清楚什么量会随着时间而减少。第一个和第二个参数的值都可以随着函数的运行而增加，这在使用递归时通常不是一件好事！

然而，这里有一个有用的观察结果。看看递归函数的第二个参数的值。每次重新计算为

b = (a & b) << 1

这有一个非常有趣的效果：b的二进制表示末尾的0位数在每次函数调用中至少增加一位。要看到这一点，假设b以k0位结束。计算<代码>a

同时，当b的二进制表示中最右边的0的数量超过a的二进制表示中最左边的1的位置时，该算法将终止。要了解原因，请注意，我们将b与a进行ANDing，一旦b中的1位高于a中的1位，并计算为0，则会触发基本情况。

综上所述，我们可以看到递归调用的数量受数字a中最高1位的位置限制，因为每次迭代都会将b中的1位移得越来越高，当这些1移过a中的1时，递归停止。

所以现在的问题是，从大O的角度来看，这意味着什么。如果您有一个数字n，并将n写入二进制，则n中最高1位的位置为O（对数n），因为该位的含义随时间呈指数增长。因此，这里的运行时是O（log n），其中n是两个输入中的最大值。

Answer 3

这个函数实际上是最坏的情况。如上文所述，大O表示法引用了函数的渐近上界。在最坏的情况下，该函数的上界是每个输入数字都是一个最大int。这意味着调用函数的次数等于整数中的位数。如果整数有32位，则函数运行32次，每次执行一系列常量运算。这使得函数为O（n），其中n是整数的大小。