algorithm - 计算 x^y 的运行时间

Question

如何找到执行 (y − 1) 乘以 x 的基本算法的运行时间(以大 O 表示法表示)以找到 x^y?

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

Answer 1

好吧，您只需要考虑每个操作的位数并将它们相加即可。当然，我们会进行一些舍入以简化事情，因为它不会影响大 O 符号的答案。

因此，x 中的位数是 ceiling(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)来表达一切，我们想使用大 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))。但它只会进行 ceiling(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 或其他任意精度类型时它不一定更快。这就是为什么它最常用于矩阵乘法等情况，在这些情况下，乘法的成本是恒定的但很大。