为什么这个循环需要O（2^n）时间复杂度？

Question

有一个循环执行蛮力算法来计算5*3，而不使用算术运算符。

我只需要加5 3次，这样它就需要O（3），如果输入是x*y，它就是O（y）。但是，在一本书中，它说它需要O（2^n），其中n是输入中的位数。我不明白为什么它用O（2^n）来表示它O（y）。这是显示时间复杂度的更好方法吗？。你能解释一下吗？

我没有要求其他算法来计算这个。

int result = 0
for(int i=0; i<3; i++){
    result += 5
}

Answer 1

不要用3和5思考。想想如何计算20亿x20亿（大致2^31乘以2^31）

每个输入为31位（N），循环将执行20亿次，即2^N。

所以，book是正确的。对于5x3的情况，3是2位。所以复杂度是O（2^2）。再次正确。

Answer 2

我认为你误读了这本书中的一段。

当这本书讨论计算两个数字乘积的算法时，它使用了乘以3×5的例子作为通过添加y y... y，x总次数计算x×y的更一般概念的具体实例。它并没有声称特定的算法“添加5 5”在时间O（2ⁿ）中运行。相反，想想这个算法：

int total = 0;
for (int i = 0; i < x; i++) {
    total += y;
}

该算法的运行时是O（x）。如果您将运行时度量为数字x中位数n的函数——正如这本书所建议的那样——那么运行时是O（2ⁿ），因为要表示数字x，您需要O（log n）位。这是多项式时间和伪多项式时间之间的区别，这本书接着描述了解决这个问题的更好算法的原因是，运行时最终是用于表示输入的位数的多项式，而不是数字的数值。关于小学乘法和加法的阐述是为了帮助你更好地理解这两个量之间的区别。

Answer 3

你声称输入的时间复杂度是O（y），这本书声称输入的位数的时间复杂度是O（2）。好消息：你们都是对的！如果数字y可以由n位表示，则y最多为2^{n− 1.}