指数算法的复杂度

Question

给定 double x 和正数 int y 我需要找到 x^y 假设输入不会导致溢出。

我想出了一个算法，该算法使用以下关于 x^y 的事实：

x^y=(x^floor(y/2))^2 如果 y 是偶数。
x^y=x*(x^floor(y/2))^2 如果 y 是奇数。
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

是的，该算法实际上称为 binary exponentiation，它的复杂性如您所述为 log_2(y)。两个数字的乘法通常被认为是 O(1) 除非数字可以任意大（也称为 BigInt）。这是因为数字的位数总是常数。

备注

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

Answer 2

您将最多执行 log2(Y) 次循环
- 在第n次循环之后，y至少被二除n次，因为对于每个循环y都被floor(y/2)代替，它低于y/2 - log2(y) 满足 2^log2(y)=y
- 你最多进行 log2(y)+1 循环，因为在 log2(y) 循环之后 y 被 floor(y/y/2)=0
每个循环都有一个常量执行时间
因此你的复杂度为 O(log2(y))

指数算法的复杂度

Complexity of exponentiation algorithm

java

algorithm

big-o

time-complexity

备注