计算x^y的运行时间

Question

如何查找执行(y − 1)乘法的基本算法的运行时间（以Big-O表示法）x找到x^y？

编辑：我还需要记住每个乘法的运行时间：“假设将n-bit数字乘以m-bit数字的时间是O(mn)”。

Answer 1

那么，你只需要考虑每个操作的位数并将它们相加即可。当然，为了简单起见，我们会做一些小调整，因为它不会影响大O符号的答案。因此，x中的位数是上限（log2（x））（即x的对数基数2以上的下一个整数）。为简单起见，我们将称这个数字为b。这意味着x大于2 ^（b-1）且小于2^b。所以x^2大于2 ^（2（b-1））且小于2 ^（2b）。因此，我们将假设x^2的大小约为2b，并且通常x^n的大小为nb。这是非常接近于正确的，因为它位于n（b-1）和nb之间。

我们的第一乘法需要时间b * b = b^2。我们的第二次乘法运算需要2b * b（因为x^2的大小为2b，而x的大小为b）。我们的第三个将是3b * b（因为x^3的大小为3b，而x的大小为b）。所以，一般来说，我们的第n次乘法将是nb * b。所以我们的总和看起来像b^2 + 2b^2 + 3b^2 + ... +（y-1）b^2。我们可以分解出b^2，给出我们（b^2）（1 + 2 + 3 + ... +（y-1））。对于第二项，1 + 2 + 3 + ... +（y-1），我们可以使用一个公式：1 + 2 + 3 + ... + n = n（n + 1）/ 2。所以我们得到（b^2）（y-1）（y）/ 2。

在这一点上我们非常接近答案，但我们想要做两件事：我们想用x和y表示所有东西（而不是b），并且我们想用big-O来减少事物为简单起见，表示法。 （y-1）（y）/ 2可以简化为O（y^2）。 b = ceiling（log2（x）），可以简化为O（log（x））。重新取代，我们得到O（（log（x））^ 2 * y^2）。

所有这一切，当然，假设我们使用的算法是这样的：

product = 1 
for i = 1 to y 
    product = product * x 
return product 

如果我们正在做的事情更复杂，更奇怪的是这样一个：

xs = empty list 
for i = 1 to y 
    xs.addItem(x) 
while xs is not empty 
    num1 = xs.removeRandomItem 
    num2 = xs.removeRandomItem 
    xs.addItem(num1*num2) 
return head(xs) 

然后时序分析变得更加复杂。 （请注意，此算法也做Y-1相乘，并得到正确的结果。）

寻找X^Y中的其他常见的算法是重复的平方算法是这样的：

result = 1 
temp = x 
while y>0 
    if y mod 2 = 1 
    result = result * temp 
    y = y - 1 
    temp = temp * temp 
    y = y/2 
return result 

对于我们每轮进行两次乘法运算，其中包含两个数字，每个数字的大小都是b（2^n），其中n是从0开始计数的整数（也就是我们经历while循环的次数）。因此，在第n轮中，每次乘法的代价为b（2^n）* b（2^n）=（b^2）（2 ^（2n））。但它只能上限（log2（y））轮。所以它的运行时间是（b^2）（2^0）+（b^2）（2^2）+（b^2）（2^4）+ ... +（b^2 ）（2 ^（2 *天花板（LOG2（Y））））。因此，我们可以再次将b^2离开（b^2）（2^0 + 2^2 + 2^4 + ... + 2 ^（2 * ceiling（log2（y））））。尽管看起来很复杂，但整个第二项实际上是O（y^2）。一旦我们再次取代b，我们发现这个也是O（（log（x））^ 2 * y^2）。所以，虽然这种算法在乘法是恒定时间操作时速度更快，但当我们使用BigIntegers或其他任意精度类型时，速度并不一定更快。这就是为什么它最常用于矩阵乘法这样的情况，其中乘法的代价是恒定的，但是很大。

Answer 2

Ø根据您选择的方法（迟缓）或O（Y），你应该开始阅读本http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4

在你的情况的步骤（Y-1）乘法O（Y）数，假设一乘法是一个操作，因为y的大小加倍会导致所需操作的数量翻倍，这被称为线性过程。 LE：在这种情况下，您将有1 * n^2 + 2 * n^2 + ... + y * n^2。您第一次将数字乘以自己，因此n * n = n^2第二次将结果n * n（大小2n）除以数字n => 2n^2等等。

N^2（1 + 2 + ... Y）= N^2 * Y *（Y + 1）/ 2

因此，答案为O（n^2 * Y^2）其中n = x中的位数（或n = ceil（log（x）））。

Answer 3

如果将每次乘法计算为单个操作，则需要y - 1步骤的算法仅为O(y - 1) = O(y)，这是您将为此问题找到的最常见答案。事实上，乘法不能在一定的时间内完成，所以你需要乘以你使用的任何multiplication algorithm的速度。

请注意，通过使用exponentiation by squaring，您可以执行少于y - 1的操作，而您的指数运算算法可以代替为O(log y)。