java - 寻找数字幂的有效方法的时间复杂度

Question

我写了一小段代码来求一个数的幂

谁能告诉我如何找到这段代码的时间复杂度。 这段代码的时间复杂度是多少。 并且它是一种求数次幂的有效方法吗

代码是:

public static void main(String[] args) {

        System.out.println(optPower(7, 15));    
    }

    static int optPower(int x, int y) {
        // divide in buckets

        if (y == 0) {
            return 1;
        }
        if (y == 1) {
            return x;
        }
        if (y == 2)
            return x * x;

        int tmpY;

        boolean isYmodified = false;
        if (y % 2 == 0) {
            tmpY = y;
        } else {
            tmpY = y - 1;
            isYmodified = true;
        }

        int biggestBucket = 2;
        int n = biggestBucket;

        /*
         * tmpY/4 , here '4' can be used as a tweking parameter to size the
         * buckets
         */
        while (tmpY % n == 0 && tmpY / 4 >= n) {
            biggestBucket = n;
            n = n * 2;
        }

        int res = 1;
        for (int i = 0; i < biggestBucket; i++) {
            res = res * x;
        }

        int mul = res;
        for (int j = 1; j < tmpY / biggestBucket; j++) {
            mul = mul * res;
        }

        return isYmodified ? mul * x : mul;

    }

应要求，我添加了更多注释以便更清楚地解释算法。

如果我想计算 5 提高到 16

第 1 步:-

5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5

这里x=5，上面方法中y=16

如果 y 是奇数，我们在最终结果中乘以一个额外的 x 并将 tmpY 分配为 y-1 使其均匀

so noOfBuckets = 4 because of below code

while (tmpY % n == 0 ) {
        biggestBucket = n;
        n = n * 2;
    }
    that is 
 16/(2 raise to 2)

step 2:-

divide 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5 into 4 buckets
bucket1 :- 5,5,5,5
bucket2 :- 5,5,5,5
bucket3 :- 5,5,5,5
bucket4 :- 5,5,5,5

第 3 步:- 仅计算桶 1 并将此桶的结果用于剩余的桶 桶 1 的结果 = 625 = 5*5*5*5

第 4 步:- 在此处输入代码 最终结果是 bucket1*bucket1*bucket1*bucket1 即 625 * 625 * 625 * 625 即 5 提高到 16

然后我们避免在桶 2、3、4 中进行迭代，并直接使用桶 1 中的值来获得最终结果。

Answer 1

平方乘法耗时O(log n):

function power(b, e)
    if (e == 0) return 1
    if (e is even) return power(b*b, e/2)
    /* e is odd */ return b * power(b, e-1)