为一段代码创建递归公式

Question

我正在做一些作业，但我正在为一个特定的问题而苦苦挣扎。我的作业中有一个类似的问题，所以我需要掌握这个问题。

代码如下：

    public static double power2(double base, int n) {
    switch (n) {
        case 1:
            return base;
        case 2:
            return base * base;
        default:
            if (n % 2 == 0) /* n is even */ {
                return power2(power2(base, n / 2), 2);
            } else /* n is odd */ {
                return power2(power2(base, n / 2), 2) * base;
            }
    }
}

我有基本情况，我认为是 0, n=1; 但是，到达 T(n) 是我挣扎的地方。

需要相似T(n-1)+c,n>1.

我需要用递归公式表达代码

任何人都可以帮我 ELI5 这个吗？

Answer 1

我很想说复发是

T(n) = T(n/2) + O(1)

如果将一般情况重写为

double temp = power2(base, n/2); // T(n/2)
if (n%2 == 0) {
  return power2(temp, 2); // O(1) by looking at the base case
} else {
  return power2(temp, 2) * base; // O(1) by looking at the base case
}

这使得它

O(log(n))

这个document covers the specific problem you're looking at. They're probably doing a better job than I am, I haven't looked at the master theorem很久了。

为一段代码创建递归公式

Creating a recursive formula for a piece of code

java

recursion

formula

master-theorem