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(n)最坏的情况下。正如上面评论中所讨论的，大 O 表示法 引用函数的渐近上界。在最坏的情况下，此函数的上限是您输入的每个数字都是 max int .这意味着该函数被调用的次数等于整数中的位数。如果您的整数有 32 bits ，然后函数运行 32 次，每次执行一系列常量操作。这使得函数 O(n) , 其中n是整数的大小。