以输入大小N表示的big-Theta运行时间

Question

当N位整数a>1时，a=a/2

我认为它是log(n)，因为每次执行while循环时，您都会将a除以2，但我的朋友认为它是2logn(N)。

Answer 1

很明显，你的算法是big-Theta(log(a))，的，其中a是你的数字

但就我对您的问题的理解而言，您想知道渐近运行时取决于您的数字的位数

这真的很难说，这取决于你的数字：

假设你有一个n位的整数，最高有效位是1，你必须把它除以n次，才能得到一个小于1的数。

现在让我们看一个整数，其中只有最小的信号位是1(所以它等于十进制中的数字1)。在那里你只需要一个部门。

所以我会说，它平均需要n/2，这使得它是-Theta(N)，这里n是你的数字的位数。最坏的情况也在big-Theta(n)中，而最好的情况在big-Theta(1)中

注意:在二进制系统中，将数字除以2的效果与在十进制系统

中将数字除以10的效果相似

Answer 2

通过采用二进制记数法中的数字并移位比特，可以有效地实现将整数除以2。在最坏的情况下，所有的位都被设置为，你必须为第一次除法移位(n-1)位，为第二次除法移位(n-2)位，依此类推，直到你在最后一次迭代中移位1位，发现数字等于1，这时你就停止了。这意味着您的算法必须将1+2+...+(n-1) = n(n-1)/2位移位，使您的算法在输入位数中为O(n^2)。

a = (a == 0 ? 0 : 1)是一种更有效的算法，它将使a具有相同的值。这会在线性时间内生成相同的答案(相等性检查在位数上是线性的)，并且它是有效的，因为您的代码只会在a最初为零的情况下离开a = 0；在所有其他情况下，最高阶位将在单元的位置结束。