algorithm - 对此代码片段进行严格的大哦运行时分析

Question

public static long F (int N) {
    if ( N == 1 ) return 1;

    return F(N - F(N-1));
}

现在我认为内部 F(N-1) 将为每个 F( N - F(N-1)) 执行 N 次，所以它将是 N² 但事实并非如此' 似乎是答案。

谁能告诉我为什么？

Answer 1

为了解决这个问题，让我们想象一下以等效的方式重写这段代码:

public static int F (int N) {
    if ( N == 1 ) return 1;
    int k = F(N - 1);
    return F(N - k);
}

我在这里所做的就是提取对 F(N - 1) 的内部调用并将其移动到顶层，以便我们可以更清楚地看到这段代码进行了两次调用到 F 并且第二次调用是针对依赖于第一次调用的子问题。

要确定这里的运行时间，我们需要弄清楚 k 是什么，这样我们才能看到我们正在进行哪种递归调用。有趣的是，对于所有 N，事实证明 F(N) = 1。您可以在这里发现这种模式:

• F(1) = 1。
• F(2) = F(2 - F(1)) = F(2 - 1) = F(1) = 1
• F(3) = F(3 - F(2)) = F(3 - 1) = F(2) = 1
• F(4) = F(4 - F(3)) = F(4 - 1) = F(3) = 1

用归纳法证明这一点是一个很好的练习。

所以这意味着对 F(N - k) 的调用将调用 F(N - 1)。这意味着代码在功能上等同于

public static int F (int N) {
    if ( N == 1 ) return 1;
    int k = F(N - 1);
    return F(N - 1);
}

这有递推关系

• F(1) = 1
• F(n) = 2F(n-1) + 1

求解 F(n) = 2ⁿ - 1。(同样，如果您愿意，可以通过归纳法正式证明这一点)。因此，复杂度为Θ(2ⁿ)。

为了验证这一点，这里有一个(非常骇人听闻的)C 脚本，它在许多不同的输入上调用该函数，报告返回值和调用次数:

#include <stdio.h>

/* Slightly modified version of F that tracks the number of calls made          
 * using the second out parameter.                                              
 */
static int F (int N, int* numCalls) {
  /* Track the number of calls. */
  (*numCalls)++;

  if ( N == 1 ) return 1;
  return F (N - F (N-1, numCalls), numCalls);
}

int main() {
  for (int i = 1; i < 10; i++) {
    int numCalls = 0;
    int result = F(i, &numCalls);
    printf("F(%d) = %d, making %d calls.\n", i, result, numCalls);
  }
}

输出是

F(1) = 1, making 1 calls.
F(2) = 1, making 3 calls.
F(3) = 1, making 7 calls.
F(4) = 1, making 15 calls.
F(5) = 1, making 31 calls.
F(6) = 1, making 63 calls.
F(7) = 1, making 127 calls.
F(8) = 1, making 255 calls.
F(9) = 1, making 511 calls.

请注意，评估 F(i) 总是需要 2ⁱ - 1 次调用(正如理论所预测的那样!)并且总是返回 1，以经验验证数学分析。