什么是这个递归代码用于计算指数的运行？

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语句，没有循环。我从来没有与大O和递归工作，我不能在网上找到任何好的资源。

Answer 1

您的函数的运行时为O（n），但可以轻松对其进行修改以使其在时间O（log n）内运行。

我们可以通过多种方式看到这一点。首先，由于每个递归调用都可以执行O（1），因此我们可以计算进行递归调用的总数。想象一下，例如，我们称之为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次通话。

现在，假设我们调用战俘（一，16）。这将触发对pow（a，8）的两次调用（总共进行了62次递归调用），再加上一次对pow（a，16）的初始调用，总共进行了63次递归调用。如果我们叫POW（A，32），我们会做两次调用战俘（一，16）（126个总递归调用），加上一个初始调用战俘（一，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），您可以使用主定理进行确认。

通常，请警惕以下形式的论点：“我们将内容减半，因此总体工作最终为O（log n）”。这可能是正确的，但是您在每一步所做的工作量对于确定运行时也非常非常重要，如您在此处看到的。