c++ - 这个用于计算指数的递归代码的运行时间是多少？

Question

以下函数的运行时间复杂度是否为O(1)？

int pow(int a, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return pow(a, n / 2) * pow(a, n / 2) * a;
    } else {
        return pow(a, n / 2) * pow(a, n / 2);
    }
}

我有这种印象，因为代码中只有 if 语句，没有循环。我以前从未使用过 Big-O 和递归，我在网上找不到任何好的资源。

Answer 1

您的函数的运行时间为 O(n)，但可以轻松修改为按时间 O(log n) 运行。

我们可以通过多种方式看到这一点。首先，我们可以计算递归调用的总数，因为每个递归调用的复杂度为 O(1)。想象一下，例如，我们为某个数字 a 调用 pow(a, 8)。然后

• pow(a, 8) 调用 pow(a, 4) 两次。
• pow(a, 4) 调用 pow(a, 2) 两次。
• pow(a, 2) 调用 pow(a, 1) 两次。
• pow(a, 1) 调用 pow(a, 0) 两次。

这意味着有

• 1 次调用 pow(a, 8)，
• 2 次调用 pow(a, 4)，
• 4 次调用 pow(a, 2)，
• 8 次调用 pow(a, 1)，以及
• 16 次调用 pow(a, 0)。

总的来说，这是 1 + 2 + 4 + 8 + 16 = 31 次调用。

现在，假设我们调用 pow(a, 16)。这将触发对 pow(a, 8) 的两次调用(总共进行了 62 次递归调用)，再加上一次对 pow(a, 16) 的初始调用，总共进行了 63 次递归调用。如果我们调用 pow(a, 32)，我们将对 pow(a, 16) 进行两次调用(总共 126 次递归调用)，再加上一次对 pow(a, 32) 的初始调用，总共 127 次递归调用.更一般地说，如果我们调用 pow(a, n)，我们会进行 4n - 1 次调用，这将是 O(n)。

我们实际上可以正式证明这一点。令 C(n) 为对大小为 n 的输入进行的调用次数。注意

C(0) = 1. C(n) = 2C(n / 2) + 1

这个递归通过主定理求解为 O(n)。

请注意，每个单独的递归调用只做很少的工作。令我们丧命的是，总的递归调用太多了，以至于这些调用的工作量加起来了。但是，尽管进行了很多总 递归调用，但进行的独特 递归调用却很少。所以考虑一下代码的这种变化:

int pow(int a, int n) {
    if (n == 0) return 1;

    int halfPow = pow(a, n / 2);
    if (n % 2 == 0) return halfPow * halfPow;
    else return halfPow * halfPow * a;
}

此代码缓存正在进行的递归调用的值，因此它每次总是触发一个调用。结果，每次调用完成的工作仍然是 O(1)，但递归中不再有分支。然后，由于每个递归调用的大小都是原始调用的一半，并且因为每个级别只有一个调用，所以运行时间为 O(log n)，您可以使用 Master 确认定理。

一般来说，要警惕“我们一直把东西减半，所以总的工作量最终是 O(log n)”这种形式的论点。这可能是正确的，但您在每个步骤中所做的工作量对于确定运行时也非常非常重要，如您在此处所见。