pow函数从递归到迭代

sulc1iza  于 2021-07-03  发布在  Java
关注(0)|答案(1)|浏览(402)

我的任务是做一个复杂度为o(logn)的递归pow函数,然后用迭代的方式做同样的算法。第一个,我认为我有它,但是,我有麻烦,在做一个完全相同的迭代方式。我有一个是o(logn),但它不是同一个。

public static BigInteger powV2(int x, int y) {
        if (y == 0) {
            return BigInteger.ONE;
        }
        BigInteger powerOfHalfX = powV2(x, y / 2);

        if (y % 2 == 0) {
            return powerOfHalfX.multiply(powerOfHalfX);

        } else {
            return BigInteger.valueOf(x).multiply(powerOfHalfX).multiply(powerOfHalfX);

            //x * powerOfHalfX * powerOfHalfX;
        }
    }

这是一个迭代过程:

public static BigInteger iterativePowV2(int x, int y) {
        BigInteger result = BigInteger.ONE;

        while (y > 0) {
            if (y % 2 == 1) {
                result = result.multiply(BigInteger.valueOf(x));
            }

            y = y >> 1; //y = y/2
            x = x * x; //
        }

        return result;
    }
bwitn5fc

bwitn5fc1#

你很接近。在我看来,这两段代码中的方法都是正确的,但在迭代版本的循环体中出现了一些小问题:

x = x * x;

应该是:

result = result.multiply(result)

因为你想计算你的跑步总量,而不是输入变量。在一些小的输入上测试一下,看看它是否工作正常!
编辑:还是不行,在这里找到了一个解决方案:迭代对数求幂

相关问题