这段代码的时间复杂度是多少？我知道除了递归部分以外，所有行的时间复杂度都是O(1)。我不确定递归的时间复杂度是多少，我有一种感觉是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);
}
这个函数的最坏情况复杂度实际上是O(n)。如上面评论所讨论的那样，大O符号指的是函数的渐近上界。该函数在最坏情况下的上界是每个输入数字都是max int。这意味着该函数被调用的次数等于一个整数中的位数。如果您的整数有32位，则该函数运行32次，每次执行一系列常量操作。这使得函数的复杂度为O(n)，其中n是您的整数的大小。
n 不能无限增长。也许问题更清晰一些，使用类似位数组的东西。 - martijnn2008n又是什么？由于大O描述了“n”与时间（在这种情况下）之间的关系，那么输入a和/或b与递归次数之间的关联是什么？没有关联。 - Andreasb = (a & b) << 1
a & b 将产生一个最后k位为零的数字，然后将结果向右移动一步将使最右边的0的数量增加1。If the integers passed are similar even if they are not zeros -> it will be invoked one time only. That is because of the XOR or ^ which requires the two corresponding bits to be different. For example:
(decimal) (binary) (decimal) (binary)
5 = 101 1 = 001
6 = 110 1 = 001
********************** Whereas *********************
3 = 011 0 = 000
If the integers passed are not zeros and not similar -> that will take the program to the carry part and here we need to consider the following:
If the two integers have no similar corresponding bits -> (a&b) will equals zero, thus the method will be invoked only one time. For example:
(decimal) (binary) (decimal) (binary)
1 = 001 1 = 001
2 = 010 3 = 011
********************** Whereas *********************
0 = 000 1 = 001
If (a&b) results with no zero -> here we come to the shift part <<
and here is the plot. If ALL the above conditions pass -> then we have a maximum of 32 bit shift and supposing that after each shift the recursion happens -> we have a maximum of 32 recursion BUT NOT always. That means it could be not the case every time (sometimes there would be no recursion as I showed above!).
因此，我认为它要么是O(1)，要么是O(n)，如果我们分析这两种情况，我们会发现：
O(1) means Constant complexity, for example:
1 invocation : 1 second
10 invocation : 1 second
100 invocation: 1 second
And so on..
But that is not the case as I showed above, because every input may cause a recursion and may not! And the recursion is not the same, although the maximum is 32 but it can be between 0 to 32.
O(n) means a Linear complexity, for example:
1 invocation : 1 second
10 invocation : 10 seconds
100 invocation: 100 seconds
And so on..
首先让我引用Wikipedia的话：
大O符号是一种数学符号，描述当参数趋近于特定值或无穷大时函数的极限行为。
在计算机科学中，大O符号用于根据算法运行时间或空间需求随着输入大小的增长而分类。
你问性能是否为O(n)。嗯，在我们回答这个问题之前，什么是n？
正如上面所述，n通常被定义为输入的大小。虽然通常指输入的数量（计数），但在这种情况下，这可以被定义为a或b的大小，因此问题是：随着a和/或b的增加，处理时间（即递归次数）是否增加？
答案是否定的。a或b的大小与递归次数之间没有相关性。当然，递归次数可能会有所不同，但与大小无关。
无论是a还是b，您都具有Omin(1)，Oavg(6.24)和Omax(33)。
更新
然而，当a和b的值较低时，您无法获得33次迭代。迭代次数受限于更大输入的位长度。位长度将是log2(n)，这给出了答案：
O(log n)其中n = max(a, b)
O<sub>max</sub>(33) 相当于 O(1)，因为这种表示法忽略常数。 - SpaceTrucker我会将n解释为值b中最右边的1位及其左侧的位数。随着n的增加，递归迭代的可能次数也会增加。因此，复杂度为O(n)。
carry==0确保了位移，使其不会再有更多位可用。这就是所谓的O(1)。 - martijnn2008O(1)是一种常数复杂度，但在这种情况下@martijnn2008，因为存在一个递归方法，在最后并不总是被调用！我认为它是线性复杂度O(n)！例如1次调用：1秒 10次：10秒等等。 - Yahya