求幂算法的复杂性

Question

鉴于double x和肯定int y我需要找到x^y假设输入不会导致溢出。

我想出了一个算法，它使用以下事实x^y：

1. x^y=(x^floor(y/2))^2 如果 y 是偶数。
2. x^y=x*(x^floor(y/2))^2 如果 y 是奇数。
3. x^y=1 如果 y 是 0

实施：

public static double power(double x, int y) {
    if(y==0)
      return 1;

    double z=power(x, y>>>1);
    z*=z;
    if((y&1)==1)
      z*=x;

    return z;
  }

我对它的复杂性分析有些挣扎。有log_2(y)递归级别，没有分支。在算法的每一层上z，乘法复杂度是O(n^2)中n的位数z。我们假设不会发生溢出，因此n最多是double类型中的一半。我是否将此乘法工作视为常数，这使算法的复杂度为O(log_2(y))？

Answer 1

是的，该算法实际上称为二进制取幂，它的复杂性log_2(y)正如您所提到的。通常会考虑两个数字的乘法，O(1)除非数字可以是任意大的（也称为 BigInt）。这是因为一个数的位数总是恒定的。

笔记

另外，虽然与问题不完全相关，但我看到您提到乘法复杂度是O(n)n 位的数量。这不是真的。数字相乘的正常方法实际上是O(n^2). 但事实上，我们可以通过一些快速乘法算法做得更好。但这超出了这个问题的范围。