algorithm - 分而治之解决数字的力量，利用主定理进行运行时分析

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

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

现在我试图用主定理来确定我的算法的运行时间：
我想，那
，因为递归调用出现了两次，
，因为IAM在一个问题中创建了两个子问题
而且，由于合并结果需要恒定的时间。
分水岭常数（）应为。
有了这些值，我假设定理的第一条规则成立：
，和，从。
因此，运行时应为：
.
我对这个结果很不确定，因为我从未有过这种情况。
我的分析正确吗？

最佳答案

首先，你应该注意到复杂度将根据pow来解释。所以，分析中的n意味着程序中的pow不是n变量。
其次，由于比较和乘法等计算的数量是恒定的（对于您的程序小于10），因此f(n) = \Theta(1)可以在这里编写它。
因此，复杂性是f(n) = 1（也可以看到Akra Bazzi方法）和T(n) = 2T(n/2) + 1。

关于algorithm - 分而治之解决数字的力量，利用主定理进行运行时分析，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56853651/