分治法求解一个数的幂，运行期分析与主定理

Question

我实现了一个分而治之的算法来计算数字的幂：

public static void main(String[] args) {
    System.out.println("Result: " + pow(2, 1));
    System.out.println("Result: " + pow(2, 9));
    System.out.println("Result: " + pow(2, 8));
    System.out.println("Result: " + pow(2, 0));
}

private static int pow(int n, int pow) {
    if(pow == 0) {
        return 1;
    }

    if(pow > 2) {
        int leftPow;
        int rightPow;

        if(pow % 2 != 0) {
            leftPow = pow/2;
            rightPow = pow/2+1;
        } else {
            leftPow = pow/2;
            rightPow = leftPow;
        }

        return pow(n, leftPow) * pow(n, rightPow);
    } else {
        if(pow == 1) {
            return n;
        } else {
            return n * n;
        }
    }
}

我的方法似乎是有效的，因为输出是：

Result: 2
Result: 512
Result: 256
Result: 1

现在我正在尝试使用Master-Theorem来确定算法的运行时间：

​

​

我假设，

​

，因为递归调用出现了两次，

​

，因为我从一个问题中创建了两个子问题

和

，因为合并结果需要恒定的时间。

分水岭常数(

)应该是

。

有了这些值，我假设定理的第一条规则成立：

，具有

，因为

。

因此，运行时应该是：

。

我对这个结果不太确定，因为我从来没有遇到过这样的情况

。

我的分析正确吗？

Answer 1

首先，您应该注意到复杂性将基于pow进行解释。因此，分析中的n意味着程序中的pow而不是n变量。

其次，由于像比较和乘法这样的计算次数是常量(对于你的程序来说小于10 )，所以你可以在这里写f(n) = \Theta(1)，你可以写f(n) = 1。

因此，复杂性是T(n) = 2T(n/2) + 1 (您也可以看到Akra-Bazzi方法)和T(n) = \Theta(n)。