java - 为一段代码创建递归公式

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))

本文档涵盖了您正在查看的特定问题。他们可能比我做得更好，我很长时间没有看主定理了。